|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
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
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|