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

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, 18, 33, 25, 29, 26, 21, 21, 22, 21, 18, 29, 22, 25, 23, 19, 26, 23, 26, 29, 28, 22, 29, 32, 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

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)
.
Only paths (2) and (3) are incomparable, thus row 3 = [5, 4, 4, 5, 5].
Triangle begins:
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, 18, 33, 25, 29, 26, 21, 21, 22, 21, 18, 29, 22, 25, 23, ...

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]), 1, 0),
            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]]], 1, 0], {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 *)

Crossrefs

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

Cf. A193691, A193692, A193694.

Sequence in context: A249620 A358537 A025498 * A128971 A292245 A206427

Adjacent sequences: A193690 A193691 A193692 * A193694 A193695 A193696

Keyword

nonn,look,tabf

Author

Alois P. Heinz, Aug 02 2011

Status

approved