0,2

For each n, each vertex in the Hasse diagram of the poset corresponds to a Dyck path of size n. The chain polynomial, C(P,t)=(1 + sum_k(c_k*t^(k+1)), gives the breakdown of this sequence by number of vertices in the chain. The 1 in front of the sum in this equation denotes the empty chain. The coefficient, c_k, gives the number of chains of length k and the exponent, (k+1), indicates the number of vertices in the chain. Here are the chain polynomials corresponding to this sequence:

n=0 1

n=1 1 + t

n=2 1 + 2t + t^2

n=3 1 + 5t + 9t^2 + 7t^3 + 2t^4

n=4 1 + 14t + 70t^2 + 176 t^3+249t^4 + 202t^5 + 88 t^6 + 16 t^7

n=5 1 + 42t + 552t^2 + 3573t^3 + 13609t^4+ 33260 t^5 + 54430t^6 + 60517t^7 + 45248t^8 + 21824t^9 + 6144t^(10) + 768t^(11)

Note that for each n, the coefficient of t is equal to the Catalan number, C_n. It is well-known that the number of Dyck paths in D_n is given by C_n (A000108). The coefficient in front of the largest power of t gives the number of maximal (and also maximum) chains (A005118).

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

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

Let x be the minimum element in D_n and y be the maximum element in D_n.

Total number of chains in D_n = (2*delta - zeta)^(-1)(x,y) where delta is the identity function and the zeta function is defined: zeta(a,b) = 1 if a<=b in D_n and 0 otherwise.

a(3)=24 since in D_3 there are 2 chains of length 3 (i.e., on 4 vertices in the Hasse diagram), 7 chains of length 2 (on 3 vertices), 9 chains of length 1 (on 2 vertices), 5 chains of length 0 (on 1 vertex) and the empty chain: 2 + 7 + 9 + 5 + 1 = 24 chains

Cf. A143673, A143674. Chains on 1 vertex A000108. Number of maximal chains A005118.

Sequence in context: A081476 A009273 A128299 this_sequence A001510 A103099 A119029

Adjacent sequences: A143669 A143670 A143671 this_sequence A143673 A143674 A143675

more,nonn

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