Skip to main content

Chapter 20 Combinatorial Proof

Exercises Practice Problems

1.

Give a combinatorial proof for the identity

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

  • LHS:\({3n \choose 3}\) counts the number of ways to choose a 3-set from \([3n]\)

  • RHS: Split \([3n]\) into 3 sets of size \(n\text{.}\) There are 3 different cases (addition principle)

    • \(3 {n \choose 3}\text{:}\) Choose one of the \(n\)-sets and pick all 3 elements from that set.

    • \(6n {n \choose 2}\text{:}\) Pick one of the three \(n\)-sets and take 2 elements from that set (number of ways is \(3{n \choose 2}\text{.}\) Next, pick one of the remaining two \(n\)-sets and take 1 element from that set (number of ways is \(2 n\text{.}\)

    • \(n^3\text{:}\) Choose one element from each of the three \(n\)-sets.

2.

Give a combinatorial proof for the identity

\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 rewrite this as
\begin{equation*} \sum_{k=0}^n {n \choose k} {n \choose n-k} = { 2n \choose n}. \end{equation*}

  • RHS: the number of ways to choose an \(n\)-set from \([2n]\text{.}\)

  • LHS: Split \([2n]\) into two sets of size \(n\text{.}\) We then consider \(n+1\) cases, depending on how many elements we pick from the first set. We can choose \(0 \leq k \leq n\) elements from the first set and then pick the remaining \(n-k\) from the second set. For a fixed \(k\text{,}\) the number of ways to do this is \({ n \choose k} {n \choose n-k}\text{.}\) We then sum over all possible \(k\text{.}\)

3.

Give a combinatorial proof for the identity

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

Solution.

This is a more general version of the previous problem.

  • RHS: the number of ways to choose an \(r\)-set from \([n+m]\text{.}\)

  • LHS: Split \([n+m]\) into two sets, one of size \(n\) and the other of size \(m\text{.}\) We then consider \(r+1\) cases, depending on how many elements we pick from the first set. We can choose \(0 \leq i \leq r\) elements from the first set and then pick the remaining \(r-i\) from the second set. For a fixed \(i\text{,}\) the number of ways to do this is \({n \choose i} {m \choose n-i}\text{.}\) We then sum over all possible \(i\text{.}\)

4.

Give a combinatorial proof for the identity

\begin{equation*} {k \choose k} + {k+1 \choose k} + {k+2 \choose k} + \cdots + {n \choose k} = {n+1 \choose k+1}. \end{equation*}

Hint: For the LHS, we have split into cases according to the LARGEST ELEMENT in our \((k+1)\)-set of \([n+1]\text{.}\)

Solution.
Both sides count the number of ways to choose \(k+1\) numbers from the set \(n+1\)

  • RHS: the number of ways to choose a \(k+1\)-set from \([n]\text{.}\)

  • LHS: We partition the subsets according to the largest element in the subset \(A \subseteq [n+1]\text{.}\) If the largest element of \(A\) is \(k+1\text{,}\) then we still must choose \(k\) elements from \([k]\text{,}\) and there are \({k \choose k}\) ways to do this. If the largest element of \(A\) is \(k+2\text{,}\) then we still must choose \(k\) elements from \([k+1]\text{,}\) and there are \({k+1 \choose k}\) ways to do this. If the largest element of \(A\) is \(k+3\text{,}\) then we still must choose \(k\) elements from \([k+2]\text{,}\) and there are \({k+2 \choose k}\) ways to do this. This same argument holds for each case. The largest possible maximum element in \(n+1\text{.}\) In this case, we still must choose \(k\) elements from \([n]\text{,}\) and there are \({n \choose k}\) ways to do this.