A108444 Number of triple descents (i.e., ddd's) 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).

5, 73, 857, 9505, 103341, 1114969, 11996209, 128989249, 1387480981, 14937170089, 160978217225, 1736820843233, 18760031574077, 202856430706617, 2195832009812065, 23792481053343361, 258038743598973477

Offset

2,1

Links

Vaclav Kotesovec, Table of n, a(n) for n = 2..100

Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.

Formula

a(n) = Sum_{k=1..2n-1} k*A108443(n,k). Example: a(3) = 1*24 + 2*15 + 3*3 + 4*1 = 73.

G.f.: zA(2A^2-2zA^2-zA-2)/(1-2zA-3zA^2), where A=1+zA^2+zA^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*(2*n+1)*(40*n^5 - 100*n^4 - 758*n^3 + 3649*n^2 - 5474*n + 2727)*a(n) = (880*n^7 - 2200*n^6 - 15316*n^5 + 79354*n^4 - 145332*n^3 + 125379*n^2 - 48111*n + 5220)*a(n-1) + (n-3)*(2*n - 5)*(40*n^5 + 100*n^4 - 758*n^3 + 1175*n^2 - 650*n + 84)*a(n-2). - Vaclav Kotesovec, Mar 18 2014

a(n) ~ 5^(3/4) * ((11+5*sqrt(5))/2)^n / (10*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 18 2014

Example

a(2)=5 because in the ten paths udud, udUdd, uudd, uU(ddd), Uddud, UddUdd, Ududd, UdU(ddd), Uu(ddd) and UU(d[dd)d] (see A027307) we have 5 ddd'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*(-z*A-2*z*A^2-2+2*A^2)/(1-3*z*A^2-2*z*A): Gser:=series(G, z=0, 26): seq(coeff(Gser, z^n), n=2..21);

Crossrefs

Cf. A027307, A108443.

Sequence in context: A248046 A059017 A099667 * A155662 A182328 A222352

Adjacent sequences: A108441 A108442 A108443 * A108445 A108446 A108447

Keyword

nonn

Author

Emeric Deutsch, Jun 10 2005

Status

approved