A371928 T(n,k) is the total number of levels in all Dyck paths of semilength n containing exactly k path nodes; triangle T(n,k), n>=0, 1<=k<=n+1, read by rows.

1, 1, 1, 1, 3, 1, 3, 5, 6, 1, 8, 15, 13, 11, 1, 23, 44, 43, 29, 20, 1, 71, 134, 138, 106, 62, 37, 1, 229, 427, 446, 371, 248, 132, 70, 1, 759, 1408, 1478, 1275, 941, 571, 283, 135, 1, 2566, 4753, 5017, 4410, 3437, 2331, 1310, 611, 264, 1, 8817, 16321, 17339, 15458, 12426, 9027, 5709, 3002, 1324, 521, 1

Offset: 0

Author

Alois P. Heinz, Apr 14 2024

Keywords

• nonn
• tabl

Comments

A Dyck path of semilength n has 2n+1 = A005408(n) nodes.

Examples

			In the A000108(3) = 5 Dyck paths of semilength 3 there are 3 levels with 1 node, 5 levels with 2 nodes, 6 levels with 3 nodes, and 1 level with 4 nodes.
  1
  2   /\      2           1           1
  2  /  \     3  /\/\     3  /\       3    /\     3
  2 /    \    2 /    \    3 /  \/\    3 /\/  \    4 /\/\/\    .
  So row 3 is [3, 5, 6, 1].
Triangle T(n,k) begins:
     1;
     1,     1;
     1,     3,     1;
     3,     5,     6,     1;
     8,    15,    13,    11,     1;
    23,    44,    43,    29,    20,    1;
    71,   134,   138,   106,    62,   37,    1;
   229,   427,   446,   371,   248,  132,   70,    1;
   759,  1408,  1478,  1275,   941,  571,  283,  135,    1;
  2566,  4753,  5017,  4410,  3437, 2331, 1310,  611,  264,   1;
  8817, 16321, 17339, 15458, 12426, 9027, 5709, 3002, 1324, 521, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..20, flattened
• Wikipedia, Counting lattice paths

Crossrefs

Columns k=1-2 give: A152880, A371903.

Row sums give A261003.

T(n+1,n+1) gives A006127.

Cf. A000108, A001700, A005408, A372014.

Programs

Maple

g:= proc(x, y, p) (h-> `if`(x=0, add(z^coeff(h, z, i)
          , i=0..degree(h)), b(x, y, h)))(p+z^y) end:
b:= proc(x, y, p) option remember; `if`(y+2<=x,
      g(x-1, y+1, p), 0)+`if`(y>0, g(x-1, y-1, p), 0)
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=1..n+1))(g(2*n, 0$2)):
seq(T(n), n=0..10);

Formula

Sum_{k=1..n+1} k * T(n,k) = A001700(n) = A005408(n) * A000108(n).