login
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
OFFSET
0,2
COMMENTS
Row n has floor(n/2) terms (n >= 2).
Row sums are the Catalan numbers (A000108).
FORMULA
T(n,0) = A126220(n).
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
Emeric Deutsch, Dec 25 2006, Aug 17 2008
STATUS
approved