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

1, 0, 2, 2, 11, 24, 93, 272, 971, 3194, 11293, 39148, 139687, 497756, 1798002, 6517194, 23807731, 87336870, 322082967, 1192381270, 4431889344, 16527495396, 61831374003, 231973133544, 872598922407, 3290312724374, 12434632908623, 47089829065940, 178672856753641

Offset

0,3

Comments

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.

Self-convolution of A055113. - Paul D. Hanna, May 31 2015

Logarithmic derivative yields A092765 (with offset 1). - Paul D. Hanna, May 31 2015

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

C. Banderier, Analytic combinatorics of random walks and planar maps, PhD Thesis, 2001 , Example 11.

C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, arXiv preprint arXiv:1609.06473 [math.CO], 2016.

Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).

Formula

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

a(n) ~ (3/sqrt(5)-1) * 2^(2*n+1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 09 2014

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

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

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

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

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

From Seiichi Manyama, Jan 17 2024: (Start)

G.f.: (1/x) * Series_Reversion( x * (1-x)^2 / (1-x+x^2)^2 ).

a(n) = (1/(n+1)) * Sum_{k=0..floor(n/2)} binomial(2*n+2,k) * binomial(n-k-1,n-2*k). (End)

Example

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.

Maple

a:= proc(n) option remember; `if`(n<3, (n-1)*(3*n-2)/2,
     ((n+1)*(115*n^3-137*n^2-10*n+8) *a(n-1)
      +4*(2*n-1)*(5*n^3+36*n^2-26*n-12) *a(n-2)
      -36*(n-2)*(2*n-1)*(2*n-3)*(5*n+1) *a(n-3))
      / (2*(5*n-4)*(2*n+1)*(n+2)*(n+1)))
    end:
seq(a(n), n=0..30); # Alois P. Heinz, May 16 2013

Mathematica

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 *)

Prog

(PARI) al(n)={local(r, p);
r=vector(n); r[1]=p=1;
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));
r}
(Maxima)
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 */

Crossrefs

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

Sequence in context: A327870 A235606 A175202 * A151365 A244280 A090527

Adjacent sequences: A187427 A187428 A187429 * A187431 A187432 A187433

Keyword

nonn,easy,walk

Author

Franklin T. Adams-Watters, Mar 09 2011

Status

approved