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 5.2 Application of Inclusion and Exclusion

Subsection 5.2.1 Multisets with restricted numbers of elements

Problem 235

In how many ways may we distribute \(k\) identical apples to \(n\) children so that no child gets more than four apples? Compare your result with your result in Problem 197

Hint

Notice that it is straightforward to figure out how many ways we may pass out the apples so that child \(i\) gets five or more apples: give five apples to child \(i\) and then pass out the remaining apples however you choose. And if we want to figure out how many ways we may pass out the apples so that a given set \(C\) of children each get five or more apples, we give five to each child in \(C\) and then pass out the remaining \(k-5|C|\) apples however we choose.

Subsection 5.2.2 The Ménage Problem

Problem 236

A group of \(n\) married couples comes to a group discussion session where they all sit around a round table. In how many ways can they sit so that no person is next to his or her spouse? (Note that two people of the same sex can sit next to each other.)

Hint 1

Start with two questions that can apply to any inclusion-exclusion problem. Do you think you would be better off trying to compute the size of a union of sets or the size of a complement of a union of sets? What kinds of sets (that are conceivably of use to you) is it easy to compute the size of? (The second question can be interpreted in different ways, and for each way of interpreting it, the answer may help you see something you can use in solving the problem.)

Hint 2

Suppose we have a set \(S\) of couples whom we want to seat side by side. We can think of lining up \(|S|\) couples and \(2n - 2|S|\) individual people in a circle. In how many ways can we arrange this many items in a circle?

Problem 237

A group of \(n\) married couples comes to a group discussion session where they all sit around a round table. In how many ways can they sit so that no person is next to his or her spouse or a person of the same sex? This problem is called the ménage problem.

Hint 1

Reason somewhat as you did in Problem 236, noting that if the set of couples who do sit side-by-side is nonempty, then the sex of the person at each place at the table is determined once we seat one couple in that set.

Hint 2

Think in terms of the sets \(A_i\) of arrangements of people in which couple \(i\) sits side-by-side. What does the union of the sets \(A_i\) have to do with the problem?

Subsection 5.2.3 Counting onto functions

Problem 238

Given a function \(f\) from the \(k\)-element set \(K\) to the \(n\)-element set \([n]\text{,}\) we say \(f\) is in the set \(A_i\) if \(f(x)\not= i\) for every \(x\) in \(K\text{.}\) How many of these sets does an onto function belong to? What is the number of functions from a \(k\)-element set onto an \(n\)-element set?

Problem 239

Find a formula for the Stirling number (of the second kind) \(S(k,n)\text{.}\)

Hint

What does Problem 238 have to do with this question?

Problem 240

If we roll a die eight times, we get a sequence of 8 numbers, the number of dots on top on the first roll, the number on the second roll, and so on.

(a)

What is the number of ways of rolling the die eight times so that each of the numbers one through six appears at least once in our sequence? To get a numerical answer, you will likely need a computer algebra package.

(b)

What is the probability that we get a sequence in which all six numbers between one and six appear? To get a numerical answer, you will likely need a computer algebra package, programmable calculator, or spreadsheet.

(c)

How many times do we have to roll the die to have probability at least one half that all six numbers appear in our sequence. To answer this question, you will likely need a computer algebra package, programmable calculator, or spreadsheet.

Subsection 5.2.4 The chromatic polynomial of a graph

