login
A104547
Number of Schroeder paths of length 2n having no UHD, UHHD, UHHHD, ..., where U=(1,1), D=(1,-1), H=(2,0).
3
1, 2, 5, 16, 60, 245, 1051, 4660, 21174, 98072, 461330, 2197997, 10585173, 51443379, 251982793, 1242734592, 6165798680, 30754144182, 154123971932, 775669589436, 3918703613376, 19866054609754, 101029857327802, 515275408644773
OFFSET
0,2
COMMENTS
A Schroeder path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1), D=(1,-1) and H=(2,0) and never going below the x-axis. Schroeder paths are counted by the large Schroeder numbers (A006318).
Equals binomial transform of A119370. - Paul D. Hanna, May 17 2006
LINKS
FORMULA
a(n) = A104546(n, 0).
G.f.: G = G(z) satisfies G = 1 + z*G + z*G(G - z/(1-z)).
G.f.: (1-2*x+2*x^2 - sqrt(1-8*x+16*x^2-12*x^3+4*x^4))/(2*x*(1-x)). - Paul D. Hanna, May 17 2006
D-finite with recurrence (n+1)*a(n) = 3*(3*n-1)*a(n-1) - 12*(2*n-3)*a(n-2) + 2*(14*n-37)*a(n-3) - 2*(8*n-31)*a(n-4) + 4*(n-5)*a(n-5). - R. J. Mathar, Jul 26 2022
EXAMPLE
a(2)=5 because we have HH, HUD, UDH, UDUD and UUDD (UHD does not qualify).
MATHEMATICA
CoefficientList[Series[(1-2*x+2*x^2 -Sqrt[1-8*x+16*x^2-12*x^3+4*x^4] )/(2*x*(1-x)), {x, 0, 40}], x] (* G. C. Greubel, Jan 02 2023 *)
PROG
(PARI) {a(n)=polcoeff(2*(1-x)/(1-2*x+2*x^2 + sqrt(1-8*x+16*x^2-12*x^3+4*x^4+x*O(x^n))), n)} \\ Paul D. Hanna, May 17 2006
(Magma) R<x>:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( (1-2*x+2*x^2 - Sqrt(1-8*x+16*x^2-12*x^3+4*x^4))/(2*x*(1-x)) )); // G. C. Greubel, Jan 02 2023
(SageMath)
def A104547_list(prec):
P.<x> = PowerSeriesRing(ZZ, prec)
return P( (1-2*x+2*x^2 - sqrt(1-8*x+16*x^2-12*x^3+4*x^4))/(2*x*(1-x)) ).list()
A104547_list(40) # G. C. Greubel, Jan 02 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Mar 14 2005
STATUS
approved