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

Comments

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

Links

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

Wikipedia, Motzkin number

Formula

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

Example

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

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

Crossrefs

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

Row sums give A372033 = A001006 + A333498.

Cf. A005717, A371928.

Sequence in context: A247719 A131308 A261360 * A350587 A184242 A307739

Adjacent sequences: A372011 A372012 A372013 * A372015 A372016 A372017

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 15 2024

Status

approved