Welcome to H3 Probability and Counting!

Hello there! If you are reading this, you’ve already mastered the basics of H2 Mathematics. In H3, we take those foundations and add some powerful "logic tools" to help us solve counting problems that might have seemed impossible before. Think of this chapter as upgrading your math toolkit with precision instruments. We are going to look at the Bijection Principle and the Inclusion-Exclusion Principle. Don't worry if these names sound fancy; they are actually based on very simple ideas we use in everyday life!

1. The Bijection Principle: Counting by Mapping

Sometimes, counting the objects in a set is really hard. The Bijection Principle says that if you can find a way to perfectly match every item in Set A with exactly one item in Set B (with none left over in either set), then Set A and Set B must have the same number of items.

Analogy: Imagine a crowded cinema. Instead of walking around counting every person, you could just count the number of occupied seats. If every person has exactly one seat and no seats are shared, the number of people equals the number of occupied seats. That's a bijection!

Distributing Indistinguishable Objects into Distinguishable Boxes

This is a classic H3 problem. Suppose you have 10 identical apples (indistinguishable) and you want to give them to 3 friends (distinguishable: Alice, Bob, and Charlie). How many ways can you do this?

We use a method called "Stars and Bars."

Step-by-Step Explanation:
1. Represent the 10 apples as stars: ★ ★ ★ ★ ★ ★ ★ ★ ★ ★
2. To divide these stars among 3 people, we need 2 "bars" or dividers ( | ). For example: ★ ★ | ★ ★ ★ ★ ★ | ★ ★ ★
3. In this example, Alice gets 2, Bob gets 5, and Charlie gets 3.
4. The problem of "distributing apples" is now exactly the same (a bijection!) as the problem of "arranging 10 stars and 2 bars."

The Formula:
If you have \(n\) identical items and \(r\) distinct boxes, the number of ways to distribute them is:
\( \binom{n + r - 1}{r - 1} \) or \( \binom{n + r - 1}{n} \)

Example: For 10 apples and 3 friends, \(n = 10\) and \(r = 3\).
Ways = \( \binom{10 + 3 - 1}{3 - 1} = \binom{12}{2} = 66 \).

Quick Review: Use Stars and Bars when the items you are giving away are exactly the same (like identical coins or candies) but the people receiving them are different.

Key Takeaway: The Bijection Principle allows us to swap a hard counting problem for an easier one that has the same total count.

2. The Inclusion-Exclusion Principle (PIE)

In H2, you learned that \( P(A \cup B) = P(A) + P(B) - P(A \cap B) \). The Inclusion-Exclusion Principle is just the "grown-up" version of this rule for more than two sets.

The main idea is: Add the individual groups, Subtract the overlaps of two groups (because you counted them twice), Add back the overlaps of three groups (because you subtracted them too many times), and so on.

Visualizing with 3 Sets

Suppose you are counting students who study Biology (B), Chemistry (C), and Physics (P). To find the total number of students who study at least one of these, we follow this pattern:
1. Include: Add the sizes of individual sets: \( |B| + |C| + |P| \)
2. Exclude: Subtract the double-overlaps: \( - |B \cap C| - |B \cap P| - |C \cap P| \)
3. Include: Add the triple-overlap back: \( + |B \cap C \cap P| \)

The Formula:
\( |A \cup B \cup C| = |A| + |B| + |C| - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C| \)

Did you know? This principle is incredibly useful for finding derangements. A derangement is a permutation where no element stays in its original spot (like 5 people leaving a party and everyone accidentally taking the wrong hat!).

Memory Aid: Think of it like a heartbeat: Plus, Minus, Plus, Minus... You start by adding single items, then subtracting pairs, then adding triples, and so on.

Key Takeaway: Inclusion-Exclusion is your "cleanup crew." Use it when sets overlap and you need to make sure you haven't over-counted or under-counted any specific members.

3. Common Pitfalls and Tips

Mistake 1: Forgetting if objects are identical or distinct.
Always ask yourself: "If I swapped these two items, would the arrangement look different?" If yes, they are distinct. If no, they are identical. Stars and Bars only works for identical items.

Mistake 2: Missing the "At Least One" condition in Stars and Bars.
The basic formula \( \binom{n+r-1}{r-1} \) allows some people to get zero items. If the question says "everyone must receive at least one apple," give everyone one apple first! Then use the formula for the remaining apples.

Mistake 3: Stopping too early in PIE.
If you have four sets, you must continue the "Plus, Minus, Plus, Minus" pattern until you reach the intersection of all four sets. Don't stop at three!

Encouragement: Combinatorics and Probability can feel like a puzzle. If you get stuck, try drawing a small version of the problem. If you can solve it for 3 items, you can usually see the pattern for 100 items!

Chapter Summary

1. Bijection Principle: Match a hard set to an easy set. Use Stars and Bars for distributing identical items into distinct boxes: \( \binom{n+r-1}{r-1} \).
2. Inclusion-Exclusion: Correct for overlapping sets by alternating addition and subtraction. It’s the ultimate tool for "at least one" or "none of the" problems.
3. Logic First: Always identify whether order matters and whether items are identical before you pick a formula!