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,3

Links

Alois P. Heinz, Rows n = 0..13, flattened

J. Woodcock, Properties of the poset of Dyck paths ordered by inclusion

Example

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, ...

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]<l[i]) then
              r:= zip((x, y)->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 *)

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).

Sequence in context: A332632 A124226 A248797 * A152290 A248699 A032006

Adjacent sequences: A193533 A193534 A193535 * A193537 A193538 A193539

Keyword

nonn,tabf

Author

Alois P. Heinz, Jul 29 2011

Status

approved