login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


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: A332539 A296787 A128299 * A001510 A103099 A266495

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 17 21:35 EST 2020. Contains 332006 sequences. (Running on oeis4.)