A108447 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 peaks of the form ud.

1, 1, 4, 20, 113, 688, 4404, 29219, 199140, 1385904, 9807820, 70364704, 510609620, 3741212535, 27639233548, 205660399220, 1539916433473, 11594310041792, 87725707127600, 666681174728724, 5086601816592432, 38948589882247968

Offset: 0

Author

Emeric Deutsch, Jun 10 2005

Keywords

• nonn

Comments

Column 0 of A108446.

Examples

			a(2)=4 because we have uUddd, UddUdd, UdUddd and UUdddd.
		

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..1000
• Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Crossrefs

Cf. A000108, A027307, A108446, A108425, A108426.

Programs

Maple

a:=n->(1/n)*sum(binomial(n,j)*binomial(n+2*j,j-1),j=0..n): 1, seq(a(n),n=1..25);
a := n -> `if`(n=0,1,simplify(hypergeom([1-n,(n+3)/2,(n+4)/2],[2, n+3],-4))): seq(a(n), n=0..21); # Peter Luschny, Oct 30 2015

Mathematica

Flatten[{1, Table[Sum[Binomial[n, j]*Binomial[n + 2*j, j-1], {j, 0, n}]/n, {n, 1, 20}]}] (* Vaclav Kotesovec, Nov 27 2017 *)
terms = 22; g[] = 1; Do[g[x] = 1+x*g[x]*(g[x]^2+g[x]-1) + O[x]^terms // Normal, {terms}]; CoefficientList[g[x], x] (* Jean-François Alcover, Jul 19 2018 *)

Formula

a(n) = (1/n) * Sum_{j=0..n} binomial(n, j)*binomial(n+2j, j-1) (n>=1); a(0)=1.

G.f.: G satisfies G = 1 + z*G*(G^2+G-1).

a(n) = hypergeom([1-n,(n+3)/2,(n+4)/2],[2,n+3],-4) for n>=1. - Peter Luschny, Oct 30 2015

a(n) ~ sqrt((s-1) / (Pi*(1 + 3*s))) / (2*n^(3/2) * r^(n + 1/2)), where r = 0.1215851068721183026145063923222031450327682505108... and s = 1.451605962955776643742608112028547116887657025022... are real roots of the system of equations 1 + r*s*(-1 + s + s^2) = s, r*(-1 + 2*s + 3*s^2) = 1. - Vaclav Kotesovec, Nov 27 2017

O.g.f.: A(x) = (1/x) * Revert( x/c(x/(1 - x)) ), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. of the Catalan numbers A000108. - Peter Bala, Mar 08 2020

D-finite with recurrence 8*n*(2*n+1)*a(n) -6*(2*n-1)*(13*n-10)*a(n-1) +24*(4*n-7)*(2*n-5)*a(n-2) +4*(19*n-40)*(n-3)*a(n-3) -35*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jul 26 2022