A104547 Number of Schroeder paths of length 2n having no UHD, UHHD, UHHHD, ..., where U=(1,1), D=(1,-1), H=(2,0).

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

Author

Emeric Deutsch, Mar 14 2005

Keywords

• nonn

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

Examples

			a(2)=5 because we have HH, HUD, UDH, UDUD and UUDD (UHD does not qualify).
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A006318, A104546, A119370.

Programs

Magma

R:=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

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

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

SageMath

def A104547_list(prec):
    P. = 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

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