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
KEYWORD
nonn,easy,walk
AUTHOR
Franklin T. Adams-Watters, Mar 09 2011
STATUS
approved