Tag Archives: Family of sets

Enumeration of Antimatroids, part II

As explained before, we would like to extend the following sequence A119770 (don’t click, it will spoil all the fun!):
1, 1, 3, 22, 485, 59386, ...
Continue reading

Advertisements

Enumeration of Antimatroids, part I

Recently I found an interesting problem: enumeration of possible antimatroids over finite set.

From combinatorial point of view, an antimatroid is a family of sets, with special properties.
Following the wikipedia definition, F is an antimatroid iff:

  • F is closed under unions, that is: \forall_{u,v \in F} u \cup v \in F
  • F is a nonempty accesible: \forall_{u \in F} ((u = \emptyset) \vee (\exists_{a \in u} u \setminus \{a\} \in F))

For example, following family is an antimatroid:
\{\{\},\{0\},\{2\},\{0,1\},\{0,2\},\{1,2\},\{0,1,2\}\}
From now, I will denote the largest set, being also a superset of every other one in the family, as S (so in previous example, S=\{0,1,2\}).

Just as matroids are generalization of antichains, antimatroids are generalization of chains.
Continue reading