cp's OEIS Frontend

A092765 Consider the 1-D random walk with jumps to next-nearest neighbors. Sequence gives number of paths of length n ending at origin.

%I A092765 #43 Feb 16 2025 08:32:52
%S A092765 1,0,4,6,36,100,430,1470,5796,21336,82404,312180,1203246,4617756,
%T A092765 17846686,68974906,267498660,1038555024,4040525320,15739195680,
%U A092765 61399048036,239788778760,937536139764,3669179504364,14373144873774,56350223472600,221094286028100
%N A092765 Consider the 1-D random walk with jumps to next-nearest neighbors. Sequence gives number of paths of length n ending at origin.
%C A092765 In Lakatos-Lindenberg and Shuler besides some physical background there is an exact algebraic expression for the generating function.
%C A092765 Examples from Banderier and Flajolet deal with constrained walks ("meanders" and "excursions") while this sequence counts unrestricted paths.
%C A092765 Logarithmic derivative of A187430 (when offset 1). - _Paul D. Hanna_, May 31 2015
%H A092765 Alois P. Heinz, <a href="/A092765/b092765.txt">Table of n, a(n) for n = 0..1000</a>
%H A092765 C. Banderier and P. Flajolet, <a href="http://dx.doi.org/10.1016/S0304-3975(02)00007-5">Basic analytic combinatorics of directed lattice paths</a>, Theoretical Computer Science, Vol. 281:1-2, pp. 37-80, 2002.
%H A092765 P. Flajolet, <a href="http://algo.inria.fr/flajolet/Publications/">Basic analytic combinatorics of directed lattice paths</a>.
%H A092765 K. Lakatos-Lindenberg and K. E. Shuler, <a href="http://dx.doi.org/10.1063/1.1665630">Random walks with nonnearest neighbor transitions. I. Analytic 1-D theory for next-nearest neighbor and exponentially distributed steps</a>, Journal of Mathematical Physics, Vol. 12 Num.4, pp. 633-652, 1971.
%H A092765 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/EightCurve.html">Eight Curve</a>
%F A092765 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).
%F A092765 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
%F A092765 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
%F A092765 a(n) = Sum_{k=0..n} binomial(n,k)*binomial(n,2*n-3*k). - _Max Alekseyev_, Feb 08 2008
%F A092765 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
%F A092765 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
%F A092765 a(n) ~ 4^n / sqrt(5*Pi*n). - _Vaclav Kotesovec_, Sep 12 2014
%F A092765 a(n) is the coefficient of x^(2*n) in ((1-x)*(1-x^3))^n. - _Max Alekseyev_, Jun 01 2015
%F A092765 a(n) = (-1)^n*binomial(2*n,n)*hypergeom([-n,n/2,(n+1)/2],[n,n+1],4). - _Peter Luschny_, Nov 02 2016
%F A092765 From _Peter Bala_, Feb 08 2022: (Start)
%F A092765 a(n) = Sum_{k = 0..n} (-1)^k*binomial(2*n,k)*binomial(3*n-2*k-1,n-k).
%F A092765 a(n) = Sum_{k = 0..floor(n/2)} binomial(2*n,k)*binomial(n-k-1,n-2*k).
%F A092765 a(n) = [x^n] ((1 - x + x^2)/(1 - x))^(2*n).
%F A092765 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.
%F A092765 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)
%e A092765 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.
%p A092765 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:
%p A092765 seq(coeff( (t^2+t+1/t+1/t^2)^n, t, 0), n=0..24);   # _Mark van Hoeij_, May 20 2013
%t A092765 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 *)
%o A092765 (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 */
%o A092765 (PARI) a(n)=sum(k=0,n,binomial(n,k)*binomial(n,2*n-3*k))  /* Max Alekseyev, Feb 08 2008 */
%o A092765 (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 */
%o A092765 (PARI) a(n) = polcoeff(( (1-x)*(1-x^3) + O(x^(2*n+1)) )^n, 2*n); /* _Max Alekseyev_, Jun 01 2015 */
%Y A092765 Cf. A027907, A092765, A187430.
%K A092765 nonn,easy
%O A092765 0,3
%A A092765 _Sergey Perepechko_, Apr 19 2004
%E A092765 More terms from _Max Alekseyev_, Apr 19 2006