Skip to main content
🔗

Section 2.5 Combinatorial Arguments

🔗
The Binomial Theorem and Pascal's Formula are examples of combinatorial identities. These are identities or equations that involve the binomial coefficients.

🔗
We've seen two possible proofs of Pascal's Formula

(nk)=(n−1k)+(n−1k−1)

🔗
in Exploration 2.3.1 and Checkpoint 2.3.12. One can prove this a third way using algebra.

Prove Theorem 2.3.2 by manipulating the right-hand side algebraically, and showing that it simplifies to the left-hand side.

🔗
Proofs by algebra are easy to follow, but often provide little information about why the statement is true. The first two proofs of Theorem 2.3.2, in contrast, provide insights about the quantities involved in the identity. Let's look at another example.

🔗
Video: Combinatorial Arguments

🔗
Now we prove Theorem 2.5.2 a second way, with what we call a combinatorial argument or a combinatorial proof. This typically involves counting one set in two different ways, thus showing that the two quantities obtained (from each way of counting) are equal.

Prove Theorem 2.5.2 by counting a set in two ways.

Solution

Our goal is to show that

\begin{equation} k\binom{n}{k} = n\binom{n-1}{k-1}\label{equation-chairperson}\tag{2.5.1} \end{equation}

given integers \(0 \leq k \leq n\text{.}\)

To do this, we count the number of ways to form a committee of \(k\) members from \(n\) people, and then elect a chair of the committee.

Suppose that from a group of \(n\) people, we want to

  1. Form a committee of \(k\) people; and
  2. Elect a chair of the committee.

By Principle 2.1.9, we can count the number of ways we can do this by multiplying.

  1. There are \(\binom{n}{k}\) ways to form a committee of \(k\) people from a group of \(n\text{.}\)
  2. From the \(k\) people in the committee, we need to choose a chair, and there are \(k\) choices.

Hence we count a total of

\begin{equation*} \binom{n}{k} \times k \end{equation*}

ways to do this. Note that this is the left-hand side of what we're proving, (2.5.1).

Now let's count the number of such committee-chair selections in a different way: by first selecting the chair.

  1. Elect a chair of the committee; then
  2. Complete the committee by adding members.

Again, we use Principle 2.1.9, noting that the number of choices in the second step is independent of who is picked for the first.

  1. There are \(n\) people in the original group, so we have \(n\) choices for committee chair.
  2. From the remaining \(n-1\) people, we need to select \(k-1\) members to fill out the committee. There are \(\binom{n-1}{k-1}\) ways to do this.

Therefore we can select a chair and form the committee a total of

\begin{equation*} n\binom{n-1}{k-1} \end{equation*}

ways. This is the right-hand side of (2.5.1)!

We just showed that the left-hand side and the right-hand side of the given identity are two different ways of counting the committee-chair possibilities, and hence, they must be equal.

🔗
The following diagrams illustrate the two ways of selecting a committee of size k=4 and a chairperson given a group of n=9 people.

🔗
First way of counting:

Nine dots in a three by three grid.
Nine dots in a three by three grid, four are bigger and colored blue.
Nine dots in a three by three grid, of the four blue dots one has been colored red and emphasized.

From nine people

pick four members

then elect a chair.

🔗
Second way:

Nine dots in a three by three grid.
Nine dots in a three by three grid, four are bigger and colored blue.
Nine dots in a three by three grid, of the four blue dots one has been colored red and emphasized.

From nine people

elect a chair

then pick three more members.

🔗
While the combinatorial proof of the Chairperson Identity is no more correct than the algebraic method, it offers a concrete, meaningful way to explain why the two quantities are always equal. Proving combinatorial identities in this manner requires creativity, especially if one is not told what set is being counted.

🔗
In general:

  • If the identity involves addition, this means the objects being counted will likely be broken up into disjoint cases (and Principle 2.1.7 is used).
  • If the identity involves multiplication, there may be multiple interpretations depending on the use of Principle 2.1.9. For instance, 2n may represent the number of subsets of {1,2,…,n} or the number of binary strings of length n.

Using algebra it is a straightforward manipulation to show that

\begin{equation*} n^2 = 2\binom{n}{2} + n \end{equation*}

for \(n \in \mathbb{N}\text{.}\) Write a complete combinatorial proof of this statement.

Hint 1

First think what objects are counted by \(n^2\text{.}\) Then, break them up into two distinct cases for the right-hand side

Hint 2

Count the ordered pairs \((i,j)\) in \(\{1,2,\ldots,n\}^2\text{,}\) and consider cases on whether the two coordinates \(i\) and \(j\) are equal or distinct.

Prove the statement in Checkpoint 2.3.8 by counting the number of subsets of \(\{1,2,\ldots,n\}\) in two ways.

Hint

Partition subsets by cardinality. (How many subsets have size 0? have size 1? And so on...)

🔗

Solutions Solutions to Selected Checkpoints