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
Keywords
Examples
a(2) = 6 because we have uudd, uUddd, Ududd, UdUddd, Uuddd and UUdddd.
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.
Crossrefs
Programs
-
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 *)
Formula
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)
Comments