JOURNAL OF COMBINATORIAL THEORY 6, 6 0  6 4
(1969)
Labeled Trees with Unlabeled EndPoints FRANK HARARY* AND ABBE MOWSHOWITZ**
Research Centerfor Group Dynamics, University of Michigan, Ann Arbor, Michigan 48104 AND JOHN RIORDAN tt
Bell Telephone Laboratories, Incorporated, Murray Hill, New Jersey 07971 1. INTRODUCTION
In structural diagrams of chemical compounds, it is customary to omit the symbol H for hydrogen, since hydrogen is always an endpoint of the diagram. This suggests the problem of the title, the enumeration of labeled trees without labels on the endpoints. Let T*(n) be the number of such trees with n points. Then T*(1) = T*(2) = 1 and, for n = 3, there is but one inner point which m a y be labeled in one way, so T*(3) = 1 also. F o r n > 2, it is convenient to enumerature by number of endpoints as well as number of points, that is, to determine T*(n) from
T*(n) = ~ R*(n, k),
n = 3, 4 ....
(1)
k=2
with R*(n, k) the number with n points and k unlabeled endpoints. It is shown that
R*(n,k)= ~(ni1) t~ k  i
R(nk,i),
k=2(1)n1,
n=3,4,...
(2) where R(n, k) is the number of trees with n labeled points, k of which are endpoints. By a result of R6nyi [4], reported in M o o n [2], and rederived in Riordan [6], n! R(n, k) = ~.. S(n  2, n  k),
k = 2(1) n  1,
n  3, 4,...
* Research supported by grant GN2544 from the National Science Foundation. Present address: Department of Computer Science, University of Toronto, Toronto, Canada. t* Present address: Rockefeller University, New York, New York 10021. 60
LABELED TREES WITH UNLABELED ENDPOINTS
61
with S(n, k) a Stirling number of the second kind, in the notation of [5]. Of course R(n, 1) = 8,1, the Kronecker delta, and R(2, 2) = I. Thus, equations (1) and (2) effectively solve the enumeration problem, but it is interesting to notice that (2) has the inverse R(n,k)=
~ (1)ki (k n i ) R * ( n +
i,i).
(3)
This may be used with the recurrence for R(n, k) (due to Versa T. S6s; see R6nyi [4]) namely kR(n, k) = (n  k) R(n  1, k  1) § k R ( n  1, k), to find the recurrence k R * ( n , k) = (n  k)[kR*(n  1, k)  (k  1) R*(n  2, k  1)] +(n
1) R * ( n   1, k  
1)
(4)
2. BASIC FORMULA Consider a tree T* belonging to the class of trees enumerated by R*(n, k). If the k (unlabeled) endpoints are removed, a new tree appears with n  k labeled points and i endpoints, enumerated by R(n  k, i). Hence any tree T* may be obtained from a tree belonging to the class R(n  k, i) by adding k lines (and associated endpoints) at the i endpoints and any of the n  k  i other points. The number of ways of doing this is the number of ways distributing k like objects into n  k unlike cells, so that i specified cells are not empty. This (cf. [5, Ch. 5]) is the coefficient of x k in (x q x 2 + ".)i(1 q x + x ~ q ...),ki = xi(1 _ x),+~, or
[nqk]=(ni1). (1)k~\ k   i ) ki This proves (2). It is worth noting that n  i 
)__(n  i  11)
1

k

