Skip to main content
\(\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}{&} \)

Section Supplementary 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{?}\)