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

0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 4, 3, 4, 6, 4, 5, 4, 2, 2, 6, 2, 0, 0, 0, 13, 9, 16, 24, 9, 17, 13, 16, 21, 21, 20, 21, 24, 13, 20, 17, 19, 23, 16, 19, 16, 13, 14, 20, 13, 10, 11, 24, 23, 21, 14, 12, 21, 10, 4, 3, 24, 11, 3, 0, 0, 0, 41, 27, 53, 80, 24, 54, 40, 59, 80, 66, 75, 86, 99, 27

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)
.
Only paths (2) and (3) are incomparable, thus row 3 = [0, 1, 1, 0, 0].
Triangle begins:
0;
0;
0,  0;
0,  1, 1,  0,  0;
0,  4, 3,  4,  6, 4,  5,  4,  2,  2,  6,  2,  0,  0;
0, 13, 9, 16, 24, 9, 17, 13, 16, 21, 21, 20, 21, 24, 13, 20, 17, 19, ...
		

Links

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

Crossrefs

Row lengths give A000108.

Cf. A193691, A193692, A193693.

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