A005573 Number of walks on cubic lattice (starting from origin and not going below xy plane). (Formerly M3943)

1, 5, 26, 139, 758, 4194, 23460, 132339, 751526, 4290838, 24607628, 141648830, 817952188, 4736107172, 27487711752, 159864676803, 931448227590, 5435879858958, 31769632683132, 185918669183370, 1089302293140564

Offset

0,2

Comments

Binomial transform of A026378, second binomial transform of A001700. - Philippe Deléham, Jan 28 2007

The Hankel transform of [1,1,5,26,139,758,...] is [1,4,15,56,209,...](see A001353). - Philippe Deléham, Apr 13 2007

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Isaac DeJager, Madeleine Naquin, Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.

E. Deutsch et al., Problem 10795: Three-Dimensional Lattice Walks in the Upper Half-Space, Amer. Math. Monthly, 108 (Dec. 2001), 980.

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 Seqs., Vol. 3 (2000), #00.1.6.

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

Formula

From Emeric Deutsch, Jan 09 2003; corrected by Roland Bacher: (Start)

a(n) = Sum_{i=0..n} (-1)^i*6^(n-i)*binomial(n, i)*binomial(2*i, i)/(i+1);

g.f. A(x) satisfies: x(1-6x)A^2 + (1-6x)A - 1 = 0. (End)

From Henry Bottomley, Aug 23 2001: (Start)

a(n) = 6*a(n-1) - A005572(n-1).

a(n) = Sum_{j=0..n} 4^(n-j)*binomial(n, floor(n/2))*binomial(n, j). (End)

a(n) = Sum_{k=0..n} binomial(n, k)*binomial(2*k+1, k)*2^(n-k).

a(n) = Sum_{k=0..n} (-1)^k*binomial(n, k)*Catalan(k)*6^(n-k).

D-finite with recurrence (n+1)*a(n) = (8*n+2)*a(n-1)-(12*n-12)*a(n-2). - Vladeta Jovovic, Jul 16 2004

a(n) = Sum_{k=0..n} A052179(n,k). - Philippe Deléham, Jan 28 2007

Conjecture: a(n)= 6^n * hypergeom([1/2,-n],[2], 2/3). - Benjamin Phillabaum, Feb 20 2011

From Paul Barry, Apr 21 2009: (Start)

G.f.: (sqrt((1-2*x)/(1-6*x)) - 1)/(2*x).

G.f.: 1/(1-5*x-x^2/(1-4*x-x^2/(1-4*x-x^2/(1-4*x-x^2/(1-... (continued fraction). (End)

G.f.: 1/(1 - 4*x - x*(1 - 2*x)/(1 - 2*x - x*(1 - 2*x)/(1 - 2*x - x*(1 - 2*x)/(1 - 2*x - x*(1 - 2*x)/(1...(continued fraction). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Jul 02 2010

a(n) ~ 6^(n+1/2)/sqrt(Pi*n). - Vaclav Kotesovec, Oct 05 2012

G.f.: G(0)/(2*x) - 1/(2*x), where G(k)= 1 + 4*x*(4*k+1)/( (4*k+2)*(1-2*x) - 2*x*(1-2*x)*(2*k+1)*(4*k+3)/(x*(4*k+3) + (1-2*x)*(k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 24 2013

a(n) = 2^n*hypergeom([-n, 3/2], [2], -2). - Peter Luschny, Apr 26 2016

E.g.f.: exp(4*x)*(BesselI(0,2*x) + BesselI(1,2*x)). - Ilya Gutkovskiy, Sep 20 2017

Mathematica

CoefficientList[Series[(Sqrt[(1-2x)/(1-6x)]-1)/(2x), {x, 0, 20}], x] (* Harvey P. Dale, Jun 24 2011 *)
a[n_] := 6^n Hypergeometric2F1[1/2, -n, 2, 2/3]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Apr 11 2017 *)

Prog

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

Crossrefs

Sequence in context: A049607 A035029 A081569 * A081911 A081187 A182401

Adjacent sequences: A005570 A005571 A005572 * A005574 A005575 A005576

Keyword

nonn,walk,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Henry Bottomley, Aug 23 2001

Status

approved