A117813 Consider 1-D random walk with jumps up to the third neighbor, i.e., set of possible jumps is {-3,-2,-1,+1,+2,+3}. Sequence gives number of paths of length n ending at origin.

1, 0, 6, 18, 122, 600, 3450, 18914, 107338, 606816, 3466356, 19852470, 114239642, 659275760, 3815952426, 22138925718, 128718762250, 749773729952, 4374616990332, 25561798008252, 149562047056572, 876140945014640, 5138089929141890, 30162194533001982

Offset: 0

Author

Sergey Perepechko, Apr 30 2006

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A092765.

Programs

Maple

a:=array(0..25,[1,0,6,18,122,600,3450]): for n from 0 to 18 do a[n + 7]:=(36864*(n + 1)*(n + 2)*(n + 3)*a[n] - 3072*(n + 2)*(n + 3)*(97*n + 142)*a[n + 1] - 64*(n + 3)*(4031*n^2 + 17601*n + 19504)*a[n + 2] - (26944*n^3 + 215856*n^2 + 498848*n + 243840)*a[n + 3] + (15912*n^3 + 173328*n^2 + 687072*n + 997512)*a[n + 4] + (1868*n^3 + 28044*n^2 + 143368*n + 249960)*a[n + 5] - 2*(n + 6)*(115*n^2 + 1080*n + 2273)*a[n + 6])/(3*(n + 7)*(3*n + 19)*(3*n + 20)) od;
a:=n->add(add(binomial(n,m)*binomial(n,2*n-4*m+2*k)*binomial(2*n-4*m+2*k,k),m=ceil((n+2*k)/4)..floor((n+k)/2)),k=0..n);

Mathematica

f[n_] := Sum[ Binomial[n, m] Binomial[n, 2 n - 4 m + 2 k] Binomial[2 n - 4 m + 2 k, k], {k, 0, n}, {m, Ceiling[(n + 2 k)/4], Floor[(n + k)/2]}]; Array[f, 21, -1]

Formula

Recurrence: 36864*(n + 1)*(n + 2)*(n + 3)*a(n) - 3072*(n + 2)*(n + 3)*(97*n + 142)*a(n + 1) - 64*(n + 3)*(4031*n^2 + 17601*n + 19504)*a(n + 2) - (26944*n^3 + 215856*n^2 + 498848*n + 243840)*a(n + 3) + (15912*n^3 + 173328*n^2 + 687072*n + 997512)*a(n + 4) + (1868*n^3 + 28044*n^2 + 143368*n + 249960)*a(n + 5) - 2*(n + 6)*(115*n^2 + 1080*n + 2273)*a(n + 6) - 3*(n + 7)*(3*n + 19)*(3*n + 20)*a(n + 7) = 0.

O.d.e. for g.f.: x^2*(6*x - 1)^2*(8*x + 1)^2*(2*x + 1)*(8*x^2 - 68*x - 27)*(d^3/dx^3)G(x) + 6*x*(6*x - 1)*(8*x + 1)*(1152*x^5 - 6640*x^4 - 4164*x^3 - 500*x^2 - 3*x + 9)*(d^2/dx^2)G(x) + 6*(110592*x^7 - 390144*x^6 - 122048*x^5 + 11416*x^4 + 10420*x^3 + 820*x^2 + 84*x - 1)*(d/dx)G(x) + 24*x*(9216*x^5 - 11520*x^4 - 1136*x^3 + 1562*x^2 + 171*x + 30)*G(x) = 0.

Algebraic equation for generating function: (16x^2+8x-1)^2+4(6x-1)(2x+1)(1216x^4+832x^3+4x^2-46x+7)G(x)^2+2(6x-1)^2(2x+1)^2(9120x^4+3744x^3-1264x^2-212x+135)G(x)^4+4(6x-1)^3(2x+1)^3(68x^2+10x-9)(8x^2-68x-27)G(x)^6+(6x-1)^4(2x+1)^4(8x^2-68x-27)^2G(x)^8=0. - Sergey Perepechko, Mar 31 2010