cp's OEIS Frontend

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

%I A064037 #42 Apr 20 2025 03:47:27
%S A064037 1,3,24,285,4242,73206,1403028,29082339,640672890,14818136190,
%T A064037 356665411440,8874875097270,227135946200940,5955171596514900,
%U A064037 159439898653636320,4347741997166750235,120493374240909299130,3387806231071627372590,96488484001399878973200
%N A064037 Number of walks of length 2n on cubic lattice, starting and finishing at origin and staying in first (nonnegative) octant.
%H A064037 Nachum Dershowitz, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Dershowitz/dersh3.html">Touchard's Drunkard</a>, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.
%H A064037 R. K. Guy, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/GUY/catwalks.html">Catwalks, sandsteps and Pascal pyramids</a>, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.
%H A064037 James Mallos, <a href="https://doi.org/10.3390/math7020165">A 6-Letter 'DNA' for Baskets with Handles</a>, Mathematics (2019) Vol. 7, No. 2, 165.
%H A064037 G. Xin, <a href="http://dx.doi.org/10.1016/j.aam.2007.04.007">Determinant formulas relating to tableaux of bounded height</a>, Adv. Appl. Math. 45 (2010) 197-211.
%F A064037 a(n) = Sum_{j=0..n} C(2n, 2j)*c(j)*c(j+1)*c(n-j) where c(k)=A000108(k).
%F A064037 G.f. is a large expression in terms of hypergeometric functions and sqrt's, see Maple program. - _Mark van Hoeij_, Apr 19 2013
%F A064037 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
%F A064037 a(n) ~ 2^(2*n - 2) * 3^(2*n + 9/2) / (Pi^(3/2) * n^(9/2)). - _Vaclav Kotesovec_, Jun 09 2019
%F A064037 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
%e A064037 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.
%p A064037 f := -3*x+(1+sqrt(1-40*x+144*x^2))/4;
%p A064037 H := (1-2*f)*f*hypergeom([1/6,1/3],[1],27*(1-2*f)*f^2)^2/sqrt(1+6*f);
%p A064037 r2 := (1-4*x)*(36*x-1)*(1920*x^2+166*x+1)*x^2;
%p A064037 r1 := -(138240*x^4+7776*x^3+200*x^2-92*x-1)*x;
%p A064037 r0 := 19800*x^3+764*x^2-86*x-1;
%p A064037 ogf := (r2*diff(H,x,x)+r1*diff(H,x)+r0*H)/(5760*x^4) + 1/(2*x);
%p A064037 series(ogf, x=0, 30); # _Mark van Hoeij_, Apr 19 2013
%p A064037 # second Maple program:
%p A064037 a:= proc(n) option remember; `if`(n<2, 2*n+1, ((8*n-4)*(5*n^2+10*n+3)
%p A064037        *a(n-1)-36*(2*n-1)*(2*n-3)*(n-1)*a(n-2))/((n+1)*(n+2)*(n+3)))
%p A064037     end:
%p A064037 seq(a(n), n=0..20);  # _Alois P. Heinz_, Mar 29 2019
%t A064037 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 *)
%o A064037 (PARI)
%o A064037 C(n,k) = binomial(n,k);
%o A064037 c(n) = binomial(2*n,n)/(n+1);
%o A064037 a(n) = sum(j=0,n, C(2*n, 2*j)*c(j)*c(j+1)*c(n-j));
%o A064037 /* _Joerg Arndt_, Apr 19 2013 */
%Y A064037 Cf. A064036. The two- and one-dimensional equivalents are A005568 and A000108.
%K A064037 nonn
%O A064037 0,2
%A A064037 _Henry Bottomley_, Aug 23 2001
%E A064037 Added more terms, _Joerg Arndt_, Apr 19 2013