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
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).
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
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Jan 09 2023
STATUS
approved