cp's OEIS Frontend

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.

%I A193629 #18 May 30 2017 09:57:14
%S A193629 1,1,2,1,5,9,7,2,14,70,176,249,202,88,16,42,552,3573,13609,33260,
%T A193629 54430,60517,45248,21824,6144,768,132,4587,72490,653521,3785264,
%U A193629 15104787,43358146,91942710,146186256,175196202,157630704,104922224,50152960,16290560,3221504
%N 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.
%H A193629 Alois P. Heinz, <a href="/A193629/b193629.txt">Rows n = 0..11, flattened</a>
%H A193629 J. Woodcock, <a href="http://garsia.math.yorku.ca/~zabrocki/papers/DPfinal.pdf">Properties of the poset of Dyck paths ordered by inclusion</a>
%e A193629 Poset of Dyck paths of semilength n=3:
%e A193629 .
%e A193629 .      A       A:/\      B:
%e A193629 .      |        /  \      /\/\
%e A193629 .      B       /    \    /    \
%e A193629 .     / \
%e A193629 .    C   D     C:        D:        E:
%e A193629 .     \ /         /\      /\
%e A193629 .      E       /\/  \    /  \/\    /\/\/\
%e A193629 .
%e A193629 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].
%e A193629 Triangle begins:
%e A193629 :   1;
%e A193629 :   1;
%e A193629 :   2,    1;
%e A193629 :   5,    9,     7,      2;
%e A193629 :  14,   70,   176,    249,     202,       88,       16;
%e A193629 :  42,  552,  3573,  13609,   33260,    54430,    60517,    45248, ...
%e A193629 : 132, 4587, 72490, 653521, 3785264, 15104787, 43358146, 91942710, ...
%p A193629 d:= proc(x, y, l) option remember;
%p A193629       `if`(x<=1, [[l[], y]], [seq(d(x-1, i, [l[], y])[], i=x-1..y)])
%p A193629     end:
%p A193629 le:= proc(l1, l2) local i;
%p A193629        for i to nops(l1) do if l1[i]>l2[i] then return false fi od; true
%p A193629      end:
%p A193629 T:= proc(n) option remember; local h, l, m, g, r;
%p A193629       l:= d(n, n, []); m:= nops(l);
%p A193629       g:= proc(t) option remember; local r, d;
%p A193629             r:= [1];
%p A193629             for d to t-1 do if le(l[d], l[t]) then
%p A193629               r:= zip((x, y)->x+y, r, [0, g(d)[]], 0)
%p A193629             fi od; r
%p A193629           end;
%p A193629       r:= [];
%p A193629       for h to m do
%p A193629         r:= zip((x, y)->x+y, r, g(h), 0)
%p A193629       od; r[]
%p A193629     end:
%p A193629 seq(T(n), n=0..7);
%Y A193629 Row sums give: A143672-A057427. Column k=0 gives: A000108. Last elements of rows give: A005118. Row lengths give: A000124(n-1). Cf. A193536.
%K A193629 nonn,tabf
%O A193629 0,3
%A A193629 _Alois P. Heinz_, Aug 01 2011