|
Search: id:A092765
|
|
|
| A092765 |
|
Consider the 1-D random walk with jumps to next-nearest neighbors. Sequence gives number of paths of length n ending at origin. |
|
+0
3
|
|
| 1, 0, 4, 6, 36, 100, 430, 1470, 5796, 21336, 82404, 312180, 1203246, 4617756, 17846686, 68974906, 267498660, 1038555024, 4040525320, 15739195680, 61399048036, 239788778760, 937536139764, 3669179504364, 14373144873774
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
In Lakatos-Lindenberg and Shuler besides some physical background there is an exact algebraic expression for the generating function.
Examples from Banderier and Flajolet deal with constrained walks ("meanders" and "excursions") while this sequence counts unrestricted paths.
|
|
REFERENCES
|
C. Banderier and P. Flajolet, Basic analytic combinatorics of directed lattice paths. Theoretical Computer Science, Vol. 281:1-2, pp. 37-80, 2002
K. Lakatos-Lindenberg and K. E. Shuler, Random walks with nonnearest neighbor transitions. I. Analytic 1-D theory for next-nearest neighbor and exponentially distributed steps, Journal of Mathematical Physics, Vol. 12 Num.4, pp. 633-652, 1971.
|
|
LINKS
|
P. Flajolet, Basic analytic combinatorics of directed lattice paths.
Eric Weisstein's World of Mathematics, Eight Curve
|
|
FORMULA
|
G.f.: in Maple notation; {x*(1+6*x)*(1-4*x)*(4+9*x)*diff(G(x), x, x)=2*(270*x^3+84*x^2+13*x-1)*diff(G(x), x)+4*x*(12+27*x)*G(x), G(0)=1, D(G)(0)=0} rec; 2*(n+1)*(2*n+1)*a(n+1)+n*(17*n-43)*a(n)=(78*n^2-66*n+36)*a(n-1)+(216*n^2-540*n+324)*a(n-2)
GFun gives the following algebraic equation for generating function: x+2*(1-4*x)*(3*x-2)*g(x)^2+(1-4*x)^2*(9*x+4)*g(x)^4=0 - Sergey Perepechko (persn(AT)aport.ru), Sep 06 2004
a(n) = (2^(2n+1) / Pi) * Int(cos(t)^n*cos(3*t)^n, t=0..Pi/2); a(n) = Sum(binomial(n,k)*binomial(4*n-2*k,2*n-k)*(-3)^k, k=0..n). G.f.: (1 + sqrt(1-4*x)) / ( sqrt(1-4*x) * ( sqrt(1+6*x+2*sqrt(9*x^2+4*x)) + sqrt(1+6*x-2*sqrt(9*x^2+4*x)) ) ). - Max Alekseyev (maxale(AT)gmail.com), Apr 19 2006
a(n) = Sum(binomial(n,k)*binomial(n,2*n-3*k), k=0..n). - Max Alekseyev, Feb 08 2008
|
|
EXAMPLE
|
a(3)=6 because 0=+2-1-1, 0=-2+1+1, 0=-1-1+2, 0=+1+1-2, 0=+1-2+1, 0=-1+2-1.
|
|
MAPLE
|
a:=array(0..20):a[0]:=1:a[1]:=0:a[2]:=4:for n from 2 to 19 do a[n+1]:=(-n*(17*n-43)*a[n]+(78*n^2-66*n+36)*a[n-1]+(216*n^2-540*n+324)*a[n-2])/(\ 2*(n+1)*(2*n+1)):print(n+1, a[n+1]) od:
|
|
PROGRAM
|
(PARI) a(n) = sum(k=0, n, binomial(n, k)*binomial(4*n-2*k, 2*n-k)*(-3)^k) - Max Alekseyev (maxale(AT)gmail.com), Apr 19 2006
(PARI) { a(n)=sum(k=0, n, binomial(n, k)*binomial(n, 2*n-3*k)) } - Max Alekseyev, Feb 08 2008
|
|
CROSSREFS
|
Adjacent sequences: A092762 A092763 A092764 this_sequence A092766 A092767 A092768
Sequence in context: A071394 A137021 A092187 this_sequence A056315 A103234 A074061
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Sergey Perepechko (persn(AT)aport.ru), Apr 19 2004
|
|
EXTENSIONS
|
More terms from Max Alekseyev (maxale(AT)gmail.com), Apr 19 2006
|
|
|
Search completed in 0.002 seconds
|
