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

1, 1, 2, 5, 13, 1, 37, 5, 111, 21, 345, 84, 1104, 322, 4, 3611, 1215, 36, 12016, 4555, 225, 40548, 17028, 1210, 138414, 63636, 5940, 22, 477076, 238004, 27534, 286, 1657956, 891268, 122850, 2366, 5802920, 3342375, 533625, 15925, 20436910, 12552580

Offset

0,3

Comments

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

Links

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

Formula

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

Example

T(5,1)=5 because we have UDUUUUDDDD, UUUDDDDUD, UUUUDDDUDD, UUUUDDUDDD and UUUUDUDDDD, where U=(1,1), D=(1,-1).
Triangle starts:
1;
1;
2;
5;
13,1;
37,5;
111,21;
345,84;
1104,322,4;
3611,1215,36;

Maple

Order:=20: Y:=solve(series((Y-Y^2)/(1-(1-t)*Y^4+(1-t)*Y^5), Y)=z, Y): 1; for n from 1 to 17 do seq(coeff(t*coeff(Y, z^(n+1)), t^j), j=1..1+floor(n/4)) od; # yields sequence in triangular form

Crossrefs

Cf. A102402, A114506, A000108, A002054, A114509.

Sequence in context: A135309 A135331 A135329 * A243366 A139023 A241758

Adjacent sequences: A114505 A114506 A114507 * A114509 A114510 A114511

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 03 2005

Status

approved