A344567 A(n, k) = [x^k] 2 / (1 - (2*n - 1)*x + sqrt(1 - 2*x - 3*x^2)). The number of n-colored Motzkin arcs of length k. Array read by ascending antidiagonals, n >= 0 and k >= 0.

1, 1, 0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 4, 3, 1, 4, 10, 13, 9, 6, 1, 5, 17, 34, 35, 21, 15, 1, 6, 26, 73, 117, 96, 51, 36, 1, 7, 37, 136, 315, 405, 267, 127, 91, 1, 8, 50, 229, 713, 1362, 1407, 750, 323, 232, 1, 9, 65, 358, 1419, 3741, 5895, 4899, 2123, 835, 603

Offset: 0

Author

Peter Luschny, May 24 2021

Keywords

• nonn
• tabl

Comments

Given a sequence a(n), we call the sequence b(n) Cameron's inverse of a, or, as dubbed by Sloane, INVERTi(a) (see the link 'Transforms' in the footer of the page), if 1 + Sum_{n>=1} a(n)*x^n = 1/(1 - Sum_{n>=1} b(n)*x^n).

Iterating this transform starting from A344506 we get:

a = A344506.

INVERTi(a) = A059738.

INVERTi(INVERTi(a)) = A005773.

INVERTi(INVERTi(INVERTi(a))) = A001006, Motzkin numbers.

INVERTi(INVERTi(INVERTi(INVERTi(a)))) = A005043.

INVERTi(INVERTi(INVERTi(INVERTi(INVERTi(a))))) = A344507.

The sequences generated in this manner correspond to the evaluation of the Motzkin polynomials (coefficients in A064189) at x = 3, 2, 1, 0, -1, -2. In terms of ordinary generating functions we have a ZZ-indexed sequence of sequences which general form is given by the formula in the name.

A "Motzkin path of length n and height k" is an integer lattice path from (0, 0) to (n, k) remaining weakly above the x-axis and consisting of steps in {U, L, D}. These acronyms stand for the steps Up = (1,1), Level = (1,0), and Down = (1, -1). An "n-colored Motzkin arc of length k" is a Motzkin path of length k and height 0 where each Level step of height 0 has one of n colors. A(n, k) is the number of n-colored Motzkin arcs of length k. The Motzkin numbers are M(k) = A(1, k).

Examples

			Array begins at n = 0, row for n = -1 added for illustration:
n\k  0   1    2     3      4       5        6         7  ... [Sequence Triangle]
--------------------------------------------------------------------------------
[-1] 1, -1,   2,   -2,     5,     -3,      15,        3, ...  [A344507]
[ 0] 1,  0,   1,    1,     3,      6,      15,       36, ...  [A005043, A089942]
[ 1] 1,  1,   2,    4,     9,     21,      51,      127, ...  [A001006, A064189]
[ 2] 1,  2,   5,   13,    35,     96,     267,      750, ...  [A005773, A038622]
[ 3] 1,  3,  10,   34,   117,    405,    1407,     4899, ...  [A059738, A126954]
[ 4] 1,  4,  17,   73,   315,   1362,    5895,    25528, ...  [A344506]
[ 5] 1,  5,  26,  136,   713,   3741,   19635,   103071, ...
[ 6] 1,  6,  37,  229,  1419,   8796,   54531,   338082, ...
[ 7] 1,  7,  50,  358,  2565,  18381,  131727,   944035, ...
[ 8] 1,  8,  65,  529,  4307,  35070,  285567,  2325324, ...
.
Triangle starts:
[0] 1;
[1] 1, 0;
[2] 1, 1,  1;
[3] 1, 2,  2,   1;
[4] 1, 3,  5,   4,   3;
[5] 1, 4, 10,  13,   9,    6;
[6] 1, 5, 17,  34,  35,   21,   15;
[7] 1, 6, 26,  73, 117,   96,   51,  36;
[8] 1, 7, 37, 136, 315,  405,  267, 127,  91;
[9] 1, 8, 50, 229, 713, 1362, 1407, 750, 323, 232.
.
Number of colors = 2, length = 4  ->  35.
.
      /\      _ _
     /  \    /   \   /\/\      3 x 1
