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.

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

Author

Emeric Deutsch, Dec 03 2005

Keywords

• nonn
• tabf

Comments

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

Examples

			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;
		

Crossrefs

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

Formula

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