|
%I #25 Mar 31 2014 05:43:46
%S 0,1,5,21,89,393,1805,8557,41585,206097,1037717,5293445,27297737,
%T 142078745,745387037,3937603037,20927156705,111818026017,600318853925,
%U 3236724317173
%N A006318(n) - 1.
%C Number of occurrences of UD, UHD, UHHD, UHHHD, ... starting at level zero in all Schroeder paths of semilength n (i.e., lattice paths from (0,0) to (2n,0), with steps H=(2,0), U=(1,1) and D=(1,-1) and not going below the x-axis). Example: a(2) = 5 because in the six paths of semilength 2, namely HH, H(UD), (UD)H, (UHD), (UD)(UD), UUDD, we have 5 required occurrences (shown between parentheses). - _Emeric Deutsch_, Dec 28 2003
%H Fung Lam, <a href="/A035011/b035011.txt">Table of n, a(n) for n = 0..1300</a>
%F G.f.: (1-4*z+z^2)/(2*z*(1-z))-sqrt(1-6*z+z^2)/(2*z). - _Emeric Deutsch_, Dec 28 2003
%F Recurrence: (2*n^2 + 11*n + 12)*a(n+3) = (14*n^2 + 59*n + 60)*a(n+2) - (14*n^2 + 53*n + 48)*a(n+1) + (2*n^2 + 5*n)*a(n). - _Ralf Stephan_, Feb 11 2014
%F Asymptotics: a(n) ~ (3+2*sqrt(2))^n*(2^(1/4)+1/2^(1/4))/sqrt(2*Pi*n^3). - _Fung Lam_, Mar 31 2014
%F From _Vaclav Kotesovec_, Mar 31 2014: (Start)
%F Recurrence: (n+1)*a(n) = (8*n-3)*a(n-1) - 7*(2*n-3)*a(n-2) + (8*n-21)*a(n-3) - (n-4)*a(n-4).
%F Recurrence: (n+1)*(2*n-3)*a(n) = (2*n-1)*(7*n-9)*a(n-1) - (2*n-3)*(7*n-5)*a(n-2) + (n-3)*(2*n-1)*a(n-3).
%F (End)
%t CoefficientList[Series[(1-4*x+x^2)/(2*x*(1-x))-Sqrt[1-6*x+x^2]/(2*x), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Mar 31 2014 *)
%o (Sage)
%o def A035011_list(n) :
%o D = [0]*(n+2); D[1] = 1
%o b = True; h = 2; R = []
%o for i in range(2*n) :
%o if b :
%o for k in range(h,0,-1) : D[k] += D[k-1]
%o else :
%o for k in range(1,h, 1) : D[k] += D[k-1]
%o R.append(D[h-2]); h += 1;
%o b = not b
%o return R
%o A035011_list(20) # _Peter Luschny_, Jun 03 2012
%Y Cf. A006318.
%K nonn
%O 0,3
%A _N. J. A. Sloane_
|
