Combinatorial arguments and proofs

Welcome to the World of Counting: Combinatorial Proofs!

In your H2 Mathematics journey, you learned how to count arrangements and selections. In H3 Mathematics, we take those skills to the next level. Instead of just finding a number, we use counting as a way to prove that two mathematical expressions are equal. This is called a combinatorial argument.

Think of it like this: if you count the number of students in a classroom by rows, and then count them again by columns, you should get the same number. If row-counting gives you one formula and column-counting gives you another, those two formulas must be equal! Don't worry if this seems a bit abstract right now—we will break it down step-by-step.

1. What is a Combinatorial Proof?

A combinatorial proof is a way of proving an identity (an equation where the left side equals the right side) by showing that both sides of the equation count the same set of objects in two different ways.

The "Story" Method: To write a combinatorial proof, you essentially tell a story about selecting a group of objects.
1. Left Hand Side (LHS): Explain how this counts a specific scenario.
2. Right Hand Side (RHS): Explain how this counts the exact same scenario using a different perspective.
3. Conclusion: Since both count the same thing, they must be equal!

Did you know?

Combinatorial proofs are often considered more "elegant" than algebraic proofs (like expanding brackets or using induction) because they reveal the reason why an identity is true, rather than just showing that the math works out.

2. The Symmetry Identity

Let's start with a classic one you already know from H2:
\( \binom{n}{r} = \binom{n}{n-r} \)

The Scenario: Suppose you have a group of \(n\) friends and you want to choose \(r\) of them to go to a concert.

LHS Explanation: By definition, the number of ways to choose \(r\) people out of \(n\) is \( \binom{n}{r} \).

RHS Explanation: Instead of choosing who goes to the concert, you could choose who stays at home. To have \(r\) people go, you must leave \(n-r\) people behind. The number of ways to choose the \(n-r\) people to stay home is \( \binom{n}{n-r} \).

Conclusion: Since every choice of "goers" corresponds to exactly one choice of "stayers," the two expressions must be equal.

3. Pascal's Identity

This is a foundational identity in combinatorics:
\( \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \)

The Scenario: You need to choose a committee of \(k\) people from a group of \(n\) people. One of these \(n\) people is a student named Sam.

LHS Explanation: The total number of ways to choose the committee is simply \( \binom{n}{k} \).

RHS Explanation: Let’s count the committees by looking at whether Sam is included or not:
• Case 1: Sam is on the committee. We already have Sam, so we only need to pick \(k-1\) more people from the remaining \(n-1\) candidates. This is \( \binom{n-1}{k-1} \) ways.
• Case 2: Sam is NOT on the committee. We must pick all \(k\) people from the remaining \(n-1\) candidates. This is \( \binom{n-1}{k} \) ways.
Since these two cases are mutually exclusive and cover all possibilities, we add them together.

Conclusion: Both sides count the total number of ways to form the committee, so \( \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \).

Quick Review: The "Star Player" Method

Whenever you see an identity that adds two combinations together to get a larger one, try to imagine a "Star Player" (like Sam above) and create two cases: one where they are included and one where they are excluded.

4. The Committee-Chair Identity

Consider the identity: \( k \binom{n}{k} = n \binom{n-1}{k-1} \)

The Scenario: We want to form a committee of \(k\) people from a group of \(n\) and then pick one person from that committee to be the Chairperson.

LHS Explanation: First, choose the \(k\) committee members from the \(n\) people in \( \binom{n}{k} \) ways. Then, from those \(k\) members, choose 1 Chairperson in \(k\) ways. Total: \( k \binom{n}{k} \).

RHS Explanation: First, pick the Chairperson from the entire group of \(n\) people in \(n\) ways. Then, from the remaining \(n-1\) people, choose the other \(k-1\) committee members in \( \binom{n-1}{k-1} \) ways. Total: \( n \binom{n-1}{k-1} \).

Conclusion: Both methods count the same committees-with-chairs, so the expressions are equal.

5. The Bijection Principle

Sometimes, we prove two things are equal by showing a one-to-one correspondence (a bijection) between two different sets. If every element in Set A can be paired with exactly one element in Set B (with none left over), then the size of Set A must equal the size of Set B.

Example: Stars and Bars
The syllabus mentions distributing indistinguishable objects into distinguishable boxes.
Suppose you have \(n\) identical candies to give to \(k\) children. This is the same as arranging \(n\) "stars" (candies) and \(k-1\) "bars" (dividers).
Because there is a bijection between the candy distribution and the arrangement of symbols, we can use the formula for arrangements to prove the distribution formula: \( \binom{n+k-1}{k-1} \).

6. Inclusion-Exclusion Principle (IEP)

In H2, you learned: \( P(A \cup B) = P(A) + P(B) - P(A \cap B) \).
In H3, we use this for more complex proofs involving "at least one" or "none" scenarios.

Concept: To count the number of elements in the union of several sets, you:
1. Add the sizes of the individual sets.
2. Subtract the sizes of all possible double-intersections (because they were counted twice).
3. Add back the sizes of all possible triple-intersections (because they were subtracted too many times)... and so on.

Analogy: If you over-correct a steering wheel to the left, you have to turn it back to the right, and then maybe a little bit back to the left to stay centered. IEP is a mathematical "steering correction."

7. Common Pitfalls and Tips

• Avoid Algebra: If a question asks for a combinatorial argument, you will lose marks if you just expand factorials. Focus on the "story."
• Check the boundaries: Make sure your "story" makes sense for the values of \(n\) and \(k\) (e.g., you can't pick 5 people from a group of 3).
• Identify the "Action": Are you picking a team? Are you assigning roles? Are you arranging symbols? Identifying the action helps you see the formula's meaning.

Summary Key Takeaways

• Combinatorial proofs show that two formulas are equal by counting the same set in two ways.
• Double Counting is the core technique: find a set, count it one way (LHS), then count it another way (RHS).
• Pascal's Identity relies on the "include or exclude" logic for a specific individual.
• The Bijection Principle shows two sets are the same size by pairing their elements perfectly.
• Inclusion-Exclusion helps count complex overlaps by adding and subtracting intersections.

Don't worry if this seems tricky at first! Combinatorial reasoning is like a puzzle. Once you find the right "story" to tell, the math falls perfectly into place.