cp's OEIS Frontend

A005572 Number of walks on cubic lattice starting and finishing on the xy plane and never going below it.

%I A005572 M3539 #204 Jan 19 2025 14:42:45
%S A005572 1,4,17,76,354,1704,8421,42508,218318,1137400,5996938,31940792,
%T A005572 171605956,928931280,5061593709,27739833228,152809506582,845646470616,
%U A005572 4699126915422,26209721959656,146681521121244,823429928805936
%N A005572 Number of walks on cubic lattice starting and finishing on the xy plane and never going below it.
%C A005572 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
%C A005572 Number of skew Dyck paths of semilength n+1 with the left steps coming in two colors. - _David Scambler_, Jun 21 2013
%C A005572 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
%D A005572 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005572 T. D. Noe, <a href="/A005572/b005572.txt">Table of n, a(n) for n = 0..200</a>
%H A005572 Rodrigo De Castro, Andrés Ramírez, and José L. Ramírez, <a href="http://arxiv.org/abs/1310.2449">Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs</a>, arXiv preprint arXiv:1310.2449 [cs.DM], 2013. See also <a href="https://doi.org/10.7561/SACS.2014.1.137">Sci. Annals Comp. Sci.</a> (2014) Vol. XXIV, Issue 1, 137-171. See p. 157.
%H A005572 Y. Cha, <a href="https://www.math.fsu.edu/~hoeij/papers/J/Cha_Y_Dissertation_2011.pdf">Closed form solutions of difference equations</a>, (2011) PhD Thesis, Florida State University, example 5.1.2.
%H A005572 Isaac DeJager, Madeleine Naquin and Frank Seidl, <a href="https://www.valpo.edu/mathematics-statistics/files/2019/08/Drube2019.pdf">Colored Motzkin Paths of Higher Order</a>, VERUM 2019.
%H A005572 Nachum Dershowitz, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Dershowitz/dersh3.html">Touchard's Drunkard</a>, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.
%H A005572 Rigoberto Flórez, Leandro Junes and José L. Ramírez, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Florez/florez4.html">Further Results on Paths in an n-Dimensional Cubic Lattice</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.2.
%H A005572 R. K. Guy, <a href="/A005555/a005555.pdf">Letter to N. J. A. Sloane, May 1990</a>
%H A005572 R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
%H A005572 P.-Y. Huang, S.-C. Liu and Y.-N. Yeh, <a href="https://doi.org/10.37236/3693">Congruences of Finite Summations of the Coefficients in certain Generating Functions</a>, The Electronic Journal of Combinatorics, 21 (2014), #P2.45.
%H A005572 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=153">Encyclopedia of Combinatorial Structures 153</a>
%H A005572 J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.
%H A005572 Lily L. Liu, <a href="https://doi.org/10.37236/329">Positivity of three-term recurrence sequences</a>, Electronic J. Combinatorics, 17 (2010), #R57.
%H A005572 Rui-Li Liu and Feng-Zhen Zhao, <a href="https://www.emis.de/journals/JIS/VOL21/Liu/liu19.html">New Sufficient Conditions for Log-Balancedness, With Applications to Combinatorial Sequences</a>, J. Int. Seq., Vol. 21 (2018), Article 18.5.7.
%H A005572 N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H A005572 R. A. Sulanke, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/SULANKE/sulanke.html">Moments of generalized Motzkin paths</a>, J. Integer Sequences, Vol. 3 (2000), #00.1.
%H A005572 Paveł Szabłowski, <a href="https://cdm.ucalgary.ca/article/view/76214">Beta distributions whose moment sequences are related to integer sequences listed in the OEIS</a>, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.
%H A005572 E. X. W. Xia and O. X. M. Yao, <a href="https://doi.org/10.37236/3412">A Criterion for the Log-Convexity of Combinatorial Sequences</a>, The Electronic Journal of Combinatorics, 20 (2013), #P3.
%F A005572 Generating function A(x) satisfies 1 + (xA)^2 = A - 4xA.
%F A005572 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
%F A005572 G.f.: (1 - 4*x - sqrt(1 - 8*x + 12*x^2))/(2*x^2).
%F A005572 D-finite with recurrence: a(n) = ((2*n+1)*a(n-1) - 3*(n-1)*a(n-2))*4/(n+2), n > 0.
%F A005572 a(m+n) = Sum_{k>=0} A052179(m, k)*A052179(n, k) = A052179(m+n, 0). - _Philippe Deléham_, Sep 15 2005
%F A005572 a(n) = 4*a(n-1) + A052177(n-1) = A052179(n, 0) = 6*A005573(n)-A005573(n-1) = Sum_{j=0..floor(n/2)} 4^(n-2*j)*C(n, 2*j)*C(2*j, j)/(j+1). - _Henry Bottomley_, Aug 23 2001
%F A005572 a(n) = Sum_{k=0..n} A097610(n,k)*4^k. - _Philippe Deléham_, Dec 03 2009
%F A005572 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
%F A005572 From _Gary W. Adamson_, Jul 21 2011: (Start)
%F A005572 a(n) = sum of top row terms of M^n, M = an infinite square production matrix as follows:
%F A005572   3, 1, 0, 0, ...
%F A005572   1, 3, 1, 0, ...
%F A005572   1, 1, 3, 1, ...
%F A005572   1, 1, 1, 3, ...
%F A005572   ... (End)
%F A005572 a(n) ~ 3*6^(n+1/2)/(n^(3/2)*sqrt(Pi)). - _Vaclav Kotesovec_, Oct 05 2012
%F A005572 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
%F A005572 From _Paul D. Hanna_, Feb 02 2015: (Start)
%F A005572 a(n) = Sum_{k=0..n} binomial(n,k) * 2^(n-k) * binomial(2*k+2, k)/(k+1).
%F A005572 a(n) = Sum_{k=0..n} binomial(n,k) * 2^(n-k) * A000108(k+1).
%F A005572 a(n) = [x^n] (1 + 4*x + x^2)^(n+1) / (n+1).
%F A005572 G.f.: (1/x) * Series_Reversion( x/(1 + 4*x + x^2) ). (End)
%F A005572 a(n) = 2^n*hypergeom([3/2, -n], [3], -2). - _Peter Luschny_, Feb 03 2015
%F A005572 a(n) = 4^n*hypergeom([-n/2, (1-n)/2], [2], 1/4). - _Robert Israel_, Feb 04 2015
%F A005572 a(n) = Sum_{k=0..n} A108198(n,k)*2^(n-k). - _Peter Luschny_, Feb 05 2015
%F A005572 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
%F A005572 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
%F A005572 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
%F A005572 From _Karol A. Penson_ and Wojciech Mlotkowski, Mar 16 2015: (Start)
%F A005572 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,
%F A005572 a(n) = int(x^n*sqrt(4-(x-4)^2)/(2*Pi), x=2..6),
%F A005572 a(n) = 2*6^n*Pochhammer(3/2, n)*hypergeom([-n, 3/2], [-n-1/2], 1/3)/(n+2)!
%F A005572 (End)
%F A005572 a(n) = GegenbauerC(n, -n-1, -2)/(n+1). - _Peter Luschny_, May 09 2016
%F A005572 E.g.f.: exp(4*x) * BesselI(1,2*x) / x. - _Ilya Gutkovskiy_, Jun 01 2020
%F A005572 From _Peter Bala_, Aug 18 2021: (Start)
%F A005572 G.f. A(x) = 1/(1 - 2*x)*c(x/(1 - 2*x))^2, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. Cf. A129400.
%F A005572 Conjecture: a(n) is even except for n of the form 2*(2^k - 1). [added Feb 03: the conjecture follows from the formula a(n) = Sum_{k = 0..n} 2^(n-k)*binomial(n, k)*Catalan(k+1) given above.] (End)
%F A005572 From _Peter Bala_, Feb 03 2024: (Start)
%F A005572 G.f.: 1/(1 - 2*x) * c(x/(1 - 2*x))^2 = 1/(1 - 6*x) * c(-x/(1 - 6*x))^2, where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108.
%F A005572 a(n) = 6^n * Sum_{k = 0..n} (-6)^(-k)*binomial(n, k)*Catalan(k+1).
%F A005572 a(n) = 6^n * hypergeom([-n, 3/2], [3], 2/3). (End)
%e A005572 a(3) = 76 = sum of top row terms of M^3; i.e., (37 + 29 + 9 + 1).
%p A005572 a := n -> simplify(2^n*hypergeom([3/2, -n], [3], -2)):
%p A005572 seq(a(n), n=0..21); # _Peter Luschny_, Feb 03 2015
%p A005572 a := n -> simplify(GegenbauerC(n, -n-1, -2))/(n+1):
%p A005572 seq(a(n), n=0..21); # _Peter Luschny_, May 09 2016
%t A005572 RecurrenceTable[{a[0]==1,a[1]==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 *)
%t A005572 a[n_]:=If[n==0,1,Coefficient[(1+4x+x^2)^(n+1),x^n]/(n+1)]
%t A005572 Table[a[n],{n,0,40}] (* _Emanuele Munarini_, Apr 06 2012 *)
%o A005572 (PARI) a(n)=polcoeff((1-4*x-sqrt(1-8*x+12*x^2+x^3*O(x^n)))/2,n+2)
%o A005572 (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 */
%o A005572 (PARI) {a(n)=sum(k=0,n, binomial(n,k) * 2^(n-k) * binomial(2*k+2, k)/(k+1) )}
%o A005572 for(n=0,30,print1(a(n),", ")) \\ _Paul D. Hanna_, Feb 02 2015
%o A005572 (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 */
%o A005572 (Sage)
%o A005572 def A005572(n):
%o A005572     A108198 = lambda n,k: (-1)^k*catalan_number(k+1)*rising_factorial(-n,k)/factorial(k)
%o A005572     return sum(A108198(n,k)*2^(n-k) for k in (0..n))
%o A005572 [A005572(n) for n in range(22)] # _Peter Luschny_, Feb 05 2015
%Y A005572 Binomial transform of A002212. Sequence shifted right twice is A025228.
%Y A005572 Cf. A001006, A025228, A025230, A108198, A129400, A182401.
%K A005572 nonn,walk,easy,nice
%O A005572 0,2
%A A005572 _N. J. A. Sloane_
%E A005572 Additional comments from _Michael Somos_, Jun 10 2000