A108427 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, 9, 85, 833, 8361, 85305, 880685, 9173505, 96220561, 1014889769, 10753517061, 114375683009, 1220435354425, 13058529727833, 140059477112925, 1505357362548737, 16209464357137953, 174827809500822345, 1888383038494338485, 20424130116241366593, 221164921352046545609, 2397512484385887298681

Offset: 1

Author

Emeric Deutsch, Jun 03 2005

Keywords

• nonn

Examples

			a(2)=9 because we have ud(Ud)d, u(Ud)dd, (Ud)dud, (Ud)d(Ud)d, (Ud)udd, (Ud)(Ud)dd, U(Ud)ddd (the peaks of the form Ud shown between parentheses).
G.f. = x + 9*x^2 + 85*x^3 + 833*x^4 + 8361*x^5 + 85305*x^6 + 880685*x^7 + ... - _Michael Somos_, Jul 01 2018
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..200
• Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.

Crossrefs

Cf. A027307, A108426.

Programs

Maple

seq(add(k*binomial(n,k)*binomial(3*n-k,n-1)/n,k=0..n),n=1..22);
a := n -> binomial(3*n-1,n-1)*hypergeom([1-n,-2*n], [1-3* n], -1); seq(round(evalf(a(n),32)), n=1..22); # Peter Luschny, Oct 06 2015

Mathematica

Table[1/n*Sum[k*Binomial[n, k]*Binomial[3n - k, n-1], {k, 0, n}], {n, 1, 20}] (* Vaclav Kotesovec, Oct 17 2012 *)
a[n_] :=  HypergeometricPFQ[{-n, n, -n + 1}, {1/2, 1}, 1];
Table[a[n], {n, 1, 22}] (* Peter Luschny, Mar 14 2018 *)
a[ n_] := JacobiP[n - 1, n + 1, 0, 3]; (* Michael Somos, Jul 01 2018 *)

Maxima

G(z):=z*((2/3)*sqrt((z+3)/z)*sin((1/3)*asin(sqrt(z)*(z+18) / (z+3)^(3/2)))+2/3);
taylor(diff(G(z),z,1)/G(z)-1/z,z,0,20); /* Vladimir Kruchinin, Oct 06 2015 */

PARI

a(n) = (1/n)*sum(k=0,n,k*binomial(n, k)*binomial(3*n-k, n-1)); \\ Joerg Arndt, May 15 2013

Formula

a(n) = (1/n)*Sum_{k=0..n} k*binomial(n, k)*binomial(3n-k, n-1).

Recurrence: 9*n*(2*n-3)*a(n) = (202*n^2 - 414*n + 185)*a(n-1) - (26*n^2 - 175*n + 255)*a(n-2) - 2*(n-3)*(2*n-5)*a(n-3), for n>3. - Vaclav Kotesovec, Oct 17 2012

a(n) ~ sqrt(30*sqrt(5)-50)*((11+5*sqrt(5))/2)^n/(20*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 17 2012. Equivalently, a(n) ~ phi^(5*n - 1) / (2* 5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 07 2021

G.f.: A(x) = 1/2*(x*B'(x)/B(x)-1), where B(x) satisfies B(x) = x*((1-2*B(x))/(2*(1-4*B(x))) + 1/(2*sqrt(1-4*B(x)))). - Vladimir Kruchinin, Oct 06 2015

a(n) = binomial(3*n-1, n-1)*hypergeom([1-n, -2*n], [1-3*n], -1). - Peter Luschny, Oct 06 2015

a(n) = hypergeom([-n, n, -n + 1], [1/2, 1], 1). - Peter Luschny, Mar 14 2018

a(n) = P(n-1, n+1, 0, 3), where P is the Jacobi Polynomial. - Richard Turk, Jun 25 2018