A193536 Triangle T(n,k), n>=0, 0<=k<=C(n,2), read by rows: T(n,k) = number of k-length saturated chains in the poset of Dyck paths of semilength n ordered by inclusion.

1, 1, 2, 1, 5, 5, 4, 2, 14, 21, 30, 38, 40, 32, 16, 42, 84, 168, 322, 578, 952, 1408, 1808, 1920, 1536, 768, 132, 330, 840, 2112, 5168, 12172, 27352, 58126, 115636, 212762, 356352, 532224, 687104, 732160, 585728, 292864, 429, 1287, 3960

Offset: 0

Author

Alois P. Heinz, Jul 29 2011

Keywords

• nonn
• tabf

Examples

			Poset of Dyck paths of semilength n=3:
.
.      A       A:/\      B:
.      |        /  \      /\/\
.      B       /    \    /    \
.     / \
.    C   D     C:        D:        E:
.     \ /         /\      /\
.      E       /\/  \    /  \/\    /\/\/\
.
Saturated chains of length k=0: A, B, C, D, E (5); k=1: A-B, B-C, B-D, C-E, D-E (5); k=2: A-B-C, A-B-D, B-C-E, B-D-E (4), k=3: A-B-C-E, A-B-D-E (2) => [5,5,4,2].
Triangle begins:
    1;
    1;
    2,   1;
    5,   5,   4,    2;
   14,  21,  30,   38,   40,    32,    16;
   42,  84, 168,  322,  578,   952,  1408,  1808,   1920,   1536,    768;
  132, 330, 840, 2112, 5168, 12172, 27352, 58126, 115636, 212762, 356352, ...
		

Links

• Alois P. Heinz, Rows n = 0..13, flattened
• J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

Crossrefs

Row sums give: A166860. Columns k=0,1 give: A000108, A002054(n-1). Last elements of rows give: A005118. Row lengths give: A000124(n-1).

Programs

Maple

d:= proc(x, y, l) option remember;
      `if`(x<=1, [[y, l[]]], [seq(d(x-1, i, [y, l[]])[], i=x-1..y)])
    end:
T:= proc(n) option remember; local g, r, j;
      g:= proc(l) option remember; local r, i;
            r:= [1];
            for i to n-1 do if l[i]>i and (i=1 or l[i-1]x+y, r, [0, g(subsop(i=l[i]-1, l))[]], 0)
            fi od; r
          end;
      r:= [];
      for j in d(n, n, []) do
        r:= zip((x, y)->x+y, r, g(j), 0)
      od; r[]
    end:
seq(T(n), n=0..7);

Mathematica

zip = With[{m = Max[Length[#1], Length[#2]]}, PadRight[#1, m] + PadRight[#2, m]]&; d[x_, y_, l_] := d[x, y, l] = If[x <= 1, {Prepend[l, y]}, Flatten[t = Table [d[x-1, i, Prepend[l, y]], {i, x-1, y}], 1]];
T[n_] := T[n] = Module[{g, r0}, g[l_] := g[l] = Module[{r, i}, r = {1}; For[i = 1, i <= n-1 , i++, If [l[[i]]>i && (i == 1 || l[[i-1]] < l[[i]]), r = zip[r, Join[{0}, g[ReplacePart[l, i -> l[[i]]-1]]]]]]; r]; r0 = {}; Do[r0 = zip[r0, g[j]], {j, d[n, n, {}]}]; r0]; Table[T[n], {n, 0, 7}] // Flatten (* Jean-François Alcover, Feb 13 2017, translated from Maple *)