A143672 Number of chains (totally ordered subsets) in the poset of Dyck paths ordered by inclusion.
1, 2, 4, 24, 816, 239968, 808814912, 38764383658368, 31491961129357837056, 503091371552266970507912704, 179763631086276515267399940231898112, 1609791936564515363272979180683040232936253440
Offset: 0
Keywords
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.
Links
Crossrefs
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
Comments