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

Links

Alois P. Heinz, Rows n = 0..11, 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       /\/  \    /  \/\    /\/\/\
.
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, ...

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

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.

Sequence in context: A176665 A199050 A306539 * A021467 A011132 A178627

Adjacent sequences: A193626 A193627 A193628 * A193630 A193631 A193632

Keyword

nonn,tabf

Author

Alois P. Heinz, Aug 01 2011

Status

approved