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).

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

Vincenzo Librandi, Table of n, a(n) for n = 1..200

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

Cf. A027307, A108446, A108426, A108427.

Sequence in context: A104093 A015572 A066443 * A218473 A098659 A269731

Adjacent sequences: A108445 A108446 A108447 * A108449 A108450 A108451

Keyword

nonn,easy

Author

Emeric Deutsch, Jun 10 2005

Status

approved