|
|
A126219
|
|
Triangle read by rows: T(n,k) is the number of binary trees (i.e., a rooted tree where each vertex has either 0, 1, or 2 children; and, when only one child is present, it is either a right child or a left child) with n edges and k pairs of adjacent vertices of outdegree 2.
|
|
1
|
|
|
1, 2, 5, 14, 40, 2, 116, 16, 344, 80, 5, 1040, 340, 50, 3188, 1360, 300, 14, 9880, 5264, 1484, 168, 30912, 19880, 6776, 1176, 42, 97520, 73728, 29568, 6608, 588, 309856, 269952, 124656, 33600, 4704, 132, 990656, 979264, 511584, 161280, 29544, 2112
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Row n has floor(n/2) terms (n >= 2).
Row sums are the Catalan numbers (A000108).
|
|
LINKS
|
|
|
FORMULA
|
Sum_{k=0..floor(n/2)-1} k*T(n,k) = 2*binomial(2n-2,n-4) = 2*A002696(n-1) (n >= 4).
G.f.: G = G(t,z) satisfies G = 1 + 2zG + z^2*(1 + 2zG + t(G - 2zG - 1))^2 (see the Maple program for the explicit expression).
|
|
EXAMPLE
|
Triangle starts:
1;
2;
5;
14;
40, 2;
116, 16;
344, 80, 5;
1040, 340, 50;
|
|
MAPLE
|
G:=1/2*(1-4*z^3*t^2-4*z^3-2*z^2*t+8*z^3*t-2*z+2*z^2*t^2-sqrt(1-8*z^3+4*z^2-4*z^2*t-4*z+8*z^3*t))/z^2/(2*z*t-t-2*z)^2: Gser:=simplify(series(G, z=0, 18)): for n from 0 to 14 do P[n]:=sort(coeff(Gser, z, n)) od: 1; 2; for n from 2 to 14 do seq(coeff(P[n], t, j), j=0..floor(n/2)-1) od; # yields sequence in triangular form
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|