A193691 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.

1, 1, 1, 2, 1, 2, 2, 4, 5, 1, 2, 2, 4, 5, 2, 4, 4, 8, 10, 5, 10, 13, 14, 1, 2, 2, 4, 5, 2, 4, 4, 8, 10, 5, 10, 13, 14, 2, 4, 4, 8, 10, 4, 8, 8, 16, 20, 10, 20, 26, 28, 5, 10, 10, 20, 25, 13, 26, 34, 37, 14, 28, 37, 41, 42, 1, 2, 2, 4, 5, 2, 4, 4, 8, 10, 5, 10, 13, 14, 2, 4, 4, 8, 10, 4

Offset: 0

Author

Alois P. Heinz, Aug 02 2011

Keywords

• nonn
• look
• tabf

Examples

			Dyck paths of semilength n=3 listed in lexicographic order:
.                                               /\
.                  /\      /\        /\/\      /  \
.     /\/\/\    /\/  \    /  \/\    /    \    /    \
.     101010    101100    110010    110100    111000
. k = (1)       (2)       (3)       (4)       (5)
.
We have (1) <= (1); (1),(2) <= (2); (1),(3) <= (3); (1),(2),(3),(4) <= (4); and (1),(2),(3),(4),(5) <= (5), thus row 3 = [1, 2, 2, 4, 5].
Triangle begins:
  1;
  1;
  1, 2;
  1, 2, 2, 4, 5;
  1, 2, 2, 4, 5, 2, 4, 4, 8, 10, 5, 10, 13, 14;
  1, 2, 2, 4, 5, 2, 4, 4, 8, 10, 5, 10, 13, 14, 2, 4, 4, 8, ...
		

Links

• Alois P. Heinz, Rows n = 0..9, flattened

Crossrefs

Row sums give A005700.

Lengths and last elements of rows give A000108.

Cf. A193692, A193693, A193694.

Programs

Maple

d:= proc(n, l) local m; m:= nops(l);
      `if`(n=m, [l], [seq(d(n, [l[], j])[],
                     j=`if`(m=0, 1, max(m+1, l[-1]))..n)])
    end:
le:= proc(x, y) local i;
       for i to nops(x) do if x[i]>y[i] then return false fi od; true
     end:
T:= proc(n) option remember; local l;
      l:= d(n, []);
      seq(add(`if`(le(l[i], l[j]), 1, 0), i=1..j), j=1..nops(l))
    end:
seq(T(n), n=0..6);

Mathematica

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[[i]], l[[j]]], 1, 0], {i, 1, j}], {j, 1, Length[l]}]]; Table[T[n], {n, 0, 6}] // Flatten (* Jean-François Alcover, Feb 01 2017, after Alois P. Heinz *)