Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

2.E: Inclusion-Exclusion (Exercises)


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

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

2.1: The Inclusion-Exclusion Formula

Ex 2.1.1 List all 6 solutions to the restricted equation in example 2.1.1, and list the corresponding 6 submultisets.

Ex 2.1.2 Find the number of integer solutions to \(x_1+x_2+x_3+x_4=25\), \(1\le x_1\le6\), \(2\le x_2\le 8\), \(0\le x_3\le8\), \(5\le x_4\le9\).

Ex 2.1.3 Find the number of submultisets of \(\{25\cdot a,25\cdot b,25\cdot c,25\cdot d\}\) of size 80.

Ex 2.1.4 Recall that \(\stwo{n}{k}\) is a Stirling number of the second kind (definition 1.8.1). Prove that for \(n\ge k\ge 0\), \(\) \stwo{n}{k}={1\over k!}\sum_{i=0}^k (-1)^{k-i}i^n{k\choose i}. \(\) Do \(n=0\) as a special case, then use inclusion-exclusion for the rest. You may assume, by convention, that \(0^0=1\).

2.2: Forbidden Position Permutations

Ex 2.2.1 Prove that $\ds D_n=nD_{n-1}+(-1)^n$ when $n\ge2$.

Ex 2.2.2 Prove that $D_n$ is even if and only if $n$ is odd.

Ex 2.2.3 Provide the missing details for example 2.2.1. What is $\ds\lim_{n\to\infty} {Q_n\over n!}$?

Ex 2.2.4 Find the number of permutations of $1,2,\ldots,8$ that have no odd number in the correct position.

Ex 2.2.5 Find the number of permutations of $1,2,\ldots,8$ that have at least one odd number in the correct position.

Ex 2.2.6 How many permutations of \([n]\) have exactly $k$ numbers in their correct positions?

Ex 2.2.7 Give a combinatorial proof that $$n!=\sum_{k=0}^n {n\choose k}D_{n-k}.$$

Ex 2.2.8 A small merry-go-round has 8 seats occupied by 8 children. In how many ways can the children change places so that no child sits behind the same child as on the first ride? The seats do not matter, only the relative positions of the children.

Ex 2.2.9 On the way into a party everyone checks a coat and a bag at the door. On the way out, the attendant hands out coats and bags randomly. In how many ways can this be done if

(a) No one gets either their own coat or their own bag?

(b) One may get one's own coat, or bag, but not both.

Ex 2.2.10 Suppose $n$ people are seated in $m\ge n$ chairs in a room. At some point there is a break, and everyone leaves the room. When they return, in how many ways can they be seated so that no person occupies the same chair as before the break?