A114509 Number of Dyck paths of semilength n having no ascents of length 4.

1, 1, 2, 5, 13, 37, 111, 345, 1104, 3611, 12016, 40548, 138414, 477076, 1657956, 5802920, 20436910, 72369903, 257518806, 920333307, 3302003826, 11888979066, 42944410207, 155576009845, 565127618392, 2057903975752, 7510967300206

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

Examples

			a(4) = 13 because among the Catalan(4)=14 Dyck paths of semilength 4 only UUUUDDDD has an ascent of length 4 (here U=(1,1), D=(1,-1)).
		

Crossrefs

Cf. A102403, A114507, A114508.

Programs

Maple

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

Maxima

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

Formula

G.f.: G=G(z) satisfies z^5*G^5-z^4*G^4+zG^2-G+1=0.

a(n) = (1/n)*sum(j=ceiling((3*n+2)/5)..n, C(n,j)*C(5*j-3*n-2,j-1) * (-1)^(n-j)), n>0. [Vladimir Kruchinin, Mar 07 2011]