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

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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; text; 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 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)); # second Maple 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] i && (i == 1 || l[[i-1]] < l[[i]]), g[ReplacePart[l, i -> l[[i]] - 1]], 0], {i, 1, n-1}]; Sum[g[j], {j, d[n, n, {}]}]]; Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Jul 06 2015, after Alois P. Heinz *) CROSSREFS Cf. A143672, A000108, A005118. Sequence in context: A045990 A007006 A174137 * A196562 A317073 A272658 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, Jul 27 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.

Last modified January 19 20:41 EST 2020. Contains 331066 sequences. (Running on oeis4.)