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

1, 0, 1, 1, 1, 1, 2, 2, 2, 1, 4, 6, 4, 3, 1, 8, 14, 12, 7, 4, 1, 18, 32, 33, 21, 11, 5, 1, 44, 74, 84, 64, 34, 16, 6, 1, 113, 180, 208, 181, 111, 52, 22, 7, 1, 296, 457, 520, 485, 344, 179, 76, 29, 8, 1, 782, 1195, 1334, 1273, 1000, 599, 274, 107, 37, 9, 1

Offset: 0

Author

Alois P. Heinz, Apr 15 2024

Keywords

• nonn
• tabl

Comments

A Motzkin path of length n has n+1 nodes.

Examples

			In the A001006(3) = 4 Motzkin paths of length 3 there are 2 levels with 1 node, 2 levels with 2 nodes, 2 levels with 3 nodes, and 1 level with 4 nodes.
  2  _     1        1
  2 / \    3 /\_    3 _/\    4 ___    .
  So row 3 is [2, 2, 2, 1].
Triangle T(n,k) begins:
    1;
    0,    1;
    1,    1,    1;
    2,    2,    2,    1;
    4,    6,    4,    3,    1;
    8,   14,   12,    7,    4,   1;
   18,   32,   33,   21,   11,   5,   1;
   44,   74,   84,   64,   34,  16,   6,   1;
  113,  180,  208,  181,  111,  52,  22,   7,  1;
  296,  457,  520,  485,  344, 179,  76,  29,  8, 1;
  782, 1195, 1334, 1273, 1000, 599, 274, 107, 37, 9, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..28, flattened
• Wikipedia, Motzkin number

Crossrefs

Columns k=1-2 give: A088457, A051485.

Row sums give A372033 = A001006 + A333498.

Cf. A005717, A371928.

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+1<=x, g(x-1, y, 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(n, 0$2)):
seq(T(n), n=0..10);

Formula

Sum_{k=1..n+1} k * T(n,k) = A005717(n+1) = (n+1) * A001006(n).