$\newcommand{\cycle}[1]{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q} \def\neg1choose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}[1]{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{🍎}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{🍌}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{🍐}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## 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{?}$