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,4

Links

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

Example

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

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 *)

Crossrefs

Row sums give A005700.

Lengths and last elements of rows give A000108.

Cf. A193692, A193693, A193694.

Sequence in context: A026832 A225044 A325246 * A089408 A350287 A208888

Adjacent sequences: A193688 A193689 A193690 * A193692 A193693 A193694

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Aug 02 2011

Status

approved