Enumerative Combinatorics: Activities and Exercises

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? Solution.

   We have forbidden 13+3 cards. So our answer is

   \begin{equation*} { 52 -16 \choose 13} = {36 \choose 13} \end{equation*}

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

   We have two bad events: no hearts and no aces.

   \begin{equation*} {52 \choose 13} - { 39 \choose 13} - {48 \choose 13} + {36 \choose 13} \end{equation*}

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

   We have four symmetric bad events: \(B_J, B_Q, B_K, B_A\text{.}\) Our answer is

   \begin{equation*} {52 \choose 13} - {4 \choose 1} {48 \choose 13} + {4 \choose 2} {44 \choose 13} - {4 \choose 3} {40 \choose 13} + {4 \choose 4} {36 \choose 13}. \end{equation*}

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? Solution.

   We have ten bad events \(A_i\text{,}\) one for each child. The event \(A_i\) is "child \(i\) gets 6 or more tangerines." The sizes of the sets corresponding to these bad events are: \​begin{eqnarray*} |A_i| &=& {14+10-1 \choose 10-1} = {23 \choose 9} \\ |A_i \cap A_j| &=& {8+10-1 \choose 10-1} = {17 \choose 9} \\ |A_i \cap A_j \cap A_k| &=& {2+10-1 \choose 10-1} = {11 \choose 9} \\ |A_i \cap A_j \cap A_k \cap A_{\ell} | &=& 0, \end{eqnarray*} and larger intersections are likewise impossibl.e Therefore the total number of good ways to distribute the tangerines is

   \begin{equation*} {29 \choose 9} - {10 \choose 1} {23 \choose 9} + {10 \choose 2} {17 \choose 9} - {10 \choose 3}{11 \choose 9} \end{equation*}

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

   We start by giving one tangerine to each child, which leaves 10 to distribute as we see fit. By a similar argument (now using 5 tangerines per child as our bad event) gives

   \begin{equation*} {19 \choose 9} - {10 \choose 1} {14 \choose 9} + {10 \choose 2} {9 \choose 9}. \end{equation*}

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

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{.}\) Solution.

   \(A_i =\) element \(i\) gets mapped to itself. In other words, \(f(i)=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*}

   Solution.

   \begin{equation*} \begin{array}{rcl} |A_i| &=& (n-1)! \\ |A_i \cap A_j| &=& (n-2)! \\ |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}| &=& (n-k)! \end{array} \end{equation*}

   Note that these sizes are independent of the actual choices for \(i,j\text{,}\) etc. All that matters is the {number of subsets in the intersection}.

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

   # 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}\)

   Solution.

   # subsets of the form	\(A_i\)	is \(n = \displaystyle{{n \choose 1}}\)
   # subsets of the form	\(A_i \cap A_j\)	is \(\displaystyle{ {n \choose 2}}\)
   # subsets of the form	\(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}\)	is \(\displaystyle{{n \choose 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{.}\) Solution.

   \begin{equation*} \sum_{k=0}^n (-1)^k {n \choose k} (n-k)! = \sum_{k=0}^n (-1)^k \frac{n!}{k!} = n! \sum_{k=0}^n \frac{(-1)^k }{k!} \end{equation*}

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{.}\) Solution.

   \(A_i = \) functions that miss element \(i \in [k]\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*}

   Solution.

   \begin{equation*} \begin{array}{rcl} |A_i| &=& (k-1)^n \\ |A_i \cap A_j| &=&(k-2)^n \\ |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_s}| &=& (k-s)^n. \end{array} \end{equation*}

   Note that these sizes are independent of the actual choices for \(i,j\text{,}\) etc. All that matters is the {number of subsets in the intersection}.

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

   # 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}\)

   Solution.

   # subsets of the form	\(A_i\)	is \(n = \displaystyle{{n \choose 1}}\)
   # subsets of the form	\(A_i \cap A_j\)	is \(\displaystyle{{n \choose 2}}\)
   # subsets of the form	\(A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_s}\)	is \(\displaystyle{{n \choose 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*}

   Solution.

   \begin{equation*} \sum_{s=0}^k (-1)^s {k \choose s} (k-s)^n \end{equation*}

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

   \begin{equation*} \frac{1}{k!} \sum_{s=0}^k (-1)^s {k \choose s} (k-s)^n = \sum_{s=0}^k (-1)^s \frac{(k-s)^n}{s!(k-s)!} \end{equation*}

   The number of surjections \(f: [n] \rightarrow [k]\) is \(k! S(n,k)\text{.}\)