|
| |
|
|
A092765
|
|
Consider the 1-D random walk with jumps to next-nearest neighbors. Sequence gives number of paths of length n ending at origin.
|
|
5
| |
|
|
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; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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
a(n) = Sum_{k=0..2n} (-1)^k*C(2n,k)*A027907(n,k) where A027907 is the triangle of trinomial coefficients. [From Paul D. Hanna (pauldhanna(AT)juno.com), Nov 30 2009]
|
|
|
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:
|
|
|
PROG
| (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
(PARI) {a(n)=sum(k=0, 2*n, (-1)^k*binomial(2*n, k)*polcoeff((1+x+x^2)^n, k))} [From Paul D. Hanna (pauldhanna(AT)juno.com), Nov 30 2009]
|
|
|
CROSSREFS
| Cf. A027907. [From Paul D. Hanna (pauldhanna(AT)juno.com), Nov 30 2009]
Sequence in context: A176002 A175061 A092187 * A056315 A103234 A074061
Adjacent sequences: A092762 A092763 A092764 * A092766 A092767 A092768
|
|
|
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
|
| |
|
|
