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

1, 3, 24, 285, 4242, 73206, 1403028, 29082339, 640672890, 14818136190, 356665411440, 8874875097270, 227135946200940, 5955171596514900, 159439898653636320, 4347741997166750235, 120493374240909299130, 3387806231071627372590, 96488484001399878973200

Offset: 0

Author

Henry Bottomley, Aug 23 2001

Keywords

• nonn

Examples

			a(1)=3 and a(2)=24 since if the possible steps are Right, Left, Up, Down, Forwards and Backwards, then the two-step paths are FB, RL and UD, while the four-step paths are FBFB, FBRL, FBUD, FFBB, FRBL, FRLB, FUBD, FUDB, RFBL, RFLB, RLFB, RLRL, RLUD, RRLL, RUDL, RULD, UDFB, UDRL, UDUD, UFBD, UFDB, URDL, URLD, UUDD.
		

Links

• Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.
• R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
• James Mallos, A 6-Letter 'DNA' for Baskets with Handles, Mathematics (2019) Vol. 7, No. 2, 165.
• G. Xin, Determinant formulas relating to tableaux of bounded height, Adv. Appl. Math. 45 (2010) 197-211.

Crossrefs

Cf. A064036. The two- and one-dimensional equivalents are A005568 and A000108.

Programs

Maple

f := -3*x+(1+sqrt(1-40*x+144*x^2))/4;
H := (1-2*f)*f*hypergeom([1/6,1/3],[1],27*(1-2*f)*f^2)^2/sqrt(1+6*f);
r2 := (1-4*x)*(36*x-1)*(1920*x^2+166*x+1)*x^2;
r1 := -(138240*x^4+7776*x^3+200*x^2-92*x-1)*x;
r0 := 19800*x^3+764*x^2-86*x-1;
ogf := (r2*diff(H,x,x)+r1*diff(H,x)+r0*H)/(5760*x^4) + 1/(2*x);
series(ogf, x=0, 30); # Mark van Hoeij, Apr 19 2013
# second Maple program:
a:= proc(n) option remember; `if`(n<2, 2*n+1, ((8*n-4)*(5*n^2+10*n+3)
       *a(n-1)-36*(2*n-1)*(2*n-3)*(n-1)*a(n-2))/((n+1)*(n+2)*(n+3)))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Mar 29 2019

Mathematica

Table[Sum[Binomial[2*n, 2*j] * CatalanNumber[j] * CatalanNumber[j+1] * CatalanNumber[n-j], {j, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Jun 09 2019 *)

PARI

C(n,k) = binomial(n,k);
c(n) = binomial(2*n,n)/(n+1);
a(n) = sum(j=0,n, C(2*n, 2*j)*c(j)*c(j+1)*c(n-j));
/* Joerg Arndt, Apr 19 2013 */

Formula

a(n) = Sum_{j=0..n} C(2n, 2j)*c(j)*c(j+1)*c(n-j) where c(k)=A000108(k).

G.f. is a large expression in terms of hypergeometric functions and sqrt's, see Maple program. - Mark van Hoeij, Apr 19 2013

a(n) = binomial(2*n,n)*((7*n+11)*A002893(n+1)-(9*n+9)*A002893(n))/(2*(n+1)*(n+2)^2*(n+3)). - Mark van Hoeij, Apr 19 2013

a(n) ~ 2^(2*n - 2) * 3^(2*n + 9/2) / (Pi^(3/2) * n^(9/2)). - Vaclav Kotesovec, Jun 09 2019

D-finite with recurrence: (n+3)*(n+2)*(n+1)*a(n) -4*(2*n-1)*(5*n^2+10*n+3)*a(n-1) +36*(n-1)*(2*n-1)*(2*n-3)*a(n-2)=0. - R. J. Mathar, Feb 20 2020

Extensions

Added more terms, Joerg Arndt, Apr 19 2013