A359364 Triangle read by rows. The Motzkin triangle, the coefficients of the Motzkin polynomials. M(n, k) = binomial(n, k) * CatalanNumber(k/2) if k is even, otherwise 0.

1, 1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 6, 0, 2, 1, 0, 10, 0, 10, 0, 1, 0, 15, 0, 30, 0, 5, 1, 0, 21, 0, 70, 0, 35, 0, 1, 0, 28, 0, 140, 0, 140, 0, 14, 1, 0, 36, 0, 252, 0, 420, 0, 126, 0, 1, 0, 45, 0, 420, 0, 1050, 0, 630, 0, 42, 1, 0, 55, 0, 660, 0, 2310, 0, 2310, 0, 462, 0

Offset

0,9

Comments

The generalized Motzkin numbers M(n, k) are a refinement of the Motzkin numbers M(n) (A001006) in the sense that they are coefficients of polynomials M(n, x) = Sum_{n..k} M(n, k) * x^k that take the value M(n) at x = 1. The coefficients of x^n are the aerated Catalan numbers A126120.

Variants are the irregular triangle A055151 with zeros deleted, A097610 with reversed rows, A107131 and A080159.

In the literature the name 'Motzkin triangle' is also used for the triangle A026300, which is generated from the powers of the generating function of the Motzkin numbers.

Links

Table of n, a(n) for n=0..77.

M. Artioli, G. Dattoli, S. Licciardi, and S. Pagnutti, Motzkin Numbers: an Operational Point of View, arXiv:1703.07262 [math.CO], 2017, (Table 1 on p. 3).

Formula

Let p(n, x) = hypergeom([(1 - n)/2, -n/2], [2], (2*x)^2).

p(n, 1) = A001006(n); p(n, sqrt(2)) = A025235(n); p(n, 2) = A091147(n).

p(2, n) = A002522(n); p(3, n) = A056107(n).

p(n, n) = A359649(n); 2^n*p(n, 1/2) = A000108(n+1).

M(n, k) = [x^k] p(n, x).

M(n, k) = [t^k] (n! * [x^n] exp(x) * BesselI(1, 2*t*x) / (t*x)).

M(n, k) = [t^k][x^n] ((1 - x - sqrt((x-1)^2 - (2*t*x)^2)) / (2*(t*x)^2)).

M(n, n) = A126120(n).

M(n, n-1) = A138364(n), the number of Motzkin n-paths with exactly one flat step.

M(2*n, 2*n) = A000108(n), the number of peakless Motzkin paths having a total of n up and level steps.

M(4*n, 2*n) = A359647(n), the central terms without zeros.

M(2*n+2, 2*n) = A002457(n) = (-4)^n * binomial(-3/2, n).

Sum_{k=0..n} M(n - k, k) = A023426(n).

Sum_{k=0..n} k * M(n, k) = 2*A014531(n-1) = 2*GegenbauerC(n - 2, -n, -1/2).

Sum_{k=0..n} i^k*M(n, k) = A343773(n), (i the imaginary unit), is the excess of the number of even Motzkin n-paths (A107587) over the odd ones (A343386).

Sum_{k=0..n} Sum_{j=0..k} M(n, j) = A189912(n).

Sum_{k=0..n} Sum_{j=0..k} M(n, n-j) = modified A025179(n).

For a recursion see the Python program.

Example

Triangle M(n, k) starts:
[0] 1;
[1] 1, 0;
[2] 1, 0,  1;
[3] 1, 0,  3, 0;
[4] 1, 0,  6, 0,   2;
[5] 1, 0, 10, 0,  10, 0;
[6] 1, 0, 15, 0,  30, 0,   5;
[7] 1, 0, 21, 0,  70, 0,  35, 0;
[8] 1, 0, 28, 0, 140, 0, 140, 0,  14;
[9] 1, 0, 36, 0, 252, 0, 420, 0, 126, 0;

Maple

CatalanNumber := n -> binomial(2*n, n)/(n + 1):
M := (n, k) -> ifelse(irem(k, 2) = 1, 0, CatalanNumber(k/2)*binomial(n, k)):
for n from 0 to 9 do seq(M(n, k), k = 0..n) od;
# Alternative, as coefficients of polynomials:
p := n -> hypergeom([(1 - n)/2, -n/2], [2], (2*x)^2):
seq(print(seq(coeff(simplify(p(n)), x, k), k = 0..n)), n = 0..9);
# Using the exponential generating function:
egf := exp(x)*BesselI(1, 2*x*t)/(x*t): ser:= series(egf, x, 11):
seq(print(seq(coeff(simplify(n!*coeff(ser, x, n)), t, k), k = 0..n)), n = 0..9);

Prog

(Python)
from functools import cache
@cache
def M(n: int, k: int) -> int:
    if k %  2: return 0
    if n <  3: return 1
    if n == k: return (2 * (n - 1) * M(n - 2, n - 2)) // (n // 2 + 1)
    return (M(n - 1, k) * n) // (n - k)
for n in range(10): print([M(n, k) for k in range(n + 1)])

Crossrefs

Variants: A055151, A080159, A097610, A107131.

Columns M(n, 2*k): A000012, A000217, A034827, A000910, A088625, A088626, A213380.

Cf. A001006 (Motzkin numbers), A026300 (Motzkin gf. triangle), A126120 (aerated Catalan), A000108 (Catalan).

Cf. A138364, A107587, A002457, A002522, A025179, A025235, A056107, A014531, A023426, A091147, A189912, A343386, A343773, A359647, A359649.

Sequence in context: A056100 A141665 A136689 * A073278 A359760 A081658

Adjacent sequences: A359361 A359362 A359363 * A359365 A359366 A359367

Keyword

nonn,tabl

Author

Peter Luschny, Jan 09 2023

Status

approved