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,2

Links

Table of n, a(n) for n=0..18.

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.

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

Example

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.

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 *)

Prog

(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 */

Crossrefs

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

Sequence in context: A351763 A355794 A355426 * A257453 A128572 A052592

Adjacent sequences: A064034 A064035 A064036 * A064038 A064039 A064040

Keyword

nonn

Author

Henry Bottomley, Aug 23 2001

Extensions

Added more terms, Joerg Arndt, Apr 19 2013

Status

approved