A114507 Number of Dyck paths of semilength n having no ascents of length 3.

1, 1, 2, 4, 10, 27, 79, 240, 750, 2387, 7711, 25214, 83315, 277799, 933596, 3159187, 10755190, 36811479, 126594819, 437220744, 1515844359, 5273760446, 18406122609, 64426136558, 226108087891, 795486834627, 2804993559426, 9911529800630, 35090946422404, 124462137097349

Offset: 0

Author

Emeric Deutsch, Dec 03 2005

Keywords

• nonn

Comments

Also number of ordered trees with n edges that have no vertices of outdegree 3.

Examples

			a(3) = 4 because we have UDUDUD, UDUUDD, UUDDUD and UUDUDD, where U=(1,1), D=(1,-1).
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A102403, A114506, A114509.

Programs

Maple

Order:=36: Y:=solve(series((Y-Y^2)/(1-Y^3+Y^4),Y)=z,Y): seq(coeff(Y,z^n),n=1..32); #(Y=zG)

Maxima

a114507(n):= 1/n*sum(binomial(n,j)*binomial(4*j-2*n-2, j-1) *(-1)^(n-j),j,ceiling((n+1)/2),n); /* Works for n > 0. Returns a(n-1). Vladimir Kruchinin, Mar 07 2011 */

PARI

a(n)={n++; sum(j=n\2+1, n, binomial(n, j)*binomial(4*j-2*n-2, j-1)*(-1)^(n-j))/n} \\ Andrew Howroyd, Jan 24 2025

Formula

G.f. G satisfies z^4*G^4-z^3*G^3+zG^2-G+1=0.

a(n-1) = 1/n*sum(j=ceiling((n+1)/2)..n, binomial(n,j)*binomial(4*j-2*n-2,j-1)*(-1)^(n-j)) n>0. - Vladimir Kruchinin, Mar 07 2011

D-finite with recurrence 2*n*(26405927*n-73197215)*(2*n+3)*(n+1)*a(n) +2*n*(2*n+1)*(26405927*n^2-273126414*n+480676927)*a(n-1) +4*(-793701648*n^4+4928830819*n^3-11073984912*n^2+10499531162*n-3092762541)*a(n-2) +2*(375778330*n^4-3447814000*n^3+22123257551*n^2-60324066977*n+51211836006)*a(n-3) +2*(12664700570*n^4-145150764350*n^3+621947195977*n^2-1179232268341*n+833841845214)*a(n-4) -3*(n-4)*(11017381441*n^3-111829680906*n^2+390445674963*n-461862831838)*a(n-5) -(n-4)*(n-5)*(30888861033*n^2-148676625095*n+156786419682)*a(n-6) +3206*(n-5)*(n-6)*(18970222*n-55906401)*(n-4)*a(n-7)=0. - R. J. Mathar, Jul 26 2022

Extensions

a(27) onwards from Andrew Howroyd, Jan 24 2025