'
which is the number of ways of distributing n  i like objects into n  k unlike cells with no cell empty.
62
HARARY, MOWSHOWIIZ~ AND RIORDAN
For verifications, note first that R*(n, n have but one inner point; next R*(n, 2) since the two endpoints may be regarded neighbors. For concreteness the first few R*(n,
1) = 1 since such trees R ( n  2, 2), n   4 , 5,..., as coalescing with their k) are as in Table I.
TABLE 1 R*(n, k) n
k
\\
2
3
4
5
6
7
8
1
1
1 1
3 2
12 9
60 52
1
3 1
18 4 1
360 360 136 30 5 1
3. RECURRENCES AND GENERATING FUNCTIONS In the form / n
R*(, + k, ~) = Z (1)~~ (~ _ i) R(,, i), i~2
(2) is an instance of the following pair of inverse relations: an= 2
k~O
(
P )(l)"kbk, nk
(5)
k~O
Thus (3) follows from change of notation and the proper identification of an,
bn .
Note that Cayley's formula [1] for the number of trees with n labeled points, namely T(n) = Z R(n, k) = n '~2,
and (3) lead to the identity n'~z = E (   1 ) i ( n 
i
1) R*(2n  1   i , n   t   i ) ,
n=3,4
.....
(6)
63
LABELED TREES WITH UNLABELED ENDPOINTS
Next
R*(n 6 2, 2) R(n, 2) = nR(n  1, 2)  nR*(n nt 1, 2), while the equations,
R(n, 3) = R*(n 6 3, 3)  nR*(n 6 2, 2), 3R(n, 3) = n(n  3) R(n  1, 2) + 3nR(n  1, 3), lead to 3R*(n 6 3, 3) = 3nR*(n 6 2, 3) 6 nR*(n 6 2, 2). In a similar way, 4R*(n 6 4, 4) = 4nR*(n 6 3, 4) 6 nR*(n 6 2, 2) 6 nR*(n 6 3, 3). The general formula provable by induction is
kR*(n 6 k, k) = knR*(n 6 k  1, k) 6 n[R*(n 6 2, 2) 6 " 6 R*(n 6 k  1, k  1)]. (7) F r o m (7) it follows that
kR*(n 6 k, k) = knR*(n 6 k  1, k)
(k 1) nR*(n 6 k 2, k1) 6 (n 6 k  1)R*(n 6 k   1, k  1),
(8)
which is effectively (4). Writing
Rn (x ) = ~ R*(n, k) x k it is a consequence of (4) that, with D = d/dx,
DR*(x) = [(n  1)(1 6 D)  xD2]R*_l(x )  x[(n  2 ) 0  xD2]R~_~(x),* for
n=5,6
.....
The first few values of T*(n) are as in Table II. T A B L E II
T*(n) n
... 2
T*(n) ...
1
3
4
5
6
7
8
9
10
1
2
6
25
135
892
6937
61886
In an earlier version of this note, we proposed the p r o b l e m of counting labeled graphs with unlabeled endpoints. This is solved in the sequel note by M o o n [3].
64
HARARY, MOWSHOWITZ, AND RIORDAN
The c o r r e s p o n d i n g p r o b l e m o f e n u m e r a t i n g s a t u r a t e d acyclic h y d r o carbons, CnH2~.2, (corresponding to trees in which every n o n  e n d p o i n t is labeled and has degree 4) is readily h a n d l e d by a s t r a i g h t f o r w a r d modification o f the method.
REFERENCES 1. A. CAYLEY,A Theorem on Trees, Quart J. Math. 23 (1889), 376378; Collected Papers, Cambridge, 13 (1897), 2628. 2. J. W. MooN, Various Proofs of Cayley's Formula for Counting Trees, in A Seminar on Graph Theory, (F. Harary, ed.) Holt, Rinehart & Winston, New York, 1967, pp. 7078. 3. J. W. MooN, Connected Graphs with Unlabeled EndPoints, J. Combinatorial Theory 6 0969), 6566. 4. A. R~NVt, Some Remarks on the Theory of Trees, Publ. Math. Inst. Hungar. Acad. Sci. 4 (1959), 7385. 5. J. RIORDAN, An Introduction to Combinatorial Analysis, Wiley, New York, 1958. 6. J. RIORDAN,The Enumeration of Labeled Trees by Degrees, Bull. Amer. Math. Soc. 72 (1966), 110112.