login
This site is supported by donations to The OEIS 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. 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

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 May 24 18:18 EDT 2017. Contains 286997 sequences.