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

%I #19 Jul 20 2017 02:23:16

%S 1,0,8,36,296,2030,15200,112308,845320,6386076,48582438,371138460,

%T 2846769992,21905812786,169041544568,1307602672376,10136307859080,

%U 78721657307320,612391634798156,4770987007606224,37219155177139126,290702353768374570,2273036878855399720

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

%H Alois P. Heinz, <a href="/A181072/b181072.txt">Table of n, a(n) for n = 0..500</a>

%F Exact formula:

%F a(n) = sum(binomial(n, k) * (sum(binomial(n, m) * binomial(n, 2*k + 2*n - 5*m), m = ceiling((2*k + n)/5)..floor(2*(n+k)/5))), k=0..n).

%F Recurrence:

%F 128000000 * (2 * n + 1) * (n + 3) * (n + 2) * (n + 1) * a(n) - 6400000 * (n + 3) * (n + 2) * (99 * n^2 + 185 * n + 50) * a(n + 1) -16000 * (n + 3) * (36954 * n^3 + 183733 * n^2 + 299913 * n + 167000) * a(n + 2) - 800 * (-1263000 + 505346 * n + 1523457 *n^2 + 630883 * n^3 + 76989 * n^4) * a(n + 3) + 80 * (71669625 + 72733160 * n + 28214529 * n^2 + 5186629 * n^3 + 389781 * n^4) * a(n + 4) + 8 * (172598700 + 157978087 * n + 52620462 * n^2 + 7605827 * n^3 + 403092 * n^4) * a(n + 5) - 4 * (92866218 + 67549595 * n + 19555350 * n^2 + 2588005 * n^3 + 129192 * n^4) * a(n + 6) - 2 * (52403820 + 30999812 * n + 6869373 * n^2 + 675772 * n^3 + 24903 * n^4) * a(n + 7) + (n + 8) * (2763 * n^3 + 53150 * n^2 + 321017 * n + 579030) * a(n + 8) + 8 * (4 * n + 35) * (n + 9) * (4 * n + 33) * (2 * n + 17) * a(n + 9) = 0

%F Algebraic equation for generating function:

%F - (400 * x^5 + 6240 * x^4 + 20376 * x^3 + 2200 * x^2 + 9 * x - 48)^2 * x^2 + 8 * (8 * x - 1) * (800000 * x^11 + 11760000 * x^10 + 78809600 * x^9 + 443644960 * x^8 + 2350482624 * x^7 + 155829416 * x^6 - 139281808 * x^5 - 52419090 * x^4 + 2482459 * x^3 + 1367208 * x^2 - 83328 * x - 2048) * g(x)^2 * x - 4 * (28000000 * x^11 + 40800000 * x^10 + 1233968000 * x^9 - 3953176000 * x^8 + 75242361184 * x^7 + 11694517328 * x^6 - 7030304072 * x^5 - 1845621940 * x^4 + 821550463 * x^3 + 67315608 * x^2 - 30631040 * x + 1921024) * (8 * x - 1)^2 * g(x)^4 * x + 8 * (140000000 * x^12 - 1194000000 * x^11 + 11067600000 * x^10 - 78000428000 * x^9 + 281516359680 * x^8 + 139037614344 * x^7 - 34486520616 * x^6 - 12507324570 * x^5 + 2600603973 * x^4 - 136469008 * x^3 - 136037760 * x^2 + 31825920 * x - 2097152) * (8 * x - 1)^3 * g(x)^6 - 2 * (3500000000 * x^12 - 53400000000 * x^11 + 453587200000 * x^10 - 2350791440000 * x^9 + 3738567060000 * x^8 + 4916593964640 * x^7 + 405974360448 * x^6 - 629094250008 * x^5 - 20410907037 * x^4 + 50599387568 * x^3 - 906930048 * x^2 - 1473314816 * x + 142606336) * (8 * x - 1)^4 * g(x)^8 + 8 * (500 * x^3 - 1200 * x^2 - 1227 * x - 256) * (7000000 * x^9 - 114300000 * x^8 + 798610000 * x^7 - 2019518000 * x^6 - 1531462308 * x^5 + 192490034 * x^4 + 195987449 * x^3 - 14097912 * x^2 - 7290368 * x + 917504) * (8 * x - 1)^5 * g(x)^10 - 4 * (70000 * x^6 - 990000 * x^5 + 4067760 * x^4 + 1850948 * x^3 - 408249 * x^2 - 120408 * x + 22528) * (500 * x^3 - 1200 * x^2 - 1227 * x - 256)^2 * (8 * x - 1)^6 * g(x)^12 + 8 * (100 * x^3 - 870 * x^2 - 177 * x + 64) * (500 * x^3 - 1200 * x^2 - 1227 * x - 256)^3 * (8 * x - 1)^7 * g(x)^14 - (500 * x^3 - 1200 * x^2 - 1227 * x - 256)^4 * (8 * x - 1)^8 * g(x)^16 = 0

%p a:=n->add(binomial(n,k)*(add(binomial(n,m)*binomial(n,2*k+2*n-5*m),m=ceil((2*k+n)/5)..floor(2*(n+k)/5))),k=0..n);

%Y Cf. A092765, A117813.

%K nonn

%O 0,3

%A _Sergey Perepechko_, Jan 23 2011