The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A143672 Number of chains (totally ordered subsets) in the poset of Dyck paths ordered by inclusion. 4
 1, 2, 4, 24, 816, 239968, 808814912, 38764383658368, 31491961129357837056, 503091371552266970507912704, 179763631086276515267399940231898112, 1609791936564515363272979180683040232936253440 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS 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). REFERENCES R. P. Stanley, Enumerative Combinatorics 1, Cambridge University Press, New York, 1997. LINKS Table of n, a(n) for n=0..11. J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion FORMULA a(n) = 1 + Sum_{i,j in {1..C(n)}} (2*delta - zeta)^(-1)[i,j] where delta is the identity matrix and the zeta matrix is defined: zeta[a,b] = 1 if a<=b in D_n and 0 otherwise. EXAMPLE 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. MAPLE d:= proc(x, y, l) option remember; `if`(x=1, [[l[], y]], [seq(d(x-1, i, [l[], y])[], i=x-1..y)]) end: le:= proc(l1, l2) local i; for i to nops(l1) do if l1[i]>l2[i] then return false fi od; true end: a:= proc(n) option remember; local l, m, g; if n=0 then return 1 fi; l:= d(n, n, []); m:= nops(l); g:= proc(t) option remember; 1 +add(`if`(le(l[d], l[t]), g(d), 0), d=1..t-1); end; 1+ add(g(h), h=1..m) end: seq(a(n), n=0..7); # Alois P. Heinz, Jul 26 2011 CROSSREFS Cf. A143673, A143674, A193629. Chains on one vertex: A000108. Number of maximal chains: A005118. Sequence in context: A296787 A341633 A128299 * A001510 A103099 A342665 Adjacent sequences: A143669 A143670 A143671 * A143673 A143674 A143675 KEYWORD nonn AUTHOR Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Aug 28 2008 EXTENSIONS a(6)-a(11), from Alois P. Heinz, Jul 26 2011, Aug 01 2011 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 20 04:34 EDT 2024. Contains 372703 sequences. (Running on oeis4.)