
5.E: The Principle of Inclusion and Exclusion (Exercises)

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

1. Each person attending a party has been asked to bring a prize. The person planning the party has arranged to give out exactly as many prizes as there are guests, but any person may win any number of prizes. If there are n guests, in how many ways may the prizes be given out so that nobody gets the prize that he or she brought?

2. There are m students attending a seminar in a room with n seats. The seminar is a long one, and in the middle the group takes a break. In how many ways may the students return to the room and sit down so that nobody is in the same seat as before? 3. What is the number of ways to pass out k pieces of candy from an unlimited supply of identical candy to n children (where n is fixed) so that each child gets between three and six pieces of candy (inclusive)? If you have done Supplementary Problem 1 in Chapter 4 compare your answer in that problem with your answer in this one.

4. In how many ways may k distinct books be arranged on n shelves so that no shelf gets more than m books?

5. Suppose that n children join hands in a circle for a game at nursery school. The game involves everyone falling down (and letting go). In how many ways may they join hands in a circle again so that nobody has the same person immediately to the right both times the group joins hands?

∗6. Suppose that n people link arms in a folk-dance and dance in a circle. Later on they let go and dance some more, after which they link arms in a circle again. In how many ways can they link arms the second time so that no one links with a person with whom he or she linked arms before?

∗7. (A challenge; the author has not tried to solve this one!) Redo Problem 6 in the case that there are n men and n women and when people arrange themselves in a circle they do so alternating gender.

8. Suppose we take two graphs G1 and G2 with disjoint vertex sets, we choose one vertex on each graph, and connect these two vertices by an edge e to get a graph G12. How does the chromatic polynomial of G12 relate to those of G1 and G2?