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

Author

Henry Bottomley, Aug 23 2001

Keywords

• nonn

Examples

			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.
		

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.

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.

Programs

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

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)