OFFSET
0,3
COMMENTS
A Schroeder path of length 2n is a lattice path in the first quadrant, from the origin to the point (2n, 0) and consisting of steps U = (1, 1), D = (1, -1) and H = (2, 0); an ascent in a Schroeder path is a maximal strings of U steps.
a(n) is the number of points at L1 distance n - 2 from any point in Z^n, for n >= 2. - Shel Kaphan, Mar 24 2023
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..400
Emanuele Munarini, Combinatorial properties of the antichains of a garland, Integers, 9 (2009), 353-374.
FORMULA
a(n) = Sum_{k=0..n} k * A090981(n, k).
G.f.: z*R*(1 + z*R)/sqrt(1 - 6*z + z^2), where R = 1 + z*R + z*R^2, i.e., R = (1 - z -sqrt(1 - 6*z + z^2))/(2*z).
D-finite Recurrence: 2*n*(17*n - 26)*a(n) = 3*(68*n^2 - 137*n + 66)*a(n-1) - 2*(17*n^2 - 34*n - 48)*a(n-2) + 3*(n - 4)*a(n-3). - Vaclav Kotesovec, Oct 19 2012
a(n) ~ 2^(-3/4)*(3 + 2*sqrt(2))^n/sqrt(Pi*n). - Vaclav Kotesovec, Oct 19 2012
a(n) = Sum_{i=0..n-1} binomial(n+1, n-i-1) * binomial(n+i, n). - Vladimir Kruchinin, Feb 05 2013
a(n) = (n*(n+1)/2)*hypergeometric([1-n, n+1], [3], -1). - Peter Luschny, Sep 17 2014
a(n) = ((n+1)/2) * A006319(n-1). - Vladimir Kruchinin, Apr 27 2024
EXAMPLE
a(2) = 6 because the Schroeder paths of length 4 are HH, H(U)D, (U)DH, (U)D(U)D, (U)HD and (UU)DD, having a total of 6 ascents (shown between parentheses).
MAPLE
R:=(1-z-sqrt(1-6*z+z^2))/2/z: G:=z*R*(1+z*R)/sqrt(1-6*z+z^2): Gser:=series(G, z=0, 30): seq(coeff(Gser, z, n), n=0..25);
# second Maple program:
a:= proc(n) option remember;
`if`(n<3, [0, 1, 6][n+1], ((204*n^2-411*n+198)*a(n-1)
+(-34*n^2+68*n+96)*a(n-2) +(3*n-12)*a(n-3))/(2*n*(17*n-26)))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Oct 20 2012
MATHEMATICA
CoefficientList[Series[x*(1-x-Sqrt[1-6*x+x^2])/(2*x)*(1+x*(1-x-Sqrt[1-6*x+x^2])/(2*x))/Sqrt[1-6*x+x^2], {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 19 2012 *)
a[n_] := Sum[ Binomial[n+1, n-i-1]*Binomial[n+i, n], {i, 0, n-1}]; (* or *) a[n_] := Hypergeometric2F1[1-n, 1+n, 3, -1]*n*(n+1)/2; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Feb 05 2013, after Vladimir Kruchinin *)
PROG
(Sage)
A125190 = lambda n : (n^2+n)*hypergeometric([1-n, n+1], [3], -1)/2
[round(A125190(n).n(100)) for n in (0..23)] # Peter Luschny, Sep 17 2014
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 20 2006
STATUS
approved