|
| |
|
|
A104550
|
|
Number of horizontal segments in all Schroeder paths of length 2n (a horizontal segment is a maximal string of horizontal steps).
|
|
3
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,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).
|
|
|
LINKS
|
|
|
|
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
|
|
|
EXAMPLE
|
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.
|
|
|
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 *)
|
|
|
PROG
|
(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
(Maxima) a(n):=sum(binomial(n+1, k)*binomial(n+k-1, k), k, 0, n+1) /* Vladimir Kruchinin, Jun 15 2020 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
