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

Offset

0,3

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),(2),(3),(4),(5) >= (1); (2),(4),(5) >= (2); (3),(4),(5) >= (3);
(4),(5) >= (4); and (5) >= (5), thus row 3 = [5, 3, 3, 2, 1].
Triangle begins:
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, 26, 19, 12, 17, 13, 9, 5, 28, 19, 22, 16, ...

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[j], l[i]), 1, 0), i=j..nops(l)), 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[[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 *)

Crossrefs

Row sums give A005700.

Lengths and first elements of rows give A000108.

Cf. A193691, A193693, A193694.

Sequence in context: A123346 A163840 A122833 * A344028 A075303 A076062

Adjacent sequences: A193689 A193690 A193691 * A193693 A193694 A193695

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Aug 02 2011

Status

approved