A114693 Number of returns to the x-axis in all hill-free Schroeder paths of length 2n+4. A Schroeder path of length 2n is a lattice path from (0,0) to (2n,0) consisting of U=(1,1), D=(1,-1) and H=(2,0) steps and never going below the x-axis. A hill is a peak at height 1.

2, 10, 48, 232, 1138, 5666, 28592, 145984, 752978, 3918282, 20547456, 108482952, 576187554, 3076640898, 16506527392, 88938911296, 481067145826, 2611212958154, 14218923060752, 77653486423528, 425227486222482

Offset

0,1

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..300

Formula

G.f.: 2*(1-3*z-sqrt(1-6*z+z^2))/(z*(1+z+sqrt(1-6*z+z^2)))^2.

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

Recurrence: (n+4)*(7*n+1)*a(n) = (42*n^2 + 109*n + 49)*a(n-1) - (7*n^2 - 4*n - 5)*a(n-2) - 2*(n-2)*a(n-3). - Vaclav Kotesovec, Oct 19 2012

a(n) ~ sqrt(15900+11243*sqrt(2))*(3+2*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 19 2012

a(n) = Sum_{k=0..n+1} ( (k^3+8*k^2+15*k+8) * Sum_{j=0..n-k} ((-1)^j*2^(n+1-j)*binomial(n+1,j)*binomial(2*n-k-j,n)) )/(8*(n+1)). - Vladimir Kruchinin, Feb 27 2016.

Example

a(0)=2 because in the three hill-free Schroeder paths of length 4, namely HH, UH(D) and UUD(D), we have altogether 2 returns to the x-axis (shown between parentheses).

Maple

G:=2*(1-3*z-sqrt(1-6*z+z^2))/z^2/(1+z+sqrt(1-6*z+z^2))^2: Gser:=series(G, z=0, 30): 2, seq(coeff(Gser, z^n), n=1..23);

Mathematica

CoefficientList[Series[2*(1-3*x-Sqrt[1-6*x+x^2])/(x*(1+x+Sqrt[1 -6*x+x^2]))^2, {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 19 2012 *)

Prog

(Maxima) a(n):=sum((k^3+8*k^2+15*k+8)*sum((-1)^j*2^(n+1-j)*binomial(n+1, j)*binomial(2*n-k-j, n), j, 0, n-k), k, 0, (n+1))/(8*(n+1)). /* Vladimir Kruchinin, Feb 27 2016 */

Crossrefs

Cf. A049611, A104219, A114692.

Sequence in context: A181296 A239073 A065982 * A086853 A036918 A200540

Adjacent sequences: A114690 A114691 A114692 * A114694 A114695 A114696

Keyword

nonn

Author

Emeric Deutsch, Dec 26 2005

Status

approved