A114507 -id:A114507 - cp's OEIS frontend

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

Emeric Deutsch, Dec 03 2005

nonn

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

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

Cf. A102403, A114507, A114508.

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)

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 */

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]

A114506 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n having k ascents of length 3 (0<=k<=floor(n/3)). Also number of ordered trees with n edges that have k vertices of outdegree 3.

Original entry on oeis.org

1, 1, 2, 4, 1, 10, 4, 27, 15, 79, 50, 3, 240, 168, 21, 750, 568, 112, 2387, 1959, 504, 12, 7711, 6850, 2115, 120, 25214, 24211, 8536, 825, 83315, 86164, 33858, 4620, 55, 277799, 308152, 133068, 23166, 715, 933596, 1106028, 520338, 108472, 6006

Offset: 0

Emeric Deutsch, Dec 03 2005

Row n has 1+floor(n/3) terms. Row sums yield the Catalan numbers (A000108). Column 0 yields A114507. Sum(kT(n,k),k=0..floor(n/3))=binomial(2n-4,n-3) (A001791).

			T(4,1)=4 because we have UDUUUDDD, UUUDDDUD, UUUDUDDD and UUUDDUDD, where U=(1,1), D=(1,-1).
Triangle starts:
1;
1;
2;
4,1;
10,4;
27,15;
79,50,3;
240,168,21;

Cf. A000108, A001791, A114507, A102402, A114508.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Maxima

Formula