login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A187430 Number of nonnegative walks of n steps with step sizes 1 and 2, starting and ending at 0. 7

%I

%S 1,0,2,2,11,24,93,272,971,3194,11293,39148,139687,497756,1798002,

%T 6517194,23807731,87336870,322082967,1192381270,4431889344,

%U 16527495396,61831374003,231973133544,872598922407,3290312724374,12434632908623,47089829065940,178672856753641

%N Number of nonnegative walks of n steps with step sizes 1 and 2, starting and ending at 0.

%C Equivalently, the number of paths from (0,0) to (n,0) using steps of the form (1,2),(1,1),(1,-1) or (1,-2) and staying on or above the x-axis.

%C Self-convolution of A055113. - _Paul D. Hanna_, May 31 2015

%C Logarithmic derivative yields A092765 (with offset 1). - _Paul D. Hanna_, May 31 2015

%H Alois P. Heinz, <a href="/A187430/b187430.txt">Table of n, a(n) for n = 0..1000</a>

%H C. Banderier, <a href="http://lipn.univ-paris13.fr/~banderier/Papers/these.ps">Analytic combinatorics of random walks and planar maps</a>, PhD Thesis, 2001 , Example 11.

%H C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, <a href="https://arxiv.org/abs/1609.06473">Explicit formulas for enumeration of lattice paths: basketball and the kernel method</a>, arXiv preprint arXiv:1609.06473 [math.CO], 2016.

%F G.f.: 1/(2*x)-(1+(1-4*x)^(1/2))*((2+2*(1-4*x)^(1/2)+12*x)^(1/2)-2)/(8*x^2). - _Mark van Hoeij_, May 16 2013

%F a(n) ~ (3/sqrt(5)-1) * 2^(2*n+1) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Sep 09 2014

%F G.f.: exp( Sum_{n>=1} A092765(n)*x^n/n ), where A092765(n) = Sum_{k=0..n} binomial(n,k)*binomial(n,2*n-3*k). - _Paul D. Hanna_, May 31 2015

%F a(n) = ((Sum_{l=0..n+1} (C(n+1,l)*Sum_{i=0..(n-1)/2}(C(n-2*i-1,2*l-1)*C(n-l+1,i))))+(((-1)^n+1)/2*C(n+1,n/2)))/(n+1). - _Vladimir Kruchinin_, Jun 26 2015

%F Sum_{n>=0} a(n)*x^(n+1) is the compositional inverse of x*(1-x^2)^2/(1+x^3)^2. - _Ira M. Gessel_, Sep 19 2017

%F Conjecture: 1 + Sum_{n>=0} a(n)*(-1)^n x^(n+1)/(1-x)^(2*n+2) = C(x), the g.f. for the Catalan numbers A000108. - _Benedict W. J. Irwin_, Jan 13 2017

%F D-finite with recurrence 2*(2*n+1)*(n+2)*(n+1)*a(n) +(n+1)*(n^2-27*n+2)*a(n-1) +2*(-73*n^3+204*n^2-167*n+6)*a(n-2) +12*(n-3)*(2*n-3)*(4*n-7)*a(n-3) +216*(2*n-5)*(n-3)*(2*n-3)*a(n-4)=0. - _R. J. Mathar_, Sep 29 2020

%e The 11 length-4 walks are 0,2,4,2,0; 0,2,3,2,0; 0,2,3,1,0; 0,2,1,2,0; 0,2,0,2,0; 0,2,0,1,0; 0,1,3,2,0; 0,1,3,1,0; 0,1,2,1,0; 0,1,0,2,0; and 0,1,0,1,0.

%p a:= proc(n) option remember; `if`(n<3, (n-1)*(3*n-2)/2,

%p ((n+1)*(115*n^3-137*n^2-10*n+8) *a(n-1)

%p +4*(2*n-1)*(5*n^3+36*n^2-26*n-12) *a(n-2)

%p -36*(n-2)*(2*n-1)*(2*n-3)*(5*n+1) *a(n-3))

%p / (2*(5*n-4)*(2*n+1)*(n+2)*(n+1)))

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, May 16 2013

%t a[n_] := (Sum[Binomial[n+1, l]*Sum[Binomial[n-2*i-1, 2*l-1]*Binomial[n-l+1, i], {i, 0, (n-1)/2}], {l, 0, n+1}] + (((-1)^n+1)*Binomial[n+1, n/2])/2)/(n+1); Table[a[n], {n, 0, 30}] (* _Jean-Fran├žois Alcover_, Oct 24 2016, after _Vladimir Kruchinin_ *)

%o (PARI) al(n)={local(r,p);

%o r=vector(n);r[1]=p=1;

%o for(k=2,n,p*=1+x+x^3+x^4;p=(p-polcoeff(p,0)-polcoeff(p,1)*x)/x^2;r[k]=polcoeff(p,0));

%o r}

%o (Maxima)

%o a(n):=((sum(binomial(n+1,l)*sum(binomial(n-2*i-1,2*l-1)*binomial(n-l+1,i),i,0,(n-1)/2),l,0,n+1))+(((-1)^n+1)*binomial(n+1,n/2))/2)/(n+1); /* _Vladimir Kruchinin_, Jun 26 2015 */

%Y Cf. A126120, A104184, A001006, A055113, A092765.

%K nonn,easy,walk

%O 0,3

%A _Franklin T. Adams-Watters_, Mar 09 2011

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 11 16:42 EDT 2021. Contains 342888 sequences. (Running on oeis4.)