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

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

Links

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

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.

Example

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.

Sequence in context: A271206 A211244 A228337 * A114848 A135330 A135328

Adjacent sequences: A114503 A114504 A114505 * A114507 A114508 A114509

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 03 2005

Status

approved