A193693 - OEIS

%I #20 Oct 08 2022 10:26:39

%S 1,1,2,2,5,4,4,5,5,14,10,11,10,8,10,9,10,12,12,8,12,14,14,42,29,33,26,

%T 18,33,25,29,26,21,21,22,21,18,29,22,25,23,19,26,23,26,29,28,22,29,32,

%U 31,18,19,21,28,30,21,32,38,39,18,31,39,42,42,132,91,105,79,52,108,78,92,73,52

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

%H Alois P. Heinz, <a href="/A193693/b193693.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 Only paths (2) and (3) are incomparable, thus row 3 = [5, 4, 4, 5, 5].

%e Triangle begins:

%e 1;

%e 1;

%e 2,   2;

%e 5,   4,  4,  5,  5;

%e 14, 10, 11, 10,  8, 10,  9, 10, 12, 12,  8, 12, 14, 14

%e 42, 29, 33, 26, 18, 33, 25, 29, 26, 21, 21, 22, 21, 18, 29, 22, 25, 23, ...

%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[i], l[j]) or le(l[j], l[i]), 1, 0),

%p             i=1..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}]]];

%t le[x_, y_] := Module[{i}, For[i = 1, i <= Length[x], i++, If[x[[i]] > y[[i]], Return[False]]]; True];

%t T[n_] := T[n] = Module[{l}, l = d[n, {}]; Table[Sum[  If[le[l[[i]], l[[j]]] || le[l[[j]], l[[i]]], 1, 0], {i, 1, Length[l]}], {j, 1, Length[l]}]];

%t Table[T[n], {n, 0, 6}] // Flatten (* _Jean-François Alcover_, Oct 08 2022, after _Alois P. Heinz_ *)

%Y Lengths, first, last and second to last elements of rows give A000108.

%Y Cf. A193691, A193692, A193694.

%K nonn,look,tabf

%O 0,3

%A _Alois P. Heinz_, Aug 02 2011