A108432 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1),U=(1,2), or d=(1,-1) and have no hills (a hill is either a ud or a Udd starting at the x-axis).

1, 0, 6, 34, 274, 2266, 19738, 177642, 1640050, 15445690, 147813706, 1433309194, 14052298690, 139063589370, 1387288675002, 13936344557354, 140859338668306, 1431424362057018, 14616361066692778, 149892742974500042, 1543146417012350050, 15942622531081651578

Offset: 0

Author

Emeric Deutsch, Jun 03 2005

Keywords

• nonn
• nice

Comments

Column 0 of A108431.

The radius of convergence of g.f. y(x) is r = (5*sqrt(5)-11)/2, with y(r) = (11*sqrt(5)+23)/38. - Vaclav Kotesovec, Mar 17 2014

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..960 (first 151 terms from Vaclav Kotesovec)
• Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Crossrefs

Cf. A027307, A108431, A108433.

Programs

Maple

g:=1/(1+2*z-z*A-z*A^2): A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3:gser:=series(g,z=0,27): 1,seq(coeff(gser,z^n),n=1..24);
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, `if`(t and y=1, 0, b(x-1, y-1, t))+
      b(x-1, y+2, is(y=0))+b(x-2, y+1, is(y=0))))
    end:
a:= n-> b(3*n, 0, false):
seq(a(n), n=0..25);  # Alois P. Heinz, Oct 06 2015

Mathematica

CoefficientList[Series[9/(3 + 18*x + 2*(3+x)*Cos[2/3*ArcSin[Sqrt[x]*(18+x)/(3+x)^(3/2)]] - 2*x*Sqrt[(3+x)/x]*Sin[1/3*ArcSin[Sqrt[x]*(18+x)/(3+x)^(3/2)]]), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 17 2014 *)

PARI

{a(n)=local(y=1); for(i=1, n, y=-(-1 + 6*x*y - 5*x*y^2 - 12*x^2*y^2 - x*y^3 + 6*x^2*y^3 + 8*x^3*y^3) + (O(x^n))^3); polcoeff(y, n)}
for(n=0, 20, print1(a(n), ", ")) \\ Vaclav Kotesovec, Mar 17 2014

Formula

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

G.f. y(x) satisfies: -1 + y + 6*x*y - 5*x*y^2 - 12*x^2*y^2 - x*y^3 + 6*x^2*y^3 + 8*x^3*y^3 = 0. - Vaclav Kotesovec, Mar 17 2014

a(n) ~ (11+5*sqrt(5))^n * sqrt(273965 + 122523*sqrt(5)) / (361 * sqrt(5*Pi) * n^(3/2) * 2^(n+3/2)). - Vaclav Kotesovec, Mar 17 2014

D-finite with recurrence 4*n*(2*n+1)*a(n) +3*(-70*n^2+83*n-34)*a(n-1) +11*(154*n^2-436*n+327)*a(n-2) +3*(-1042*n^2+4875*n-4627)*a(n-3) +2*(-4016*n^2+18260*n-21399)*a(n-4) +12*(-206*n^2+1383*n-2322)*a(n-5) -80*(n-4)*(2*n-9)*a(n-6)=0. - R. J. Mathar, Jul 26 2022