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, 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

Author

Emeric Deutsch, Dec 25 2006, Aug 17 2008

Keywords

• nonn
• tabf

Comments

Row n has floor(n/2) terms (n >= 2).

Row sums are the Catalan numbers (A000108).

Examples

			Triangle starts:
     1;
     2;
     5;
    14;
    40,   2;
   116,  16;
   344,  80,   5;
  1040, 340,  50;
		

Crossrefs

Cf. A000108, A002696, A126220.

Programs

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

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).