cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A143672 Number of chains (totally ordered subsets) in the poset of Dyck paths ordered by inclusion.

Original entry on oeis.org

1, 2, 4, 24, 816, 239968, 808814912, 38764383658368, 31491961129357837056, 503091371552266970507912704, 179763631086276515267399940231898112, 1609791936564515363272979180683040232936253440
Offset: 0

Views

Author

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

Keywords

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).

Examples

			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.
		

References

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

Crossrefs

Cf. A143673, A143674, A193629. Chains on one vertex: A000108. Number of maximal chains: A005118.

Programs

  • 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

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.

Extensions

a(6)-a(11), from Alois P. Heinz, Jul 26 2011, Aug 01 2011