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

%I #8 May 09 2012 08:51:31

%S 1,1,2,5,13,37,111,345,1104,3611,12016,40548,138414,477076,1657956,

%T 5802920,20436910,72369903,257518806,920333307,3302003826,11888979066,

%U 42944410207,155576009845,565127618392,2057903975752,7510967300206

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

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

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

%F 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]

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

%p 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)

%o (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]

%Y Cf. A102403, A114507, A114508.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Dec 03 2005