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

Author

Emeric Deutsch, Dec 20 2006

Keywords

• nonn

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

Examples

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

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.

Crossrefs

Cf. A006319, A090981, A008288, A026002, A190666.

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

Programs

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

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

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) = A026002(n) - A190666(n-2) for n >= 2. - Shel Kaphan, Mar 24 2023

a(n) = ((n+1)/2) * A006319(n-1). - Vladimir Kruchinin, Apr 27 2024