We defined a graph to consist of set \(V\) of elements called vertices and a set \(E\) of elements called edges such that each edge joins two vertices. A coloring of a graph by the elements of a set \(C\) (of colors) is an assignment of an element of \(C\) to each vertex of the graph; that is, a function from the vertex set \(V\) of the graph to \(C\text{.}\) A coloring is called proper if for each edge joining two distinct vertices 2 If a graph had a loop connecting a vertex to itself, that loop would connect a vertex to a vertex of the same color. It is because of this that we only consider edges with two distinct vertices in our definition., the two vertices it joins have different colors. You may have heard of the famous four color theorem of graph theory that says if a graph may be drawn in the plane so that no two edges cross (though they may touch at a vertex), then the graph has a proper coloring with four colors. Here we are interested in a different, though related, problem: namely, in how many ways may we properly color a graph (regardless of whether it can be drawn in the plane or not) using \(k\) or fewer colors? When we studied trees, we restricted ourselves to connected graphs. (Recall that a graph is connected if, for each pair of vertices, there is a walk between them.) Here, disconnected graphs will also be important to us. Given a graph which might or might not be connected, we partition its vertices into blocks called connected components as follows. For each vertex \(v\) we put all vertices connected to it by a walk into a block together. Clearly each vertex is in at least one block, because vertex \(v\) is connected to vertex \(v\) by the trivial walk consisting of the single vertex \(v\) and no edges. To have a partition, each vertex must be in one and only one block. To prove that we have defined a partition, suppose that vertex \(v\) is in the blocks \(B_1\) and \(B_2\text{.}\) Then \(B_1\) is the set of all vertices connected by walks to some vertex \(v_1\) and \(B_2\) is the set of all vertices connected by walks to some vertex \(v_2\text{.}\)

Problem 241

(Relevant in Appendix C as well as this section.) Show that \(B_1=B_2\text{.}\)

Since \(B_1=B_2\text{,}\) these two sets are the same block, and thus all blocks containing \(v\) are identical, so \(v\) is in only one block. Thus we have a partition of the vertex set, and the blocks of the partition are the connected components of the graph. Notice that the connected components depend on the edge set of the graph. If we have a graph on the vertex set \(V\) with edge set \(E\) and another graph on the vertex set \(V\) with edge set \(E'\text{,}\) then these two graphs could have different connected components. It is traditional to use the Greek letter \(\gamma\) (gamma) 3 The greek letter gamma is pronounced gam-uh, where gam rhymes with ham. to stand for the number of connected components of a graph; in particular, \(\gamma(V,E)\) stands for the number of connected components of the graph with vertex set \(V\) and edge set \(E\text{.}\) We are going to show how the principle of inclusion and exclusion may be used to compute the number of ways to properly color a graph using colors from a set \(C\) of \(c\) colors.

Problem 242

Suppose we have a graph \(G\) with vertex set \(V\) and edge set \(E\text{.}\) Suppose \(F\) is a subset of \(E\text{.}\) Suppose we have a set \(C\) of \(c\) colors with which to color the vertices.

(a)

In terms of \(\gamma(V,F)\text{,}\) in how many ways may we color the vertices of \(G\) so that each edge in \(F\) connects two vertices of the same color?

Hint

For each edge in \(F\) to connect two vertices of the same color, we must have all the vertices in a connected component of the graph with vertex set \(V\) and edge set \(F\) colored the same color.

(b)

Given a coloring of \(G\text{,}\) for each edge \(e\) in \(E\text{,}\) let us consider the property that the endpoints of \(e\) are colored the same color. Let us call this property “property \(e\text{.}\)” In this way each set of properties can be thought of as a subset of \(E\text{.}\) What set of properties does a proper coloring have?

(c)

Find a formula (which may involve summing over all subsets \(F\) of the edge set of the graph and using the number \(\gamma(V,F)\) of connected components of the graph with vertex set \(V\) and edge set \(F\)) for the number of proper colorings of \(G\) using colors in the set \(C\text{.}\)

Hint

How does the number you are trying to compute relate to the union of the sets \(A_i\text{?}\)

The formula you found in Problem 242.c is a formula that involves powers of \(c\text{,}\) and so it is a polynomial function of \(c\text{.}\) Thus it is called the chromatic polynomial of the graph \(G\text{.}\) Since we like to think about polynomials as having a variable \(x\) and we like to think of \(c\) as standing for some constant, people often use \(x\) as the notation for the number of colors we are using to color \(G\text{.}\) Frequently people will use \(\chi_G(x)\) to stand for the number of way to color \(G\) with \(x\) colors, and call \(\chi_G(x)\) the chromatic polynomial of \(G\text{.}\)