A035011 A006318(n) - 1.

0, 1, 5, 21, 89, 393, 1805, 8557, 41585, 206097, 1037717, 5293445, 27297737, 142078745, 745387037, 3937603037, 20927156705, 111818026017, 600318853925, 3236724317173

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

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

Links

• Fung Lam, Table of n, a(n) for n = 0..1300

Crossrefs

Cf. A006318.

Programs

Mathematica

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

Sage

def A035011_list(n) :
    D = [0]*(n+2); D[1] = 1
    b = True; h = 2; R = []
    for i in range(2*n) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
        else :
            for k in range(1,h, 1) : D[k] += D[k-1]
            R.append(D[h-2]); h += 1;
        b = not b
    return R
A035011_list(20) # Peter Luschny, Jun 03 2012

Formula

G.f.: (1-4*z+z^2)/(2*z*(1-z))-sqrt(1-6*z+z^2)/(2*z). - Emeric Deutsch, Dec 28 2003

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

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

From Vaclav Kotesovec, Mar 31 2014: (Start)

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

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

(End)