cp's OEIS Frontend

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.

%I A344567 #33 May 27 2021 10:43:24
%S A344567 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 A344567 26,73,117,96,51,36,1,7,37,136,315,405,267,127,91,1,8,50,229,713,1362,
%U A344567 1407,750,323,232,1,9,65,358,1419,3741,5895,4899,2123,835,603
%N 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.
%C A344567 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 A344567 Iterating this transform starting from A344506 we get:
%C A344567   a = A344506.
%C A344567   INVERTi(a) = A059738.
%C A344567   INVERTi(INVERTi(a)) = A005773.
%C A344567   INVERTi(INVERTi(INVERTi(a))) = A001006, Motzkin numbers.
%C A344567   INVERTi(INVERTi(INVERTi(INVERTi(a)))) = A005043.
%C A344567   INVERTi(INVERTi(INVERTi(INVERTi(INVERTi(a))))) = A344507.
%C A344567 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 A344567 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 A344567 Martin Aigner, <a href="https://dx.doi.org/10.1006/eujc.1998.0235">Motzkin Numbers</a>, Europ. J. Comb. 19 (1998), 663-675.
%H A344567 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 A344567 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 A344567 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 A344567 Arow(n) = [x^n] reverse(x*((n-1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n-1)*x + 1)) / x.
%F A344567 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 A344567 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 A344567 Array begins at n = 0, row for n = -1 added for illustration:
%e A344567 n\k  0   1    2     3      4       5        6         7  ... [Sequence Triangle]
%e A344567 --------------------------------------------------------------------------------
%e A344567 [-1] 1, -1,   2,   -2,     5,     -3,      15,        3, ...  [A344507]
%e A344567 [ 0] 1,  0,   1,    1,     3,      6,      15,       36, ...  [A005043, A089942]
%e A344567 [ 1] 1,  1,   2,    4,     9,     21,      51,      127, ...  [A001006, A064189]
%e A344567 [ 2] 1,  2,   5,   13,    35,     96,     267,      750, ...  [A005773, A038622]
%e A344567 [ 3] 1,  3,  10,   34,   117,    405,    1407,     4899, ...  [A059738, A126954]
%e A344567 [ 4] 1,  4,  17,   73,   315,   1362,    5895,    25528, ...  [A344506]
%e A344567 [ 5] 1,  5,  26,  136,   713,   3741,   19635,   103071, ...
%e A344567 [ 6] 1,  6,  37,  229,  1419,   8796,   54531,   338082, ...
%e A344567 [ 7] 1,  7,  50,  358,  2565,  18381,  131727,   944035, ...
%e A344567 [ 8] 1,  8,  65,  529,  4307,  35070,  285567,  2325324, ...
%e A344567 .
%e A344567 Triangle starts:
%e A344567 [0] 1;
%e A344567 [1] 1, 0;
%e A344567 [2] 1, 1,  1;
%e A344567 [3] 1, 2,  2,   1;
%e A344567 [4] 1, 3,  5,   4,   3;
%e A344567 [5] 1, 4, 10,  13,   9,    6;
%e A344567 [6] 1, 5, 17,  34,  35,   21,   15;
%e A344567 [7] 1, 6, 26,  73, 117,   96,   51,  36;
%e A344567 [8] 1, 7, 37, 136, 315,  405,  267, 127,  91;
%e A344567 [9] 1, 8, 50, 229, 713, 1362, 1407, 750, 323, 232.
%e A344567 .
%e A344567 Number of colors = 2, length = 4  ->  35.
%e A344567 .
%e A344567       /\      _ _
%e A344567      /  \    /   \   /\/\      3 x 1
%e A344567 .    _         _
%e A344567     / \_     _/ \              2 x 2
%e A344567 .
%e A344567     /\_ _   _ _/\   _/\_       3 x 4
%e A344567 .
%e A344567     _ _ _ _                    1 x 16
%e A344567 .
%e A344567 Number of colors = 4, length = 2  ->  17.
%e A344567 .
%e A344567     /\                         1 x 1
%e A344567 .
%e A344567     _ _                        1 x 16
%p A344567 Arow := proc(n, len) option remember;
%p A344567 2 / (1 - (2*n - 1)*x + sqrt(1 - 2*x - 3*x^2));
%p A344567 seq(coeff(series(%, x, len+2), x, k), k = 0..len) end:
%p A344567 T := (n, k) -> Arow(n-k, k+1)[k+1]:
%p A344567 for n from 0 to 9 do Arow(n, 7) od; # prints array
%p A344567 for n from 0 to 9 do seq(T(n, k), k=0..n) od; # prints triangle
%p A344567 # Alternative via series reversion:
%p A344567 for n from -1 to 6 do  # print the array starting from n = -1
%p A344567 rgf := x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1):
%p A344567 subsop(1 = NULL, gfun:-seriestolist(series(rgf, x, 18), 'revogf')) od;
%p A344567 # Via recursively defined polynomials:
%p A344567 p := proc(n, k) option remember;
%p A344567 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 A344567 A := (n, k) -> subs(x = n, p(k, 0)):
%p A344567 for n from 0 to 8 do lprint(seq(A(n, k), k = 0..9)) od;
%p A344567 # Computing the columns:
%p A344567 Acol := proc(k, len) seq(subs(x = n, p(k, 0)), n = 0..len) end:
%p A344567 for k from 0 to 6 do Acol(k, 9) od;
%t A344567 Unprotect[Power]; 0^0 := 1;
%t A344567 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 A344567 (SageMath)
%o A344567 def Arow(n, len):
%o A344567     R.<x> = PowerSeriesRing(QQ, default_prec=len)
%o A344567     f = x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1)
%o A344567     return f.reverse().shift(-1).list()
%o A344567 for n in (0..8): print(Arow(n,10))
%o A344567 (PARI)
%o A344567 F(n) = {x*((n - 1)*x + 1) / ((n^2 - n + 1)*x^2 + (2*n - 1)*x + 1)}
%o A344567 M(n,m=n) = {Mat(vectorv(n, i, Vec(serreverse(F(i-1) + O(x*x^m)))))}
%o A344567 { my(A=M(8)); for(n=1, #A, print(A[n, ])) } \\ _Andrew Howroyd_, May 27 2021
%Y A344567 Cf. A064189, A097609, A344506, A059738, A005773, A001006, A005043, A344507.
%Y A344567 Cf. triangles: A089942, A064189, A038622, A126954.
%K A344567 nonn,tabl
%O A344567 0,8
%A A344567 _Peter Luschny_, May 24 2021