login
A101307
Triangle read by rows: T(n,k) is the number of ordered trees having n edges and k branches of length 2.
1
1, 1, 1, 3, 2, 7, 6, 1, 18, 18, 6, 47, 59, 24, 2, 129, 188, 96, 16, 362, 605, 369, 90, 4, 1038, 1948, 1395, 436, 45, 3022, 6305, 5164, 1981, 315, 9, 8917, 20460, 18885, 8568, 1830, 126, 26600, 66585, 68352, 35818, 9565, 1071, 21, 80098, 217186, 245497, 145796
OFFSET
1,4
COMMENTS
Row n has 1+floor(n/2) terms (n>=0).
Row sums are the Catalan numbers (A000108).
Column k=0 yields A101308.
T(2n,n) = A001006(n-1) (n>0) (the Motzkin numbers).
LINKS
Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees and branch lengths, Discrete Math., 282, 2004, 89-94.
J. Riordan, Enumeration of plane trees by branches and endpoints, J. Comb. Theory (A) 19, 1975, 214-222.
FORMULA
G.f.: G=G(t, z) satisfies G=1+P+PG(G-1), where P= z/(1-z)+(t-1)z^2 (for the explicit form see the Maple program).
EXAMPLE
Triangle begins:
1;
1, 1;
3, 2;
7, 6, 1;
18, 18, 6;
MAPLE
G:=(1+t*z^2-z^2+z^3-t*z^3-sqrt((1+t*z^2-z^2+z^3-t*z^3)*(1-4*z+3*z^2-3*t*z^2-3*z^3+3*t*z^3)))/2/z/(1-z+t*z+z^2-t*z^2): Gserz:=simplify(series(G, z=0, 16)): for n from 1 to 14 do P[n]:=sort(coeff(Gserz, z^n)) od: for n from 1 to 14 do seq(coeff(t*P[n], t^k), k=1..1+floor(n/2)) od; # yields the sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Dec 22 2004
STATUS
approved