A104550 Number of horizontal segments in all Schroeder paths of length 2n (a horizontal segment is a maximal string of horizontal steps).

1, 4, 20, 104, 552, 2972, 16172, 88720, 489872, 2719028, 15157188, 84799992, 475894200, 2677788492, 15102309468, 85347160608, 483183316512, 2739851422820, 15558315261812, 88462135512712, 503569008273992, 2869602773253884, 16368396446913420, 93449566652932784, 533954950648248752

Offset: 1

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

Examples

			a(2)=4 because we have (HH),(H)UD,UD(H),U(H)D,UDUD and UUDD; the 4 horizontal segments are shown between parentheses.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..200

Crossrefs

Cf. A006318, A104549, A002002 (partial sums).

Cf. A035028.

Programs

Maple

G:=(1-z)*(1-z-sqrt(1-6*z+z^2))/2/sqrt(1-6*z+z^2): Gser:=series(G,z=0,28): seq(coeff(Gser,z^n),n=1..24);
a := n -> hypergeom([-n, n-1], [1], -1);
seq(round(evalf(a(n),36)),n=1..23); # Peter Luschny, Aug 02 2014

Mathematica

Rest[CoefficientList[Series[(1-x)*(1-x-Sqrt[1-6*x+x^2])/ (2*Sqrt[1 -6*x+x^2]), {x, 0, 20}], x]] (* Vaclav Kotesovec, Oct 17 2012 *)

Maxima

a(n):=sum(binomial(n+1,k)*binomial(n+k-1,k),k,0,n+1); /* Vladimir Kruchinin, Jun 15 2020 */

PARI

x='x+O('x^66); Vec((1-x)*(1-x-sqrt(1-6*x+x^2))/(2*sqrt(1-6*x+x^2))) \\ Joerg Arndt, May 13 2013

Formula

G.f.: (1-x)*(1-x-sqrt(1-6*x+x^2))/(2*sqrt(1-6*x+x^2)).

a(n) = Jacobi_P(n+1,-1,-2,3). [Paul Barry, Sep 27 2009]

Recurrence: n*a(n) = (7*n-6)*a(n-1) - (7*n-22)*a(n-2) + (n-4)*a(n-3). - Vaclav Kotesovec, Oct 17 2012

a(n) ~ sqrt(6*sqrt(2)-8)*(3+2*sqrt(2))^n/(2*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 17 2012

a(n) = Hyper2F1([-n, n-1], [1], -1). - Peter Luschny, Aug 02 2014

a(n) = Sum_{k=0..n+1} C(n+1,k)*C(n+k-1,k). - Vladimir Kruchinin, Jun 15 2020