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,3

Comments

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

Links

Table of n, a(n) for n=0..26.

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. [From Vladimir Kruchinin, Mar 07 2011]

Example

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

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)

Prog

(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); [Vladimir Kruchinin, Mar 07 2011]

Crossrefs

Cf. A102403, A114507, A114508.

Sequence in context: A126031 A151416 A193114 * A003080 A149854 A151442

Adjacent sequences: A114506 A114507 A114508 * A114510 A114511 A114512

Keyword

nonn

Author

Emeric Deutsch, Dec 03 2005

Status

approved