A143673 Number of antichains in the poset of Dyck paths ordered by inclusion.

2, 2, 3, 7, 42, 2361, 37620704

Offset: 0

Author

Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Aug 28 2008

Keywords

• nonn
• more

Comments

Also the number of order ideals (down-sets) for this poset.

This is the breakdown by size of (or number of elements in) the antichains beginning with antichains of size 0 and increasing:

n=0: 1, 1;

n=1: 1, 1;

n=2: 1, 2;

n=3: 1, 5, 1;

n=4: 1, 14, 21, 6;

n=5: 1, 42, 309, 793, 810, 348, 56, 2;

n=6: 1, 132, 4059, 54706, 390885, 1648100, 4380095, 7682096, 9172750, 7585779, 4370731, 1749626, 481189, 89055, 10676, 785, 38, 1;

Note that the number of maximum antichains (for each n) is given by the rightmost entry in each of these rows.

Examples

			For n = 3 there are 7 antichains. Assume that the five elements in the D_3 poset are depicted using a Hasse diagram and labeled A through E from bottom to top. Then the 7 antichains are: { }, {A}, {B}, {C}, {D}, {E}, {B,C}.
		

References

• R. P. Stanley, Enumerative Combinatorics 1, Cambridge University Press, New York, 1997.

Links

• J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

Crossrefs

Cf. A143672. Number of maximal antichains A143674.

Extensions

a(6) from Alois P. Heinz, Jul 28 2011