cp's OEIS Frontend

A166860 Number of saturated chains in the poset of Dyck paths ordered by inclusion.

%I A166860 #23 Dec 12 2021 22:31:18
%S A166860 1,1,3,16,191,9586,3621062,13539455808,596242050871827,
%T A166860 358279069210950329112,3339667708892016201497713938,
%U A166860 540966002417189385158099747634890008,1685909333511453301447626182908204645875878754,110859993072493750180447848516163015805399916591746521402
%N A166860 Number of saturated chains in the poset of Dyck paths ordered by inclusion.
%C A166860 Breakdown by length of chain:
%C A166860 n: chains
%C A166860 0:  1;
%C A166860 1:  1;
%C A166860 2:  2,  1;
%C A166860 3:  5,  5,   4,   2;
%C A166860 4: 14, 21,  30,  38,  40,  32,   16;
%C A166860 5: 42, 84, 168, 322, 578, 952, 1408, 1808, 1920, 1536, 768;
%C A166860 Note that for each n, there are C_n chains of length 0 (A000108) and the number of maximal chains is A005118.
%D A166860 R. P. Stanley, Enumerative Combinatorics 1, Cambridge University Press, New York, 1997.
%H A166860 J. Woodcock, <a href="http://garsia.math.yorku.ca/~zabrocki/papers/DPfinal.pdf">Properties of the poset of Dyck paths ordered by inclusion</a>
%F A166860 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).
%F A166860 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.
%e A166860 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.
%e A166860 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.
%p A166860 # E.g., for n=3, using John Stembridge's Symmetric Functions package:
%p A166860 withSF();
%p A166860 AA:=add(s[op(la)],la=subPar([2,1]));tos(skew(AA,AA));
%p A166860 scalar(%, add(h1^r,r=0..4));
%p A166860 # second Maple program:
%p A166860 d:= proc(x, y, l) option remember;
%p A166860       `if`(x<=1, [[y, l[]]], [seq(d(x-1, i, [y, l[]])[], i=x-1..y)])
%p A166860     end:
%p A166860 a:= proc(n) option remember; local g;
%p A166860       g:= proc(l) option remember;
%p A166860             1 +add(`if`(l[i]>i and (i=1 or l[i-1]<l[i]),
%p A166860                 g(subsop(i=l[i]-1, l)), 0), i=1..n-1)
%p A166860           end;
%p A166860       add(g(j), j=d(n, n, []))
%p A166860     end:
%p A166860 seq(a(n), n=0..10);  # _Alois P. Heinz_, Jul 27 2011
%t A166860 d[x_, y_, l_List] := d[x, y, l] = If[x <= 1, {Join[{y}, l]}, Flatten[Table[d[x-1, i, Join[{y}, l]], {i, x-1, y}], 1]]; a[n_] := a[n] = Module[{g}, g[l_List] := g[l] = 1 + Sum[If[l[[i]] > 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_ *)
%Y A166860 Cf. A143672, A000108, A005118.
%K A166860 nonn
%O A166860 0,3
%A A166860 Jennifer Woodcock (jennifer.woodcock(AT)ugdsb.on.ca), Oct 21 2009
%E A166860 a(9)-a(13) from _Alois P. Heinz_, Jul 27 2011