login
Triangle T(n,k), n>=0, 1<=k<=C(n), read by rows: T(n,k) = number of elements >= k-th path in the poset of Dyck paths of semilength n ordered by inclusion.
5

%I #21 Feb 01 2017 12:28:45

%S 1,1,2,1,5,3,3,2,1,14,9,10,7,4,9,6,7,5,3,4,3,2,1,42,28,32,23,14,32,22,

%T 26,19,12,17,13,9,5,28,19,22,16,10,23,16,19,14,9,13,10,7,4,14,10,12,9,

%U 6,9,7,5,3,5,4,3,2,1,132,90,104,76,48,107,75,89,66,43,62,48,34,20,104

%N Triangle T(n,k), n>=0, 1<=k<=C(n), read by rows: T(n,k) = number of elements >= k-th path in the poset of Dyck paths of semilength n ordered by inclusion.

%H Alois P. Heinz, <a href="/A193692/b193692.txt">Rows n = 0..9, flattened</a>

%e Dyck paths of semilength n=3 listed in lexicographic order:

%e . /\

%e . /\ /\ /\/\ / \

%e . /\/\/\ /\/ \ / \/\ / \ / \

%e . 101010 101100 110010 110100 111000

%e . k = (1) (2) (3) (4) (5)

%e .

%e We have (1),(2),(3),(4),(5) >= (1); (2),(4),(5) >= (2); (3),(4),(5) >= (3);

%e (4),(5) >= (4); and (5) >= (5), thus row 3 = [5, 3, 3, 2, 1].

%e Triangle begins:

%e 1;

%e 1;

%e 2, 1;

%e 5, 3, 3, 2, 1;

%e 14, 9, 10, 7, 4, 9, 6, 7, 5, 3, 4, 3, 2, 1;

%e 42, 28, 32, 23, 14, 32, 22, 26, 19, 12, 17, 13, 9, 5, 28, 19, 22, 16, ...

%p d:= proc(n, l) local m; m:= nops(l);

%p `if`(n=m, [l], [seq(d(n, [l[], j])[],

%p j=`if`(m=0, 1, max(m+1, l[-1]))..n)])

%p end:

%p le:= proc(x, y) local i;

%p for i to nops(x) do if x[i]>y[i] then return false fi od; true

%p end:

%p T:= proc(n) option remember; local l;

%p l:= d(n, []);

%p seq(add(`if`(le(l[j], l[i]), 1, 0), i=j..nops(l)), j=1..nops(l))

%p end:

%p seq(T(n), n=0..6);

%t d[n_, l_] := d[n, l] = Module[{m}, m = Length[l]; If[n == m, {l}, Flatten[#, 1]& @ Table[d[n, Append[l, j]], {j, If[m == 0, 1, Max[m + 1, Last[l]]], n}]]]; le[x_, y_] := Module[{i}, For[i = 1, i <= Length[x], i++, If[x[[i]] > y[[i]] , Return[False]]]; True]; T[n_] := T[n] = Module[{l}, l = d[n, {}]; Table[Sum[If[le[l[[j]], l[[i]]], 1, 0], {i, j, Length[l]}], {j, 1, Length[l]}]]; Table[T[n], {n, 0, 6}] // Flatten (* _Jean-François Alcover_, Feb 01 2017, after _Alois P. Heinz_ *)

%Y Row sums give A005700.

%Y Lengths and first elements of rows give A000108.

%Y Cf. A193691, A193693, A193694.

%K nonn,look,tabf

%O 0,3

%A _Alois P. Heinz_, Aug 02 2011