login
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

%I #23 Feb 27 2016 18:08:58

%S 2,10,48,232,1138,5666,28592,145984,752978,3918282,20547456,108482952,

%T 576187554,3076640898,16506527392,88938911296,481067145826,

%U 2611212958154,14218923060752,77653486423528,425227486222482

%N 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.

%H Vincenzo Librandi, <a href="/A114693/b114693.txt">Table of n, a(n) for n = 0..300</a>

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

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

%F 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

%F a(n) ~ sqrt(15900+11243*sqrt(2))*(3+2*sqrt(2))^n/(4*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 19 2012

%F 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.

%e 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).

%p 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);

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

%o (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 */

%Y Cf. A049611, A104219, A114692.

%K nonn

%O 0,1

%A _Emeric Deutsch_, Dec 26 2005