Chapter 14 Cardinality Rules602
consisting ofkrooted trees. To add the next edge, we choose any vertex to be the
root of a new tree. Then we add an edge between this new root and the root of any
one of thek 1 subtrees that did not include the chosen vertex. So the next edge
can be chosen inn.k 1/ways to form a new spanning forest consisting ofk 1
rooted trees.
Therefore, if one multiplies together the number of choices from the first step,
the second step, etc., the total number of choices is
YnkD 2n.k 1/Dnn ^1 .n 1/ŠDnn ^2 nŠ:Equating these two formulas for the number of edge sequences, we getTnnŠ D
nn ^2 nŠ, and cancellingnŠwe arrive at Cayley’s formula
TnDnn ^2 :Generalize Pitman’s derivation to count the number of spanning forests consist-
ing ofkrooted trees onnvertices.
Exam Problems
Problem 14.25.
Suppose that two identical 52-card decks are mixed together. Write a simple for-
mula for the number of distinct permutations of the 104 cards.
Problems for Section 14.6
Class Problems
Problem 14.26.
The Tao of BOOKKEEPER: we seek enlightenment through contemplation of the
wordBOOKKEEPER.
(a)In how many ways can you arrange the letters in the wordPOKE?(b)In how many ways can you arrange the letters in the wordBO 1 O 2 K? Observe
that we have subscripted the O’s to make them distinct symbols.
(c)Suppose we map arrangements of the letters inBO 1 O 2 Kto arrangements
of the letters inBOOKby erasing the subscripts. Indicate with arrows how the
arrangements on the left are mapped to the arrangements on the right.