login
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

%I #33 May 27 2021 10:43:24

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

%T 26,73,117,96,51,36,1,7,37,136,315,405,267,127,91,1,8,50,229,713,1362,

%U 1407,750,323,232,1,9,65,358,1419,3741,5895,4899,2123,835,603

%N 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.

%C 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).

%C Iterating this transform starting from A344506 we get:

%C a = A344506.

%C INVERTi(a) = A059738.

%C INVERTi(INVERTi(a)) = A005773.

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

%C INVERTi(INVERTi(INVERTi(INVERTi(a)))) = A005043.

%C INVERTi(INVERTi(INVERTi(INVERTi(INVERTi(a))))) = A344507.

%C 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.

%C 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).

%H Martin Aigner, <a href="https://dx.doi.org/10.1006/eujc.1998.0235">Motzkin Numbers</a>, Europ. J. Comb. 19 (1998), 663-675.

%H F. R. Bernhart, <a href="https://doi.org/10.1016/S0012-365X(99)00054-0">Catalan, Motzkin and Riordan numbers</a>, Discrete Mathematics, Vol. 204, No. 1-3 (1999), 73-112.

%H Isaac DeJager, Madeleine Naquin, Frank Seidl, Paul Drube, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Drube/drube7.html">Colored Motzkin Paths of Higher Order</a>, Journal of Integer Sequences, Vol. 24 (2021)

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

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

%F 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).

%F 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].

%e Array begins at n = 0, row for n = -1 added for illustration:

%e n\k 0 1 2 3 4 5 6 7 ... [Sequence Triangle]

%e --------------------------------------------------------------------------------

%e [-1] 1, -1, 2, -2, 5, -3, 15, 3, ... [A344507]

%e [ 0] 1, 0, 1, 1, 3, 6, 15, 36, ... [A005043, A089942]

%e [ 1] 1, 1, 2, 4, 9, 21, 51, 127, ... [A001006, A064189]

%e [ 2] 1, 2, 5, 13, 35, 96, 267, 750, ... [A005773, A038622]

%e [ 3] 1, 3, 10, 34, 117, 405, 1407, 4899, ... [A059738, A126954]

%e [ 4] 1, 4, 17, 73, 315, 1362, 5895, 25528, ... [A344506]

%e [ 5] 1, 5, 26, 136, 713, 3741, 19635, 103071, ...

%e [ 6] 1, 6, 37, 229, 1419, 8796, 54531, 338082, ...

%e [ 7] 1, 7, 50, 358, 2565, 18381, 131727, 944035, ...

%e [ 8] 1, 8, 65, 529, 4307, 35070, 285567, 2325324, ...

%e .

%e Triangle starts:

%e [0] 1;

%e [1] 1, 0;

%e [2] 1, 1, 1;

%e [3] 1, 2, 2, 1;

%e [4] 1, 3, 5, 4, 3;

%e [5] 1, 4, 10, 13, 9, 6;

%e [6] 1, 5, 17, 34, 35, 21, 15;

%e [7] 1, 6, 26, 73, 117, 96, 51, 36;

%e [8] 1, 7, 37, 136, 315, 405, 267, 127, 91;

%e [9] 1, 8, 50, 229, 713, 1362, 1407, 750, 323, 232.

%e .

%e Number of colors = 2, length = 4 -> 35.

%e .

%e /\ _ _

%e / \ / \ /\/\ 3 x 1

%e . _ _

%e / \_ _/ \ 2 x 2

%e .

%e /\_ _ _ _/\ _/\_ 3 x 4

%e .

%e _ _ _ _ 1 x 16

%e .

%e Number of colors = 4, length = 2 -> 17.

%e .

%e /\ 1 x 1

%e .

%e _ _ 1 x 16

%p Arow := proc(n, len) option remember;

%p 2 / (1 - (2*n - 1)*x + sqrt(1 - 2*x - 3*x^2));

%p seq(coeff(series(%, x, len+2), x, k), k = 0..len) end:

%p T := (n, k) -> Arow(n-k, k+1)[k+1]:

%p for n from 0 to 9 do Arow(n, 7) od; # prints array

%p for n from 0 to 9 do seq(T(n, k), k=0..n) od; # prints triangle

%p # Alternative via series reversion:

%p for n from -1 to 6 do # print the array starting from n = -1

%p rgf := x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1):

%p subsop(1 = NULL, gfun:-seriestolist(series(rgf, x, 18), 'revogf')) od;

%p # Via recursively defined polynomials:

%p p := proc(n, k) option remember;

%p 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:

%p A := (n, k) -> subs(x = n, p(k, 0)):

%p for n from 0 to 8 do lprint(seq(A(n, k), k = 0..9)) od;

%p # Computing the columns:

%p Acol := proc(k, len) seq(subs(x = n, p(k, 0)), n = 0..len) end:

%p for k from 0 to 6 do Acol(k, 9) od;

%t Unprotect[Power]; 0^0 := 1;

%t 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}]

%o (SageMath)

%o def Arow(n, len):

%o R.<x> = PowerSeriesRing(QQ, default_prec=len)

%o f = x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1)

%o return f.reverse().shift(-1).list()

%o for n in (0..8): print(Arow(n,10))

%o (PARI)

%o F(n) = {x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1)}

%o M(n,m=n) = {Mat(vectorv(n, i, Vec(serreverse(F(i-1) + O(x*x^m)))))}

%o { my(A=M(8)); for(n=1, #A, print(A[n, ])) } \\ _Andrew Howroyd_, May 27 2021

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

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

%K nonn,tabl

%O 0,8

%A _Peter Luschny_, May 24 2021