.    _         _
    / \_     _/ \              2 x 2
.
    /\_ _   _ _/\   _/\_       3 x 4
.
    _ _ _ _                    1 x 16
.
Number of colors = 4, length = 2  ->  17.
.
    /\                         1 x 1
.
    _ _                        1 x 16
		

Links

• Martin Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675.
• F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discrete Mathematics, Vol. 204, No. 1-3 (1999), 73-112.
• Isaac DeJager, Madeleine Naquin, Frank Seidl, Paul Drube, Colored Motzkin Paths of Higher Order, Journal of Integer Sequences, Vol. 24 (2021)

Crossrefs

Cf. A064189, A097609, A344506, A059738, A005773, A001006, A005043, A344507.

Cf. triangles: A089942, A064189, A038622, A126954.

Programs

Maple

Arow := proc(n, len) option remember;
2 / (1 - (2*n - 1)*x + sqrt(1 - 2*x - 3*x^2));
seq(coeff(series(%, x, len+2), x, k), k = 0..len) end:
T := (n, k) -> Arow(n-k, k+1)[k+1]:
for n from 0 to 9 do Arow(n, 7) od; # prints array
for n from 0 to 9 do seq(T(n, k), k=0..n) od; # prints triangle
# Alternative via series reversion:
for n from -1 to 6 do  # print the array starting from n = -1
rgf := x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1):
subsop(1 = NULL, gfun:-seriestolist(series(rgf, x, 18), 'revogf')) od;
# Via recursively defined polynomials:
p := proc(n, k) option remember;
if n = k then 1 elif k < 0 or n < 0 or k > n then 0 elif k = 0 then x*p(n-1, 0) + p(n-1, 1) else p(n-1, k-1) + p(n-1, k) + p(n-1, k+1) fi end:
A := (n, k) -> subs(x = n, p(k, 0)):
for n from 0 to 8 do lprint(seq(A(n, k), k = 0..9)) od;
# Computing the columns:
Acol := proc(k, len) seq(subs(x = n, p(k, 0)), n = 0..len) end:
for k from 0 to 6 do Acol(k, 9) od;

Mathematica

Unprotect[Power]; 0^0 := 1;
A[n_, k_] := Sum[(n-1)^j Binomial[k, j] Hypergeometric2F1[(j - k)/2, (j - k + 1)/2, j + 2, 4], {j, 0, k}]; Table[A[n, k], {n, 0, 6}, {k, 0, 8}]

PARI

F(n) = {x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1)}
M(n,m=n) = {Mat(vectorv(n, i, Vec(serreverse(F(i-1) + O(x*x^m)))))}
{ my(A=M(8)); for(n=1, #A, print(A[n, ])) } \\ Andrew Howroyd, May 27 2021

SageMath

def Arow(n, len):
    R. = PowerSeriesRing(QQ, default_prec=len)
    f = x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1)
    return f.reverse().shift(-1).list()
for n in (0..8): print(Arow(n,10))

Formula

A(n, k) = Sum_{j=0..n} (k - 1)^j*binomial(n, j)*hypergeom([(j - n)/2, (j - n + 1)/2], [j + 2], 4).

Arow(n) = [x^n] reverse(x*((n-1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n-1)*x + 1)) / x.

Computationally more elementary is the following procedure: Let P_n(x) be polynomials defined recursively by P_n(x) = p(n, 0) where p(n, k) = 0 if k < 0 or n < 0 or k > n, p(n, n) = 1, p(n, 0) = x*p(n-1, 0) + p(n-1, 1), and in all other cases p(n, k) = p(n-1, k-1) + p(n-1, k) + p(n-1, k+1). Then A(n, k) = P_k(n).

The coefficients of these polynomials are in A097609. Thus the columns of the array can be calculated as: Acol(k) = [P_k(n) for n >= 0].