
## SectionSupplementary Problems

###### 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 Exercise 1 of 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 is to the right of the same child that was previously to his or her right?

###### 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 is next to a person with whom he or she linked arms before.

###### 7

(A challenge; the author has not tried to solve this one!) Redo Exercise 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 $G_1$ and $G_2$ with disjoint vertex sets, we choose one vertex on each graph, and connect these two graphs by an edge $e$ to get a graph $G_{12}\text{.}$ How does the chromatic polynomial of $G_{12}$ relate to those of $G_1$ and $G_2\text{?}$