|
| |
|
|
A092765
|
|
Consider the 1-D random walk with jumps to next-nearest neighbors. Sequence gives number of paths of length n ending at origin.
|
|
7
|
|
|
|
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, 56350223472600, 221094286028100
(list;
graph;
refs;
listen;
history;
text;
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.
|
|
|
LINKS
|
|
|
|
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, Sep 06 2004
a(n) = (2^(2n+1) / Pi) * Integral(cos(t)^n*cos(3*t)^n, t=0..Pi/2); a(n) = Sum_{k=0..n} binomial(n,k)*binomial(4*n-2*k,2*n-k)*(-3)^k. 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, Apr 19 2006
a(n) = Sum_{k=0..n} binomial(n,k)*binomial(n,2*n-3*k). - Max Alekseyev, Feb 08 2008
a(n) = Sum_{k=0..2n} (-1)^k*binomial(2n,k)*A027907(n,k) where A027907 is the triangle of trinomial coefficients. - Paul D. Hanna, Nov 30 2009
a(n) = ((n-1)*(35*n^2-49*n+12) *a(n-1) +18*(n-1)*(2*n-3)*(5*n-2) *a(n-2)) / (2*n*(2*n-1)*(5*n-7)) for n>=2, a(n) = 1-n for n<2. - Alois P. Heinz, May 20 2013
a(n) is the coefficient of x^(2*n) in ((1-x)*(1-x^3))^n. - Max Alekseyev, Jun 01 2015
a(n) = (-1)^n*binomial(2*n,n)*hypergeom([-n,n/2,(n+1)/2],[n,n+1],4). - Peter Luschny, Nov 02 2016
a(n) = Sum_{k = 0..n} (-1)^k*binomial(2*n,k)*binomial(3*n-2*k-1,n-k).
a(n) = Sum_{k = 0..floor(n/2)} binomial(2*n,k)*binomial(n-k-1,n-2*k).
a(n) = [x^n] ((1 - x + x^2)/(1 - x))^(2*n).
The Gauss congruences a(n*p^k) == a(n*p^(k-1)) ( mod p^k ) hold for any prime p and positive integers n and k.
Conjecture: the stronger congruences a(n*p^k) == a(n*p^(k-1)) ( mod p^(2*k) ) hold for any prime p, except p = 3, and positive integers n and k.(End)
|
|
|
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:
seq(coeff( (t^2+t+1/t+1/t^2)^n, t, 0), n=0..24); # Mark van Hoeij, May 20 2013
|
|
|
MATHEMATICA
|
a[n_] := Binomial[4n, 2n]*Hypergeometric2F1[-2n, -n, 1/2 - 2n, 3/4]; Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Nov 22 2012 *)
|
|
|
PROG
|
(PARI) a(n) = sum(k=0, n, binomial(n, k)*binomial(4*n-2*k, 2*n-k)*(-3)^k) /* Max Alekseyev, 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)) /* Paul D. Hanna, Nov 30 2009 */
(PARI) a(n) = polcoeff(( (1-x)*(1-x^3) + O(x^(2*n+1)) )^n, 2*n); /* Max Alekseyev, Jun 01 2015 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
