|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
|
|
LINKS
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|