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

Comments

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

Links

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

Wikipedia, Counting lattice paths

Formula

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

Example

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

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

Crossrefs

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

Row sums give A261003.

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

Cf. A000108, A001700, A005408, A372014.

Sequence in context: A345943 A342342 A182600 * A179760 A334852 A160552

Adjacent sequences: A371925 A371926 A371927 * A371929 A371930 A371931

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 14 2024

Status

approved