A119770 Number of different antimatroids on n labeled items.

1, 1, 3, 22, 485, 59386, 133059751, 64649980092538

Offset

0,3

Comments

See link for software to generate the sequence. a(8) should be roughly 2^78 and seems hopeless without more mathematics.

Antimatroids are a subset of greedoids, usually defined either in terms of set systems, as David Eppstein does in his tree searches, or in terms of formal languages. The two are equivalent, as discussed in Kempner and Levit. - Jonathan Vos Post, Jun 20 2006

Links

Table of n, a(n) for n=0..7.

David Eppstein, Reverse search for antimatroids.

Yulia Kempner and Vadim E. Levit, Correspondence between two antimatroid algorithmic characterizations, arXiv:math/0307013 [math.CO], 2003.

Przemysław Uznański, Enumeration of antimatroids.

Example

The three antimatroids on the two items 0 and 1 are (a) {},{0},{0,1}, (b) {},{1},{0,1} and (c) {},{0},{1},{0,1}.

Crossrefs

Cf. A224913 (counts antimatroids, taking symmetries into account).

Sequence in context: A364844 A156512 A385549 * A395410 A272659 A233748

Adjacent sequences: A119767 A119768 A119769 * A119771 A119772 A119773

Keyword

nonn,more,hard

Author

David Eppstein, Jun 19 2006

Extensions

a(6) added based on a computer search by Przemyslaw Uznanski - David Eppstein, Feb 26 2013

a(7) added by Przemyslaw Uznanski, computed by Przemyslaw Uznanski and Michał Bartoszkiewicz, Apr 19 2013

Status

approved