|
%I #55 Jan 17 2024 09:35:29
%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.
%H Jean-Luc Baril and José L. Ramírez, <a href="http://jl.baril.u-bourgogne.fr/knight.pdf">Knight's paths towards Catalan numbers</a>, Univ. Bourgogne Franche-Comté (2022).
%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
%F From _Seiichi Manyama_, Jan 17 2024: (Start)
%F G.f.: (1/x) * Series_Reversion( x * (1-x)^2 / (1-x+x^2)^2 ).
%F a(n) = (1/(n+1)) * Sum_{k=0..floor(n/2)} binomial(2*n+2,k) * binomial(n-k-1,n-2*k). (End)
%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
|
