A181072 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.
1, 0, 8, 36, 296, 2030, 15200, 112308, 845320, 6386076, 48582438, 371138460, 2846769992, 21905812786, 169041544568, 1307602672376, 10136307859080, 78721657307320, 612391634798156, 4770987007606224, 37219155177139126, 290702353768374570, 2273036878855399720
Offset: 0
Keywords
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..500
Programs
-
Maple
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);
Formula
Exact formula:
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).
Recurrence:
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
Algebraic equation for generating function:
- (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