login
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.
2
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).
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
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Dec 03 2005
STATUS
approved