A108424 Number of paths from (0,0) to (3n,0) that stay in the first quadrant, consist of steps u=(2,1), U=(1,2), or d=(1,-1) and do not touch the x-axis, except at the endpoints.

2, 6, 34, 238, 1858, 15510, 135490, 1223134, 11320066, 106830502, 1024144482, 9945711566, 97634828354, 967298498358, 9659274283650, 97119829841854, 982391779220482, 9990160542904134, 102074758837531810, 1047391288012377774, 10788532748880319298

Offset

1,1

Comments

These are the large nu-Schröder numbers with nu=NE(NEE)^(n-1). - Matias von Bell, Jun 02 2021

Links

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

Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

M. von Bell and M. Yip, Schröder combinatorics and nu-associahedra, arXiv:2006.09804 [math.CO], 2020.

Formula

a(n) = A027307(n-1) + A032349(n).

G.f.: z*A+z*A^2, where A=1+z*A^2+z*A^3 or, equivalently, A=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3.

a(n) = (n*2^n*C(2*n, n)/((2n-1)(n+1))) * Sum_{j=0..n-1} (C(n-1, j))^2 / (2^j*C(n+j+1,j)).

Recurrence: n*(2*n-1)*a(n) = 3*(6*n^2-10*n+3)*a(n-1) + (46*n^2-227*n+279)*a(n-2) + 2*(n-3)*(2*n-7)*a(n-3). - Vaclav Kotesovec, Oct 17 2012

a(n) ~ sqrt(30*sqrt(5) - 50)*((11 + 5*sqrt(5))/2)^n/(20*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012

a(n) = Sum_{i=0..n} (2*n+i-2)!/((n-i)!*(n+i-1)!*i!), n>0. - Vladimir Kruchinin, Feb 16 2013

From Matias von Bell, Jun 02 2021: (Start)

a(n) = 2*Sum_{i>=0} (1/n)*binomial(2*n-2,i)*binomial(3*n-2-i,2*n-1).

a(n) = 2*A344553(n). (End)

a(n) = 2*binomial(3*n - 2, 2*n - 1)*hypergeom([2 - 2*n, 1 - n], [2 - 3*n], -1) / n. - Peter Luschny, Jun 14 2021

From Peter Bala, Jun 17 2023: (Start)

a(n) = (-1)^(n+1) * (1/((d-1)*n + 1))*Sum_{i = 0..n} binomial((d - 1)*n+1, n-i) * binomial((d-1)*n+i, i), with d = -1.

P-recursive: n*(2*n - 1)*(5*n - 8)*a(n) = (110*n^3 - 396*n^2 + 445*n - 150)*a(n-1) + (n - 2)*(2*n - 5)*(5*n - 3)*a(n-2) with a(1) = 2 and a(2) = 6.

The g.f. A(x) = 2*x + 6*x^2 + 34*x^3 + .... Then 1/(1 - A(x)) = 1 + 2*x + 10*x^2 + 66*x^3 + .. is the g.f. of A027307.

(1/x) * the series reversion of x*(1 - A(x)) = 1 + 2*x + 14*x^2 + 134*x^3 + ... is the g.f. of A144097.

(1/x) * the series reversion of x/(1 - A(x)) = 1 - 2*x - 2*x^2 - 6*x^3 - 22*x^4 - 90*x^5 - ... = 1 - x - x*S(x), where S(x) is the g.f. of A006318. (End)

Example

a(2) = 6 because we have uudd, uUddd, Ududd, UdUddd, Uuddd and UUdddd.

Maple

A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3: G:=z*A+z*A^2: Gser:=series(G, z=0, 28): seq(coeff(Gser, z^n), n=1..25);
a:=proc(n) if n=1 then 2 else (n*2^n*binomial(2*n, n)/((2*n-1)*(n+1)))*sum(binomial(n-1, j)^2/2^j/binomial(n+j+1, j), j=0..n-1) fi end: seq(a(n), n=1..19);
# Alternative:
a := n -> 2*binomial(3*n - 2, 2*n - 1)*hypergeom([2 - 2*n, 1 - n], [2 - 3*n], -1)/n:
seq(simplify(a(n)), n = 1..21); # Peter Luschny, Jun 14 2021

Mathematica

Table[(n*2^n*Binomial[2*n, n]/((2n-1)*(n+1))) * Sum[(Binomial[n-1, j])^2/ (2^j * Binomial[n+j+1, j]), {j, 0, n-1}], {n, 1, 20}] (* Vaclav Kotesovec, Oct 17 2012 *)

Crossrefs

Cf. A027307, A032349, A344553.

Cf. A006318 (d = 2, signed version at d = 0), A027307 (d = 3), A144097 (d = 4), A260332 (d = 5, conjecturally), A363006 (d = 6).

Sequence in context: A371768 A019029 A019032 * A364394 A328884 A002685

Adjacent sequences: A108421 A108422 A108423 * A108425 A108426 A108427

Keyword

nonn

Author

Emeric Deutsch, Jun 03 2005

Status

approved