|
| |
|
|
A166860
|
|
Number of saturated chains in the poset of Dyck paths ordered by inclusion.
|
|
1
| |
|
|
1, 1, 3, 16, 191, 9586, 3621062, 13539455808, 596242050871827, 358279069210950329112, 3339667708892016201497713938, 540966002417189385158099747634890008, 1685909333511453301447626182908204645875878754, 110859993072493750180447848516163015805399916591746521402
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Breakdown by length of chain:
n: chains
0: 1;
1: 1;
2: 2, 1;
3: 5, 5, 4, 2;
4: 14, 21, 30, 38, 40, 32, 16;
5: 42, 84, 168, 322, 578, 952, 1408, 1808, 1920, 1536, 768;
Note that for each n, there are C_n chains of length 0 (A000108) and the number of maximal chains is A005118.
|
|
|
REFERENCES
| R. P. Stanley, Enumerative Combinatorics 1, Cambridge University Press, New York, 1997.
|
|
|
LINKS
| J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion
|
|
|
FORMULA
| 1) For D_i, D_j in D_n, the number of saturated chains = sum_{D_i<=D_j} (number of standard Young tableaux for D_j\D_i partition)
2) Define zeta(x,y)=1 if x=y or if y immediately covers x in the poset and delta is the identity function. Then the number of saturated chains = sum of entries in the (2*delta - zeta)^(-1) matrix.
|
|
|
EXAMPLE
| For n=3, the Hasse diagram consists of 5 vertices corresponding to the 5 Dyck paths. With area as the rank function, we have one vertex of rank 0, two of rank 1, one of rank 2 and one of rank 3.
There are 16 saturated chains with 5 chains on one vertex, 5 chains on two vertices, 4 chains on three vertices and the 2 maximal chains on four vertices.
|
|
|
MAPLE
| eg. for n=3, using John Stembridge's Symmetric Functions package:
withSF();
AA:=add(s[op(la)], la=subPar([2, 1])); tos(skew(AA, AA));
scalar(%, add(h1^r, r=0..4));
# 2nd program
d:= proc(x, y, l) option remember;
`if` (x<=1, [[y, l[]]], [seq (d(x-1, i, [y, l[]])[], i=x-1..y)])
end:
a:= proc(n) option remember; local g;
g:= proc(l) option remember;
1 +add (`if`(l[i]>i and (i=1 or l[i-1]<l[i]),
g (subsop (i=l[i]-1, l)), 0), i=1..n-1)
end;
add (g(j), j=d(n, n, []))
end:
seq (a(n), n=0..10); # Alois P. Heinz, Jul 27 2011
|
|
|
CROSSREFS
| Cf. A143672, A000108, A005118.
Sequence in context: A045990 A007006 A174137 * A196562 A113597 A000273
Adjacent sequences: A166857 A166858 A166859 * A166861 A166862 A166863
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Oct 21 2009
|
|
|
EXTENSIONS
| a(9)-a(13) from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jul 27 2011
|
| |
|
|
