The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005572 Number of walks on cubic lattice starting and finishing on the xy plane and never going below it. (Formerly M3539) 24
 1, 4, 17, 76, 354, 1704, 8421, 42508, 218318, 1137400, 5996938, 31940792, 171605956, 928931280, 5061593709, 27739833228, 152809506582, 845646470616, 4699126915422, 26209721959656, 146681521121244, 823429928805936 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS Also number of paths from (0,0) to (n,0) in an n X n grid using only Northeast, East and Southeast steps and the East steps come in four colors. - Emeric Deutsch, Nov 03 2002 Number of skew Dyck paths of semilength n+1 with the left steps coming in two colors. - David Scambler, Jun 21 2013 Number of 2-colored Schroeder paths from (0,0) to (2n+2,0) with no level steps H=(2,0) at an even level. There are two ways to color an H-step at an odd level.  Example: a(1)=4 because we have UUDD, UHD (2 choices) and UDUD. - José Luis Ramírez Ramírez, Apr 27 2015 REFERENCES N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS T. D. Noe, Table of n, a(n) for n = 0..200 R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449 [cs.DM], 2013. Y. Cha, Closed form solutions of difference equations (2011) PhD Thesis, Florida State University, eample 5.1.2 Isaac DeJager, Madeleine Naquin, Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019. Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5. Rigoberto Flórez, Leandro Junes, José L. Ramírez, Further Results on Paths in an n-Dimensional Cubic Lattice, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.2. R. K. Guy, Letter to N. J. A. Sloane, May 1990 R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6. P.-Y. Huang, S.-C. Liu, Y.-N. Yeh, Congruences of Finite Summations of the Coefficients in certain Generating Functions, The Electronic Journal of Combinatorics, 21 (2014), #P2.45. INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 153 J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5. Lily L. Liu, Positivity of three-term recurrence sequences, Electronic J. Combinatorics, 17 (2010), #R57. Rui-Li Liu, Feng-Zhen Zhao, New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences, J. Int. Seq., Vol. 21 (2018), Article 18.5.7. N. J. A. Sloane, Transforms R. A. Sulanke, Moments of generalized Motzkin paths, J. Integer Sequences, Vol. 3 (2000), #00.1. E. X. W. Xia and O. X. M. Yao, A Criterion for the Log-Convexity of Combinatorial Sequences, The Electronic Journal of Combinatorics, 20 (2013), #P3. FORMULA Generating function A(x) satisfies 1 + (xA)^2 = A - 4xA. a(0) = 1 and, for n > 0, a(n) = 4a(n-1) + Sum_{i=1..n-1} a(i-1)*a(n-i-1). - John W. Layman, Jan 07 2000 G.f.: (1 - 4*x - sqrt(1 - 8*x + 12*x^2))/(2*x^2). D-finite with recurrence: a(n) = ((2*n+1)*a(n-1) - 3*(n-1)*a(n-2))*4/(n+2), n > 0. a(m+n) = Sum_{k>=0} A052179(m, k)*A052179(n, k) = A052179(m+n, 0). - Philippe Deléham, Sep 15 2005 a(n) = 4a(n-1) + A052177(n-1) = A052179(n, 0) = 6*A005573(n)-A005573(n-1) = Sum_{j=0..floor(n/2)}(4^(n-2j)*C(n, 2j)*C(2j, j)/(j+1))). - Henry Bottomley, Aug 23 2001 a(n) = Sum_{k=0..n} A097610(n,k)*4^k. - Philippe Deléham, Dec 03 2009 Let A(x) be the g.f., then B(x) = 1 + x*A(x) = 1 + 1*x + 4*x^2 + 17*x^3 + ... = 1/(1-z/(1-z/(1-z/(...)))) where z=x/(1-2*x) (continued fraction); more generally B(x) = C(x/(1-2*x)) where C(x) is the g.f. for the Catalan numbers (A000108). - Joerg Arndt, Mar 18 2011 From Gary W. Adamson, Jul 21 2011: (Start) a(n) = sum of top row terms of M^n, M = an infinite square production matrix as follows:   3, 1, 0, 0, ...   1, 3, 1, 0, ...   1, 1, 3, 1, ...   1, 1, 1, 3, ...   ... (End) a(n) ~ 3*6^(n+1/2)/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Oct 05 2012 a(n) = Sum_{k=0..floor(n/2)} binomial(n,2*k) * binomial(2k,k) * 4^(n-2k) / (k+1). - Max Alekseyev, Feb 02 2015 From Paul D. Hanna, Feb 02 2015: (Start) a(n) = Sum_{k=0..n} binomial(n,k) * 2^(n-k) * binomial(2*k+2, k)/(k+1). a(n) = Sum_{k=0..n} binomial(n,k) * 2^(n-k) * A000108(k+1). a(n) = [x^n] (1 + 4*x + x^2)^(n+1) / (n+1). G.f.: (1/x) * Series_Reversion( x/(1 + 4*x + x^2) ). (End) a(n) = 2^n*hypergeom([3/2, -n], , -2). - Peter Luschny, Feb 03 2015 a(n) = 4^n*hypergeom([-n/2, (1-n)/2], , 1/4). - Robert Israel, Feb 04 2015 a(n) = Sum_{k=0..n} A108198(n,k)*2^(n-k). - Peter Luschny, Feb 05 2015 a(n) = 2*(12^(n/2))*(n!/(n+2)!)*GegenbauerC(n, 3/2,2/sqrt(3)), where GegenbauerC are Gegenbauer polynomials in Maple notation. This is a consequence of Robert Israel's formula. - Karol A. Penson, Feb 20 2015 a(n) = (2^(n+1)*3^((n+1)/2)*P(n+1,1,2/sqrt(3)))/((n+1)*(n+2)) where P(n,u,x) are the associated Legendre polynomials of the first kind. - Peter Luschny, Feb 24 2015 a(n) = -6^(n+1)*sqrt(3)*Integral{t=0..Pi}(cos(t)*(2+cos(t))^(-n-2))/(Pi*(n+2)). - Peter Luschny, Feb 24 2015 From Karol A. Penson and Wojciech Mlotkowski, Mar 16 2015: (Start) Integral representation as the n-th moment of a positive function defined on a segment x=[2, 6]. This function is the Wigner's semicircle distribution shifted to the right by 4. This representation is unique. In Maple notation, a(n) = int(x^n*sqrt(4-(x-4)^2)/(2*Pi), x=2..6), a(n) = 2*6^n*pochhammer(3/2, n)*hypergeom([-n, 3/2], [-n-1/2], 1/3)/(n+2)! (End) a(n) = GegenbauerC(n, -n-1, -2)/(n+1). - Peter Luschny, May 09 2016 E.g.f.: exp(4*x) * BesselI(1,2*x) / x. - Ilya Gutkovskiy, Jun 01 2020 EXAMPLE a(3) = 76 = sum of top row terms of M^3; i.e., (37 + 29 + 9 + 1). MAPLE a := n -> simplify(2^n*hypergeom([3/2, -n], , -2)): seq(a(n), n=0..21); # Peter Luschny, Feb 03 2015 a := n -> simplify(GegenbauerC(n, -n-1, -2))/(n+1): seq(a(n), n=0..21); # Peter Luschny, May 09 2016 MATHEMATICA RecurrenceTable[{a==1, a==4, a[n]==((2n+1)a[n-1]-3(n-1)a[n-2]) 4/(n+2)}, a[n], {n, 30}] (* Harvey P. Dale, Oct 04 2011 *) a[n_]:=If[n==0, 1, Coefficient[(1+4x+x^2)^(n+1), x^n]/(n+1)] Table[a[n], {n, 0, 40}] (* Emanuele Munarini, Apr 06 2012 *) PROG (PARI) a(n)=polcoeff((1-4*x-sqrt(1-8*x+12*x^2+x^3*O(x^n)))/2, n+2) (PARI) { A005572(n) = sum(k=0, n\2, binomial(n, 2*k) * binomial(2*k, k) * 4^(n-2*k) / (k+1) ) } /* Max Alekseyev, Feb 02 2015 */ (PARI) {a(n)=sum(k=0, n, binomial(n, k) * 2^(n-k) * binomial(2*k+2, k)/(k+1) )} for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Feb 02 2015 (Maxima) a(n):=coeff(expand((1+4*x+x^2)^(n+1)), x^n)/(n+1); makelist(a(n), n, 0, 12); /* Emanuele Munarini, Apr 06 2012 */ (Sage) def A005572(n):     A108198 = lambda n, k: (-1)^k*catalan_number(k+1)*rising_factorial(-n, k)/factorial(k)     return sum(A108198(n, k)*2^(n-k) for k in (0..n)) [A005572(n) for n in range(22)] # Peter Luschny, Feb 05 2015 CROSSREFS Binomial transform of A002212. Sequence shifted right twice is A025228. Cf. A001006, A108198. Sequence in context: A026773 A081186 A239204 * A202879 A333059 A081922 Adjacent sequences:  A005569 A005570 A005571 * A005573 A005574 A005575 KEYWORD nonn,walk,easy,nice AUTHOR EXTENSIONS Additional comments from Michael Somos, Jun 10 2000 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 11 09:11 EDT 2021. Contains 343788 sequences. (Running on oeis4.)