login
A108448
Number of peaks of the form ud in all 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).
3
1, 7, 61, 575, 5641, 56695, 579125, 5984767, 62390545, 654862247, 6911195501, 73265596607, 779594526361, 8321683861015, 89070157349221, 955598531432447, 10273391096237089, 110647714508386375, 1193641560393864605
OFFSET
1,2
COMMENTS
a(n) = Sum_{k=1..n} k*A108446(n,k). Example: a(3) = 1*32 + 2*13 + 3*1 = 61.
LINKS
Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.
FORMULA
G.f.: z*A/(1-2*z*A-3*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 (the g.f. of A027307).
Recurrence: (n-1)*(2*n-1)*a(n) = (18*n^2-26*n+1)*a(n-1) + (46*n^2-225*n+276)*a(n-2) + 2*(n-3)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 18 2012
a(n) ~ sqrt(70*sqrt(5)-150)*((11+5*sqrt(5))/2)^n/(20*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 18 2012. Equivalently, a(n) ~ phi^(5*n - 2) / (2 * 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021
a(n) = Sum_{k=1..n} k*C(n-1,k-1)*C(2*n+k-1,n)/(n+k). - Vladimir Kruchinin, Mar 03 2014
a(n) = P(n-1,n,0,3), where P is the Jacobi Polynomial. - Richard Turk, Jun 27 2018
From Peter Bala, Feb 08 2024: (Start)
a(n) = Sum_{k = 0..n-1} binomial(2*n-1, k)*binomial(n-1, k)*2^k.
(n - 1)*(2*n - 1)*(10*n - 17)*a(n) = (220*n^3 - 814*n^2 + 950*n - 341)*a(n-1) + (n - 2)*(2*n - 3)*(10*n - 7)*a(n-2) with a(1) = 1 and a(2) = 7.. (End)
EXAMPLE
a(2) = 7 because in the ten paths (ud)(ud), (ud)Udd, u(ud)d, uUddd, Udd(ud), UddUdd, Ud(ud)d, UdUddd, U(ud)dd and UUdddd (see A027307) we have 7 ud's (shown between parentheses).
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/(1-2*z*A-3*z*A^2): Gser:=series(G, z=0, 25): seq(coeff(Gser, z^n), n=1..23);
MATHEMATICA
RecurrenceTable[{(n-1)*(2*n-1)*a[n]==(18*n^2-26*n+1)*a[n-1] +(46*n^2-225*n+276)*a[n-2]+2*(n-3)*(2*n-5)*a[n-3], a[1]==1, a[2]==7, a[3]==61}, a, {n, 20}] (* Vaclav Kotesovec, Oct 18 2012 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Jun 10 2005
STATUS
approved