Division & Distribution of Identical Objects: The "Star and Bar" Method
Master the powerful combinatorial technique for counting distributions of identical items among distinct groups.
Why Star and Bar Method Matters for JEE
The Stars and Bars method is a powerful combinatorial technique used to solve distribution problems where we need to count the number of ways to distribute identical objects among distinct recipients.
🎯 JEE Significance
- Appears in every JEE Main paper (1-2 questions)
- Forms basis for advanced combinatorial problems
- Essential for probability and statistics applications
- Saves 3-5 minutes per problem compared to casework
🎯 Quick Navigation
1. Understanding the Stars and Bars Concept
What are "Stars" and "Bars"?
🌟 Stars Represent:
- Identical objects being distributed
- Coins, pens, balls, or any identical items
- The total number we're distributing (n)
｜ Bars Represent:
- Dividers between different groups
- Separate distinct recipients or boxes
- Number of bars = (number of groups - 1)
📖 Simple Example
Distribute 5 identical stars among 3 people:
🌟 🌟 | 🌟 | 🌟 🌟
Person 1 gets 2, Person 2 gets 1, Person 3 gets 2
The arrangement of 5 stars and 2 bars uniquely determines one distribution!
2. Non-Negative Integer Solutions
When recipients can get ZERO objects
🎯 The Fundamental Formula
Number of non-negative integer solutions to:
$$x_1 + x_2 + \cdots + x_r = n$$
is given by:
$$\binom{n + r - 1}{r - 1}$$
🧠 Derivation Insight
We have n stars (identical objects) and (r-1) bars (dividers between r groups).
Total items to arrange: n + (r-1)
We choose positions for either the bars OR the stars:
$$\binom{n + r - 1}{r - 1} = \binom{n + r - 1}{n}$$
Both expressions are equivalent and equally valid!
📝 Example Problem 1
Find the number of ways to distribute 10 identical chocolates among 4 children.
✅ Solution
Step 1: Identify n and r
n = 10 (chocolates), r = 4 (children)
Step 2: Apply formula for non-negative solutions:
$$\binom{10 + 4 - 1}{4 - 1} = \binom{13}{3}$$
Step 3: Calculate:
$$\binom{13}{3} = \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = 286$$
Answer: 286 ways
3. Positive Integer Solutions
When each recipient gets AT LEAST ONE object
🎯 The Positive Solutions Formula
Number of positive integer solutions to:
$$x_1 + x_2 + \cdots + x_r = n$$
is given by:
$$\binom{n - 1}{r - 1}$$
🧠 Derivation Insight
Give 1 object to each recipient first, then distribute the remaining freely.
If each $x_i \geq 1$, then let $y_i = x_i - 1$, so $y_i \geq 0$
The equation becomes:
$$y_1 + y_2 + \cdots + y_r = n - r$$
Number of non-negative solutions:
$$\binom{(n-r) + r - 1}{r - 1} = \binom{n - 1}{r - 1}$$
📝 Example Problem 2
Find the number of ways to distribute 15 identical pens among 5 students such that each student gets at least one pen.
✅ Solution
Step 1: Identify n and r
n = 15 (pens), r = 5 (students)
Step 2: Apply formula for positive solutions:
$$\binom{15 - 1}{5 - 1} = \binom{14}{4}$$
Step 3: Calculate:
$$\binom{14}{4} = \frac{14 \times 13 \times 12 \times 11}{4 \times 3 \times 2 \times 1} = 1001$$
Answer: 1001 ways
4. Common Mistakes & How to Avoid Them
❌ Mistake 1: Confusing Identical vs Distinct Objects
Wrong: Using stars and bars for distinct objects
Correct: Stars and bars only works when objects are IDENTICAL
💡 Remember: If objects are distinct, use different methods like functions or permutations
❌ Mistake 2: Misapplying the Formulas
Wrong: Using $\binom{n-1}{r-1}$ when zero is allowed
Correct: Use $\binom{n+r-1}{r-1}$ for non-negative, $\binom{n-1}{r-1}$ for positive
💡 Memory Aid: "Add for zero" - add (r-1) in the top when zero is allowed
❌ Mistake 3: Forgetting Lower Bounds > 1
Wrong: Not adjusting when minimum is more than 1
Correct: If each $x_i \geq k$, give k to each first, then use non-negative formula
5. Advanced Applications & Variations
🎯 Problem Type 1: Lower Bounds > 0
Find number of solutions to $x_1 + x_2 + x_3 + x_4 = 20$ where each $x_i \geq 2$.
✅ Solution Approach
Step 1: Give minimum to each variable first
Give 2 to each: $2 \times 4 = 8$ distributed
Step 2: Remaining to distribute freely:
$20 - 8 = 12$ remaining
Step 3: Now distribute 12 among 4 with no restrictions:
$$\binom{12 + 4 - 1}{4 - 1} = \binom{15}{3} = 455$$
🎯 Problem Type 2: Upper Bounds
Find number of solutions to $x_1 + x_2 + x_3 = 10$ where $0 \leq x_i \leq 4$.
✅ Solution Approach
Step 1: Total without restrictions:
$$\binom{10 + 3 - 1}{3 - 1} = \binom{12}{2} = 66$$
Step 2: Subtract cases where any $x_i \geq 5$
Use inclusion-exclusion principle
Step 3: Final answer: 66 - 3×[cases with $x_1 \geq 5$] + ...
🎯 Problem Type 3: Natural Number vs Whole Number
Distribute 8 identical books among 3 shelves. Find number of distributions if:
(a) Shelves can be empty
(b) Each shelf gets at least one book
✅ Solution
Part (a): Shelves can be empty → Non-negative solutions
$$\binom{8 + 3 - 1}{3 - 1} = \binom{10}{2} = 45$$
Part (b): Each shelf gets at least one → Positive solutions
$$\binom{8 - 1}{3 - 1} = \binom{7}{2} = 21$$
📋 Quick Reference Guide
Formulas to Memorize
Non-negative solutions:
$$\binom{n + r - 1}{r - 1}$$
When zero is allowed
Positive solutions:
$$\binom{n - 1}{r - 1}$$
When each gets ≥ 1
Step-by-Step Approach
- Identify if objects are identical
- Determine if distribution allows zero or needs positive
- Apply the correct formula based on conditions
- For special bounds, use the "give minimum first" strategy
- Double-check your n and r values
📝 Practice Problems
Test your understanding with these JEE-level problems:
1. How many ways to distribute 12 identical chocolates among 5 children?
2. Find number of positive integer solutions to x + y + z = 15
3. Distribute 20 identical coins among 4 people such that each gets at least 3 coins
4. Find number of non-negative integer solutions to a + b + c + d = 10
Mastered Stars and Bars?
This powerful technique will help you solve distribution problems in seconds during JEE!