Skip to main content

Chapter 9 Inclusion/Exclusion

Here are the Inclusion-Exclusion formulas for two sets

\begin{equation*} | A \cup B | = |A| + |B| - |A \cap B| \end{equation*}

and three sets

\begin{equation*} | A \cup B \cup C | = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |A \cap C| + |A \cap B \cap C|. \end{equation*}

The general formula for the union (events \(A_i\) are good) is

\begin{equation*} | A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{j=1}^n (-1)^{j+1} \sum_{ \{i_1, i_2, \ldots i_j \}} | A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j} | \end{equation*}

where \(\{ i_1, i_2, \ldots , i_j \} \in { [n] \choose j}\text{.}\) We also write this as

\begin{equation*} | A_1 \cup A_2 \cup \cdots \cup A_n | = \sum_{ \emptyset \neq S \subset [n]} (-1)^{|S|+1} | A_{S} | \end{equation*}

where \(A_S = \cap_{i \in S} A_i\) for \(S \neq \emptyset\text{.}\)

The general formula for the complement of the union (events \(A_i\) are bad) is

\begin{equation*} | \left( A_1 \cup A_2 \cup \cdots \cup A_n \right)^c | = \sum_{S \subset [n]} (-1)^{|S|} | A_{S} | \end{equation*}

where

\begin{equation*} A_S = \left\{ \begin{array}{cl} A & \mbox{for } S = \emptyset, \\ \displaystyle{\cap_{i \in S} A_i} & \mbox{for } S \neq \emptyset. \\ \end{array} \right. \end{equation*}

Exercises Practice Problems

1. Some Bridge Hands.

A standard deck of 52 cards consists of four suits (clubs, diamonds, hearts, spades) with 13 cards each (2 through 10, Jack, Queen, King, Ace). A bridge hand consists of 13 cards.

  1. How many bridge hands have no ace and no hearts?

  2. How many bridge hands have at least one ace and at least one heart?

  3. How many bridge hands have at least one Jack, one King, one Queen and one Ace?

2. Tangerines for Children.

  1. How many ways can you distribute 20 identical tangerines to 10 distinct children so that each child receives at most 5 tangerines?

  2. How many ways can part (a) be completed if each child must receive at least one tangerine?

3. A Formula for Derangements.

Recall that a derangement of \([n]\) is a permutation \(\phi: [n] \rightarrow [n]\) such that \(\phi(i) \neq i\) for all \(i \in [n]\text{.}\) In this problem, we develop an inclusion/exclusion formula for the number of derangements of \([n]\text{.}\) Let \(A\) be the set of all permutations of \([n]\text{.}\) We will define a set of "bad" events \(A_1, A_2 , \ldots , A_n\text{,}\) so that the set of derangements is

\begin{equation*} \left( A_1 \cup A_2 \cup \cdots \cup A_n \right)^c = A \backslash \left( A_1 \cup A_2 \cup \cdots \cup A_n \right). \end{equation*}

  1. Define the "bad" event \(A_i\) in a very natural way. Here "bad" should be taken in the context that we want a derangement, but event \(A_i\) is preventing this for element \(i\text{.}\)

  2. Calculate the following quantities:

    \begin{equation*} \begin{array}{rcl} |A_i| &=& \\ |A_i \cap A_j| &=& \\ |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}| &=& \end{array} \end{equation*}

  3. Determine the number of subsets of the following forms:

    Table 9.0.1.
    # subsets of the form \(A_i\)
    # subsets of the form \(A_i \cap A_j\)
    # subsets of the form \(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}\)

  4. Use the inclusion/exclusion formula to find number of derangements of \([n]\text{.}\) Calculate:

    \begin{equation*} \left| \left( A_1 \cup A_2 \cup \cdots \cup A_n \right)^c \right| = \sum_{k=0}^n \,\,\, \sum_{i_1, i_2, \ldots , i_k} (-1)^k |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}| \end{equation*}

    where the sum is over all \(\{i_1, i_2, \ldots , i_k \} \in \displaystyle{[n] \choose k }\text{.}\)

4. A Formula for Surjections.

Now we determine the number of surjections \(f: [n] \rightarrow [k]\) when \(n \geq k\text{.}\) We will then use that formula to get a formula for \(S(n,k)\text{.}\)

Let \(A\) be the set of all functions from \([n]\) to \([k]\text{,}\) where \(k \leq n\text{.}\)

  1. Define the "bad" event \(A_i\) in a very natural way. Here "bad" should be taken in the context that we want a surjection, but event \(A_i\) is preventing this for element \(i\text{.}\)

  2. Calculate the following quantities:

    \begin{equation*} \begin{array}{rcl} |A_i| &=& \\ |A_i \cap A_j| &=& \\ |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_s}| &=& \end{array} \end{equation*}

  3. Determine the number of subsets of the following forms:

    Table 9.0.2.
    # subsets of the form \(A_i\)
    # subsets of the form \(A_i \cap A_j\)
    # subsets of the form \(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_s}\)

  4. Use the inclusion/exclusion formula to find number of surjections from \([n]\) to \([k]\text{.}\)

    \begin{equation*} \left| \left( A_1 \cup A_2 \cup \cdots \cup A_n \right)^c \right| = \sum_{S \subseteq [n]} (-1)^{|S|} |A_S|. \end{equation*}

  5. If you divide your answer to (d) by \(k!\) then you get a formula for \(S(n,k)\text{.}\) Explain why.