A064036 Number of walks of length n on cubic lattice, starting at origin, staying in first (nonnegative) octant.

1, 3, 12, 51, 234, 1110, 5460, 27405, 140490, 729918, 3845016, 20447658, 109801692, 593806356, 3234529584, 17715445605, 97567971930, 539701180590, 2998595422680, 16719506691030, 93559970043540, 525093580540620, 2955822168597480, 16680150247605390, 94365481922990460

Offset

0,2

Links

Robert Israel, Table of n, a(n) for n = 0..500

R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6.

Formula

a(n) = sum_j[C(n, j)B(j)B(j+1)B(n-j)] where B(k)=C(k, [k/2])=A001405(k)

E.g.f.: (BesselI(0, 2*x)+BesselI(1, 2*x))^3. - Vladeta Jovovic, Apr 28 2003

From Vaclav Kotesovec, Jun 10 2019: (Start)

Recurrence: (n+1)*(n+2)*(n+3)*a(n) = 4*(5*n^2+10*n+3)*a(n-1) + 4*(n-1)*(10*n^2+10*n-9)*a(n-2) - 144*(n-2)*(n-1)*a(n-3) - 144*(n-3)*(n-2)*(n-1)*a(n-4).

a(n) ~ 6^(n + 3/2) / (Pi*n)^(3/2). (End)

Example

a(2)=12 since a(1) is obviously 3 and from each of these three positions there are four possible steps which remain in the first octant.

Maple

S:= series((BesselI(0, 2*x)+BesselI(1, 2*x))^3, x, 101):
seq(simplify(coeff(S, x, n))*n!, n=0..100); # Robert Israel, Oct 10 2016

Crossrefs

Cf. A064037. The two- and one-dimensional equivalents are A005566 and A001405. With no restriction on the walks, the number is 6^n, i.e. A000400.

Sequence in context: A151188 A151189 A199875 * A195255 A241468 A224914

Adjacent sequences: A064033 A064034 A064035 * A064037 A064038 A064039

Keyword

nonn

Author

Henry Bottomley, Aug 23 2001

Status

approved