14.11. References 595
Describe a bijection fromBXto the set of permutations ofX.^7 This implies that
there are how may bijections fromXtoX?
Problems for Section 14.4
Class Problems
Problem 14.10.
Use induction to prove that there are 2 nsubsets of ann-element set (Theorem 4.5.5).
Homework Problems
Problem 14.11.
Here is a purely combinatorial proof of Fermat’s Little Theorem 8.10.8.
(a)Suppose there are beads available inadifferent colors for some integera > 1,
and letpbe a prime number. How many different colored lengthpsequences of
beads can be strung together? How many of them contain beads of at least two
different colors?
(b)Make each string ofpbeads with at least two colors into a bracelet by tying
the two ends of the string together. Two bracelets are the same if one can be rotated
to yield the other. (Note, however, that youcannot”flip” a bracelet over or reflect
it.) Show that for every bracelet, there are exactlypstrings of beads that yield it.
Hint: Both the fact thatpis prime and that the bracelet consists of at least two
colors are needed for this to be true.
(c)Conclude thatpj.ap a/and from this conclude Fermat’s Little Theorem.Problems for Section 14.5
Practice Problems
Problem 14.12.
Eight students—Anna, Brian, Caine,... —are to be seated around a circular table
in a circular room. Two seatings are regarded as defining the samearrangementif
each student has the same student on his or her right in both seatings: it does not
(^7) A sequence in which all the elements of a setXappear exactly once is called apermutationof
X(see Section 14.3.3).