A076026 - OEIS

%I #42 Oct 18 2023 12:22:20

%S 1,1,6,37,230,1434,8952,55917,349374,2183230,13643972,85270626,

%T 532926716,3330739972,20816939100,130105200765,813155081070,

%U 5082210417270,31763782696740,198523522444950,1240771573465140,7754820693127020,48467623215477120,302922622226091090

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

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

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

%H G. C. Greubel, <a href="/A076026/b076026.txt">Table of n, a(n) for n = 0..1000</a>

%H Richard Ehrenborg, Gábor Hetyei, and Margaret Readdy, <a href="https://arxiv.org/abs/2310.06288">Catalan-Spitzer permutations</a>, arXiv:2310.06288 [math.CO], 2023. See p. 20.

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

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

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

%F From _Gary W. Adamson_, Jul 25 2011: (Start)

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

%F   6, 1, 0, 0, 0, ...

%F   1, 1, 1, 0, 0, ...

%F   1, 1, 1, 1, 0, ...

%F   1, 1, 1, 1, 1, ...

%F   ... (End)

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

%F a(n) ~ 3*5^(2*n-1)/4^(n+1). - _Vaclav Kotesovec_, Dec 09 2013

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

%t CoefficientList[Series[(2-4*Sqrt[1-4*x])/(3-5*Sqrt[1-4*x]), {x, 0, 30}], x] (* _Vaclav Kotesovec_, Dec 09 2013 *)

%t 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 *)

%o (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

%o (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

%o (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

%Y Cf. A000108, A001700, A049027, A076025.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, Oct 29 2002