Enumerative Combinatorics: Activities and Exercises

1. Creating a \(k\)-list.

Prove the following identity where we "treat element \(n\) as special." Think about this as writing a recipe, and then counting the number of ways that you can complete the recipe.

Solution.

2. Another Chairperson Identity.

Prove the following chairperson identity.

1. Explain how each side of the equation corresponds to a recipe for creating a chaired committee. Solution.

   LHS

   • Pick the chair (\(n\) ways).

   • For the remaining \(n-1\text{,}\) decide whether each person is on the committee.

   RHS

   • Choose the size \(k\) of the committee

   • Pick the committee: \({n \choose k}\) ways.

   • Pick the chair from the committee members: \(k\) ways

   • Sum over \(1 \leq k \leq n\) to handle all committee sizes.

2. Starting with the binomial theorem

   \begin{equation*} (x+y)^n = \sum_{k=0}^{n} {n \choose k} x^k y^{n-k}, \end{equation*}

   give another proof of this chairperson identity. (Hint: first, take the partial derivative of both sides with respect to \(x\text{.}\)) Solution.

   \begin{equation*} \frac{\partial}{\partial x} (x+y)^n = n(x+y)^{n-1} \end{equation*}

   and

   \begin{equation*} \frac{\partial}{\partial x} \left( \sum_{k=0}^{n} {n \choose k} x^k y^{n-k} \right)= \sum_{k=1}^{n} k {n \choose k} x^{k-1} y^{n-k} \end{equation*}

   Now plug in \(x=y=1\) to get

   \begin{equation*} n 2^{n-1} = \sum_{k=1}^n k {n \choose k} \end{equation*}

3. Picking a 2-Set.

Most introductory discrete mathematics books ask students to use induction to prove that

In this course, we recognize the right hand side is actually \({n+1 \choose 2}\text{.}\) In other words, we have

Give a combinatorial proof of this identity about choosing a \(2\)-set from \([n+1]\text{.}\) Remember that an addition sign corresponds to "or." Hint: pick the largest element of the \(2\)-set first. Solution.

4. Combinatorial Proofs.

Give a combinatorial proof for each of the following identities. Each one involves splitting the original set into two or more subsets, and then performing the task at hand.

1. .

   \begin{equation*} {3n \choose 3} = 3 {n \choose 3} + 6n {n \choose 2} + n^3. \end{equation*}

   Solution.

   LHS: choose a 3-set from \([3n]\) RHS: split \([3n]\) into \(\{1, \ldots, n \}\) and \(\{ n+1 ,\ldots, 2n\}\) and \(\{ 2n+1, \ldots, 3n \}\) and do one of the following

   • Pick a subset (3 ways) and take 3 elements from that set

   • Pick a subset (3 ways) and pick one element from that set. Now pick a second set (2 ways) and pick two elements from that set.

   • Choose one element from each set.

2. .

   \begin{equation*} \sum_{k=0}^n \left( {n \choose k} \right)^2 = { 2n \choose n}. \end{equation*}

   Hint: you will need the identity \({r \choose s} = {r \choose r-s.}\text{.}\) Solution.

   We can rewrite this as

   \begin{equation*} \sum_{k=0}^n {n \choose k} {n \choose n-k} = { 2n \choose n}. \end{equation*}

   We have the following interpretation. RHS: pick an \(n\)-set from \([2n]\text{.}\) LHS: Choose \(1 \leq k \leq n\text{.}\) Then pick \(k\) elements from \(\{1 , \ldots, n\}\) and pick \(n-k\) elements from \(\{n+1, \ldots, 2n \}\text{.}\)

3. .

   \begin{equation*} {n + m \choose r} = \sum_{i=0}^r {n \choose i} {m \choose r-i}. \end{equation*}

   Solution.

   This is a lot like the previous problem. LHS: pick an \(r\)-set from \([n+m]\text{.}\) RHS:

   • Split the set into \(\{1, \ldots, n\}\) and \(\{n+1, \ldots, m \}\text{.}\)

   • Choose \(i\) where \(0 \leq i \leq r\text{.}\)

   • Pick an \(i\)-set from \(\{1, \ldots, n\}\) and pick an \((n-i)\)-set from \(\{n+1, \ldots, m \}\text{.}\)

   • Sum over all possible values for \(i\text{.}\)

5. Subsets of \(n\) Without Successive Elements.

We define the following sets:

• \({\mathcal{A}_n}\text{:}\) subsets of \([n]\) that do not contain successive elements

• \({\mathcal{B}_n}\) ordered sums of 1's and 2's that add to \(n\text{.}\)

Show that \({\mathcal{A}_n}\) is in bijection with \({\mathcal{B}_{n+1}}\text{.}\)