A125190 Number of ascents in all Schroeder paths of length 2n.

0, 1, 6, 32, 170, 912, 4942, 27008, 148626, 822560, 4573910, 25534368, 143027898, 803467056, 4524812190, 25537728000, 144411206178, 818017823808, 4640757865126, 26364054632480, 149959897539018, 853941394691792, 4867745532495086, 27773897706129792

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*A090981(n,k), k=0..n).

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^2+n)*hypergeometric([1-n, n+1], [3], -1)/2. - Peter Luschny, Sep 17 2014

a(n) = A026002(n) - A190666(n-2) for n>=2. - Shel Kaphan, Mar 24 2023

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

Cf. A090981, A008288, A026002, A190666.

-2-diagonal of A266213 for n>=1.

Sequence in context: A199699 A306900 A137637 * A264460 A180037 A277742

Adjacent sequences: A125187 A125188 A125189 * A125191 A125192 A125193

Keyword

nonn

Author

Emeric Deutsch, Dec 20 2006

Status

approved