Labeled trees with unlabeled end-points

Labeled trees with unlabeled end-points

JOURNAL OF COMBINATORIAL THEORY 6, 6 0 - 6 4 (1969) Labeled Trees with Unlabeled End-Points FRANK HARARY* AND ABBE MOWSHOWITZ** Research Centerfor ...

139KB Sizes 0 Downloads 21 Views

JOURNAL OF COMBINATORIAL THEORY 6, 6 0 - 6 4

(1969)

Labeled Trees with Unlabeled End-Points 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 end-point of the diagram. This suggests the problem of the title, the enumeration of labeled trees without labels on the end-points. 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 end-points 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 end-points. It is shown that

R*(n,k)= ~(n--i--1) t~ k -- i

R(n--k,i),

k=2(1)n--1,

n=3,4,...

(2) where R(n, k) is the number of trees with n labeled points, k of which are end-points. 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 GN-2544 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 END-POINTS

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)k-i (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) end-points are removed, a new tree appears with n -- k labeled points and i end-points, 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 end-points) 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- ...),-k-i = xi(1 _ x)-,+~, or

[--nq-k]=(n--i--1). (--1)k-~\ k - - i ) k--i 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 end-points 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, n--k

(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 END-POINTS

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, k--1) 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 end-points. 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), 376-378; Collected Papers, Cambridge, 13 (1897), 26-28. 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. 70-78. 3. J. W. MooN, Connected Graphs with Unlabeled End-Points, J. Combinatorial Theory 6 0969), 65-66. 4. A. R~NVt, Some Remarks on the Theory of Trees, Publ. Math. Inst. Hungar. Acad. Sci. 4 (1959), 73-85. 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), 110-112.