|
|
A101276
|
|
Triangle read by rows: T(n,k) is the number of ordered trees having n edges and k branches of length 1.
|
|
0
|
|
|
1, 0, 1, 1, 0, 1, 1, 2, 0, 2, 2, 2, 6, 0, 4, 3, 8, 6, 16, 0, 9, 6, 14, 30, 16, 45, 0, 21, 11, 36, 54, 106, 45, 126, 0, 51, 22, 74, 168, 196, 360, 126, 357, 0, 127, 43, 173, 372, 706, 675, 1197, 357, 1016, 0, 323, 87, 378, 981, 1636, 2775, 2268, 3913, 1016, 2907, 0, 835, 176
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
COMMENTS
|
Row n has n+1 terms (n>=0). Row sums are the Catalan numbers (A000108). Column 0 yields A026418. T(n,n)=A001006(n-1) (n>0) (the Motzkin numbers).
|
|
REFERENCES
|
E. 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.
|
|
LINKS
|
Table of n, a(n) for n=0..66.
|
|
FORMULA
|
G.f. G=G(t, z) satisfies z(t+z-tz)G^2-(1-z+tz+z^2-tz^2)G+1-z+tz+z^2-tz^2=0.
|
|
EXAMPLE
|
T(3,1)=2 because we have the tree with three edges hanging from the root and the tree with one edge hanging from the root at the end of which two edges are hanging.
|
|
MAPLE
|
G := 1/2/(-z^2+t*z^2-t*z)*(-1+z-t*z-z^2+t*z^2+sqrt(1-3*t^2*z^2-8*t*z^3+6*t^2*z^3+6*z^4*t-3*t^2*z^4-2*t*z-z^2-3*z^4+2*z^3-2*z+4*t*z^2)): Gser:=simplify(series(G, z=0, 13)): P[0]:=1: for n from 1 to 11 do P[n]:=coeff(Gser, z^n) od: for n from 0 to 11 do seq(coeff(t*P[n], t^k), k=1..n+1) od; # yields the sequence in triangular form
|
|
CROSSREFS
|
Cf. A000108, A000106, A026418.
Sequence in context: A199123 A207944 A063088 * A103863 A166395 A061199
Adjacent sequences: A101273 A101274 A101275 * A101277 A101278 A101279
|
|
KEYWORD
|
nonn,tabl
|
|
AUTHOR
|
Emeric Deutsch, Dec 20 2004
|
|
STATUS
|
approved
|
|
|
|