14.11. References 601
(a)For how many rolls doexactlytwo dice have the value 6 and the remaining
five dice all have different values? Remember to describe a bijection and write a
simple arithmetic formula.
Example:.6;2;6;1;3;4;5/is a roll of this type, but.1;1;2;6;3;4;5/and.6;6;1;2;4;3;4/
are not.
(b)For how many rolls do two dice have the same value and the remaining five
dice all have different values? Remember to describe a bijection and write a simple
arithmetic formula.
Example:.4;2;4;1;3;6;5/is a roll of this type, but.1;1;2;6;1;4;5/and.6;6;1;2;4;3;4/
are not.
(c)For how many rolls do two dice have one value, two different dice have a
second value, and the remaining three dice a third value? Remember to describe a
bijection and write a simple arithmetic formula.
Example:.6;1;2;1;2;6;6/is a roll of this type, but.4;4;4;4;1;3;5/and.5;5;5;6;6;1;2/
are not.
Problem 14.24(Counting trees).
8
What is the numberTnof different trees that can be formed from a set ofn
distinct vertices? Cayley’s formula gives the answerTn Dnn ^2. One way to
derive this appears in Problem 14.8. This and three additional derivations are given
by Aigner & Ziegler (1998), who comment that “the most beautiful of them all” isa
counting argument due to Jim Pitman that we now describe.
Pitman’s derivation counts in two different ways the number of different se-
quences of edges that can be added to an empty graph onnvertices to form a
rooted tree. One way to form such a sequence is to start with one of theTnpossible
unrooted trees, choose one of its n vertices as root, and choose one of the.n 1/Š
possible sequences in which to add itsn 1 edges. Therefore, the total number of
sequences that can be formed in this way is
Tnn.n 1/ŠDTnnŠ:Another way to count these edge sequences is to start with the empty graph and
build up a spanning forest of rooted trees by adding edges in sequence. When
n kedges have been added, the graph with these edges will be a spanning forest
(^8) From Double counting, wikipedia, Aug. 30, 2014. See also Pr ufer Sequences