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

1, 1, 2, 1, 5, 9, 7, 2, 14, 70, 176, 249, 202, 88, 16, 42, 552, 3573, 13609, 33260, 54430, 60517, 45248, 21824, 6144, 768, 132, 4587, 72490, 653521, 3785264, 15104787, 43358146, 91942710, 146186256, 175196202, 157630704, 104922224, 50152960, 16290560, 3221504

Offset: 0

Author

Alois P. Heinz, Aug 01 2011

Keywords

• nonn
• tabf

Examples

			Poset of Dyck paths of semilength n=3:
.
.      A       A:/\      B:
.      |        /  \      /\/\
.      B       /    \    /    \
.     / \
.    C   D     C:        D:        E:
.     \ /         /\      /\
.      E       /\/  \    /  \/\    /\/\/\
.
Chains of length k=0: A, B, C, D, E (5); k=1: A-B, A-C, A-D, A-E, B-C, B-D, B-E, C-E, D-E (9); k=2: A-B-C, A-B-D, A-B-E, A-C-E, A-D-E, B-C-E, B-D-E (7), k=3: A-B-C-E, A-B-D-E (2) => [5, 9, 7, 2].
Triangle begins:
:   1;
:   1;
:   2,    1;
:   5,    9,     7,      2;
:  14,   70,   176,    249,     202,       88,       16;
:  42,  552,  3573,  13609,   33260,    54430,    60517,    45248, ...
: 132, 4587, 72490, 653521, 3785264, 15104787, 43358146, 91942710, ...
		

Links

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

Crossrefs

Row sums give: A143672-A057427. Column k=0 gives: A000108. Last elements of rows give: A005118. Row lengths give: A000124(n-1). Cf. A193536.

Programs

Maple

d:= proc(x, y, l) option remember;
      `if`(x<=1, [[l[], y]], [seq(d(x-1, i, [l[], y])[], i=x-1..y)])
    end:
le:= proc(l1, l2) local i;
       for i to nops(l1) do if l1[i]>l2[i] then return false fi od; true
     end:
T:= proc(n) option remember; local h, l, m, g, r;
      l:= d(n, n, []); m:= nops(l);
      g:= proc(t) option remember; local r, d;
            r:= [1];
            for d to t-1 do if le(l[d], l[t]) then
              r:= zip((x, y)->x+y, r, [0, g(d)[]], 0)
            fi od; r
          end;
      r:= [];
      for h to m do
        r:= zip((x, y)->x+y, r, g(h), 0)
      od; r[]
    end:
seq(T(n), n=0..7);