Bijection principle (include the case of distributing indistinguishable objects into distinguishable boxes)

Welcome to the Bijection Principle!

In H3 Mathematics, counting can sometimes feel like trying to count a swarm of bees—everything is moving, and it’s easy to lose track. The Bijection Principle is your secret weapon. Instead of counting the "hard" thing directly, we find a "twin" problem that is much easier to count and show that they have the exact same number of outcomes. This is the heart of combinatorial reasoning!

Don't worry if this seems a bit abstract at first. We are going to focus on one of its most famous applications: Stars and Bars. By the end of these notes, you’ll be able to distribute identical items into different boxes like a pro.

1. What exactly is a "Bijection"?

Imagine you are at a wedding. You want to know if there are exactly as many chairs as there are guests. You could count every guest and then count every chair, but that’s a lot of work. Instead, you just wait for everyone to sit down. If every guest has exactly one chair and no chairs are empty, you have a bijection.

In math, a bijection is a rule that pairs every element of Set A with exactly one element of Set B, with nothing left over. Because they are perfectly paired, we know that:
Size of Set A = Size of Set B

The Bijection Principle says: To count Set A, find a Set B that is easier to count and establish a bijection between them.

Quick Review: Prerequisite Concepts

Before we move on, let's clarify two terms that often trip students up:
• Indistinguishable (Identical) Objects: Like 10 identical gold coins. If you swap two coins, nothing changes.
• Distinguishable (Distinct) Boxes: Like 3 different people (Alice, Bob, and Charlie). It matters who gets which coin!

2. The Stars and Bars Method

This is the most common way we apply the Bijection Principle in H3. We use it to solve this specific problem: How many ways can we distribute \(n\) indistinguishable objects into \(r\) distinguishable boxes?

The Analogy: The Candy Shop

Imagine you have 7 identical lollipops (the Stars) to give to 3 different children (the Bars).
To separate the lollipops into 3 groups, we don't need 3 dividers; we only need 2 dividers.
If we place the dividers like this: \(* * | * * * | * *\), it means:
• Child 1 gets 2 lollipops.
• Child 2 gets 3 lollipops.
• Child 3 gets 2 lollipops.

Did you know? The number of "Bars" (dividers) is always one less than the number of boxes. If you have \(r\) boxes, you need \(r - 1\) bars.

3. Case 1: Boxes Can Be Empty (\(x_i \ge 0\))

If we are allowed to give a child zero lollipops, the dividers and lollipops can be in any order.
Example: \(| * * * * * * * |\) means Child 2 gets all 7, while Child 1 and 3 get zero.

Step-by-Step Calculation

1. Identify the number of objects: \(n\) (Stars).
2. Identify the number of boxes: \(r\).
3. Calculate the number of dividers needed: \(r - 1\) (Bars).
4. Find the total number of items to arrange: \(n + (r - 1)\).
5. The Formula: We choose the positions for the bars from the total positions:
\( \binom{n+r-1}{r-1} \) or \( \binom{n+r-1}{n} \)

Example: Distribute 10 identical marbles into 4 different bags.
• \(n = 10\)
• \(r = 4\), so Bars = \(4 - 1 = 3\)
• Total positions = \(10 + 3 = 13\)
• Ways = \( \binom{13}{3} = \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = 286 \)

Key Takeaway: When objects are identical and boxes are distinct, think "Stars and Bars" and remember that \(r\) boxes only need \(r-1\) dividers!

4. Case 2: Each Box Must Have At Least One (\(x_i \ge 1\))

Sometimes the problem says "each box must be non-empty." This is actually easier!
If we have 7 lollipops and 3 children, and everyone must get at least one, we can use a simple trick.

The "Pre-delivery" Trick

1. Give one lollipop to each child first.
2. Now you have \(n - r\) lollipops left to distribute freely.
3. Use the Case 1 formula with the remaining lollipops.

Alternative Logic (The Gaps Method):
Imagine the 7 stars in a row: \(* \_ * \_ * \_ * \_ * \_ * \_ *\)
There are 6 gaps between them. To create 3 groups, we just need to pick 2 gaps to place our bars.
The Formula: \( \binom{n-1}{r-1} \)

Example: Find the number of positive integer solutions to \(x_1 + x_2 + x_3 = 10\).
• Here, \(n = 10\) and \(r = 3\).
• Since they are positive integers, \(x_i \ge 1\).
• Ways = \( \binom{10-1}{3-1} = \binom{9}{2} = 36 \).

5. Common Mistakes to Avoid

• Mixing up \(n\) and \(r\): Always ask yourself: "What is being divided (stars)?" and "Who/What is receiving them (boxes)?"
• Using the wrong formula for "at least 1": If the question says "non-negative," use the \(n+r-1\) formula. If it says "positive" or "at least one," use the \(n-1\) formula.
• Forgetting the bijection: Remember that we are counting sequences of stars and bars because there is a 1-to-1 mapping between those sequences and the ways to fill the boxes.

6. Summary Quick Review

The Scenario: Distributing \(n\) identical items into \(r\) distinct boxes.
The Method: Stars and Bars.
• If boxes can be empty: Ways = \( \binom{n+r-1}{r-1} \)
• If boxes cannot be empty: Ways = \( \binom{n-1}{r-1} \)
• Why it works: We are creating a bijection between the distribution of items and a string of symbols (\(*\) and \(|\)).

Keep practicing! Combinatorics is all about seeing the pattern. Once you "see" the stars and bars in a problem, the math becomes a simple calculation.