Math Detours · Grade 11 · Around the corner · 9

Count it twice

Count the same thing in two ways and you have proved an identity. Committees with a chair, the hockey stick in Pascal's triangle, and Vandermonde's sum.

Name ____________________Date ____________

Tonight's idea

Here is a way to prove an identity with no algebra. Count one collection of things in two different ways. Both counts are correct, so they must be equal.

Recall \(\binom nk\), read "\(n\) choose \(k\)": the number of ways to choose \(k\) things from \(n\) (where you met this).

From \(n\) people, pick a committee of \(k\) and make one member the chair. How many outcomes are there?

Committee first. There are \(\binom nk\) committees, then \(k\) choices of chair.

Chair first. There are \(n\) choices of chair, then \(\binom{n-1}{k-1}\) ways to pick the other \(k - 1\) members from the \(n - 1\) people left.

\(k\dbinom nk = n\dbinom{n-1}{k-1}\).

No factorials were needed, and you can see why it is true. The recipe is always the same. Find a collection that one side of the identity counts. Then find a second way to organise the count. Often the second way sorts the collection into cases, and the cases turn into a sum.

Watch one: the hockey stick

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
\(1 + 3 + 6 + 10 = 20\).

In Pascal's triangle, add down a diagonal from the edge and the total sits just below the last number. Why?

Count teams of 3 from people numbered 1 to 6: \(\binom63 = 20\). Now sort the teams by their highest number. Highest 3: the other two come from \(\{1, 2\}\), so \(\binom22 = 1\) team. Highest 4: \(\binom32 = 3\). Highest 5: \(\binom42 = 6\). Highest 6: \(\binom52 = 10\). Every team is in exactly one case, so

\[\binom22 + \binom32 + \binom42 + \binom52 = \binom63.\]

The same sorting proves \(\binom rr + \binom{r+1}r + \cdots + \binom nr = \binom{n+1}{r+1}\).

More patterns: mathdetours.com/demos/pascal.html.

Your turn

  1. (a) Check the committee identity with numbers for \(n = 6\), \(k = 3\). (b) Use the hockey stick to find \(1 + 4 + 10 + 20 + 35\) without adding.
  2. Now the committee can be any size from 1 to \(n\), and it still has a chair. Count the outcomes chair first. Then count them committee first, sorted by size \(k\). Write down the identity you have proved, and check it for \(n = 4\).
  3. A club has 5 seniors and 4 juniors. Count the teams of 3 directly. Then count them sorted by the number of seniors, and check the totals agree. Write the identity for \(m\) seniors, \(n\) juniors and a team of \(r\). (It is called Vandermonde's identity.)
  4. Prove that \(\binom n0^2 + \binom n1^2 + \cdots + \binom nn^2 = \binom{2n}{n}\) by counting something twice. You may use \(\binom nk = \binom n{n-k}\). Check it for \(n = 3\).

Stretch: a chair and a secretary

From \(n\) people choose a committee of any size, a chair, and a secretary. One person may hold both jobs. Count the outcomes in two ways to find a short formula for \(\displaystyle\sum_{k=0}^{n} k^2\binom nk\). Check it for \(n = 4\).

Answers

  1. (a) \(3\binom63 = 3 \times 20 = 60\) and \(6\binom52 = 6 \times 10 = 60\). (b) These are \(\binom33, \binom43, \binom53, \binom63, \binom73\), so the sum is \(\binom84 = 70\).
  2. Chair first: \(n\) choices, then each of the other \(n - 1\) people is in or out, \(2^{n-1}\) ways. Committee first: \(\binom nk\) committees of size \(k\), each with \(k\) possible chairs. So \(\displaystyle\sum_{k=1}^{n} k\binom nk = n\,2^{n-1}\). For \(n = 4\): \(4 + 12 + 12 + 4 = 32 = 4 \times 8\).
  3. Directly: \(\binom93 = 84\). By seniors (0, 1, 2, 3): \(\binom50\binom43 + \binom51\binom42 + \binom52\binom41 + \binom53\binom40 = 4 + 30 + 40 + 10 = 84\). In general \(\displaystyle\sum_{k=0}^{r} \binom mk\binom n{r-k} = \binom{m+n}{r}\), where \(\binom ab\) counts as 0 when \(b > a\).
  4. Take \(n\) seniors and \(n\) juniors and choose a team of \(n\): \(\binom{2n}{n}\) ways. Sorted by the number \(k\) of seniors: \(\binom nk\) ways to pick the seniors and \(\binom n{n-k} = \binom nk\) ways to pick the juniors, so \(\binom nk^2\) teams. Add over \(k\). (This is question 3 with \(m = n = r\).) For \(n = 3\): \(1 + 9 + 9 + 1 = 20 = \binom63\).

Stretch. Committee first: a committee of size \(k\) has \(k\) choices of chair and \(k\) of secretary, so the count is \(\sum k^2\binom nk\). Jobs first: if one person holds both, \(n\) choices and the rest are in or out, \(n\,2^{n-1}\). If two people hold them, \(n(n-1)\) choices and the other \(n - 2\) are in or out, \(n(n-1)2^{n-2}\). Total \(n\,2^{n-2}\,(2 + n - 1) = n(n+1)2^{n-2}\). For \(n = 4\): \(4 + 24 + 36 + 16 = 80 = 4 \times 5 \times 4\).

← PreviousNext: How many different necklaces? →