A076026 Expansion of g.f.: (1-4*x*C)/(1-5*x*C) where C = (1/2-1/2*(1-4*x)^(1/2))/x = g.f. for Catalan numbers A000108.

1, 1, 6, 37, 230, 1434, 8952, 55917, 349374, 2183230, 13643972, 85270626, 532926716, 3330739972, 20816939100, 130105200765, 813155081070, 5082210417270, 31763782696740, 198523522444950, 1240771573465140, 7754820693127020, 48467623215477120, 302922622226091090

Offset

0,3

Comments

a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps at level 0 come in 6 colors and those at a higher level come in 2 colors. Example: a(4)=230 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have 6^3 = 216 paths of shape HHH, 6 paths of shape HUD, 6 paths of shape UDH, and 2 paths of shape UHD. - Emeric Deutsch, May 02 2011

References

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, Catalan-Spitzer permutations, arXiv:2310.06288 [math.CO], 2023. See p. 20.

Formula

a(n+1) = Sum_{k=0..n} A039598(n,k)*4^k. - Philippe Deléham, Mar 21 2007

a(n) = Sum_{k=0..n} A039599(n,k)*A015521(k), for n >= 1. - Philippe Deléham, Nov 22 2007

Let A be the Toeplitz matrix of order n defined by: A[i,i-1]=-1, A[i,j]=Catalan(j-i), (i<=j), and A[i,j]=0, otherwise. Then, for n >= 1, a(n+1)=(-1)^n*charpoly(A,-5). - Milan Janjic, Jul 08 2010

From Gary W. Adamson, Jul 25 2011: (Start)

a(n) = upper left term in M^(n-1), M = an infinite square production matrix as follows:

6, 1, 0, 0, 0, ...

1, 1, 1, 0, 0, ...

1, 1, 1, 1, 0, ...

1, 1, 1, 1, 1, ...

... (End)

D-finite with recurrence: 4*n*a(n) = (41*n-24)*a(n-1) - 50*(2*n-3)*a(n-2). - Vaclav Kotesovec, Dec 09 2013

a(n) ~ 3*5^(2*n-1)/4^(n+1). - Vaclav Kotesovec, Dec 09 2013

O.g.f. A(x) = (1 - *Sum_{n >= 1} binomial(2*n,n)*x^n)/(1 - (3/2)*Sum_{n >= 1} binomial(2*n,n)*x^n). - Peter Bala, Sep 01 2016

Mathematica

CoefficientList[Series[(2-4*Sqrt[1-4*x])/(3-5*Sqrt[1-4*x]), {x, 0, 30}], x] (* Vaclav Kotesovec, Dec 09 2013 *)
Flatten[{1, Table[FullSimplify[(2*n)!*Hypergeometric2F1Regularized[1, n+1/2, n+2, 16/25] / (25*n!) + 3*5^(2*n-1)/4^(n+1)], {n, 1, 30}]}] (* Vaclav Kotesovec, Dec 09 2013 *)

Prog

(PARI) my(x='x+O('x^30)); Vec((2-4*sqrt(1-4*x))/(3-5*sqrt(1-4*x))) \\ G. C. Greubel, May 04 2019
(Magma) R<x>:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( (2- 4*Sqrt(1-4*x))/(3-5*Sqrt(1-4*x)) )); // G. C. Greubel, May 04 2019
(Sage) ((2-4*sqrt(1-4*x))/(3-5*sqrt(1-4*x))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, May 04 2019

Crossrefs

Cf. A000108, A001700, A049027, A076025.

Sequence in context: A005668 A018904 A192807 * A161734 A081570 A122898

Adjacent sequences: A076023 A076024 A076025 * A076027 A076028 A076029

Keyword

nonn,easy

Author

N. J. A. Sloane, Oct 29 2002

Status

approved