login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

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. 6
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 (list; graph; refs; listen; history; text; internal format)
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, 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.

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

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: A194638 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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified November 19 16:10 EST 2017. Contains 294936 sequences.