|
| |
|
|
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, 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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
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:
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).
|
|
|
LINKS
|
|
|
|
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].
|
|
|
EXAMPLE
|
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]
[ 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
|
|
|
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}]
|
|
|
PROG
|
(SageMath)
def Arow(n, len):
R.<x> = 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))
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
