login
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.
14
1, 1, 4, 20, 113, 688, 4404, 29219, 199140, 1385904, 9807820, 70364704, 510609620, 3741212535, 27639233548, 205660399220, 1539916433473, 11594310041792, 87725707127600, 666681174728724, 5086601816592432, 38948589882247968
OFFSET
0,3
COMMENTS
Column 0 of A108446.
LINKS
Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.
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
EXAMPLE
a(2)=4 because we have uUddd, UddUdd, UdUddd and UUdddd.
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jun 10 2005
STATUS
approved