A101276 Triangle read by rows: T(n,k) is the number of ordered trees having n edges and k branches of length 1.

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, 860, 2310, 4771, 6660, 10451, 7469, 12644, 2907, 8350, 0, 2188

Offset: 0

Author

Emeric Deutsch, Dec 20 2004

Keywords

• nonn
• tabl

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

Examples

			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.
		

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.

Crossrefs

Cf. A000108, A001006, A026418.

Programs

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

Mathematica

m = 12; G[_] = 0;
Do[G[z_] = (1 + t z - t z^2 - z + z^2 + G[z]^2 (t z - t z^2 + z^2))/(1 + t z - t z^2 - z + z^2) + O[z]^m, {m}];
CoefficientList[#, t]& /@ CoefficientList[G[z], z] // Flatten (* Jean-François Alcover, Nov 15 2019 *)

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.