login
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.
3
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
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
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Aug 01 2011
STATUS
approved