Advanced Counting Problems

• Stars and bars — distributing identical objects into distinct bins.
• Derangements Dₙ = n! · Σ(k=0 to n) (−1)ᵏ/k! — permutations with no fixed points.
• Inclusion-exclusion principle for counting with overlapping restrictions.
• Committee and seating problems with restrictions.

Level 1 — Stars and bars and basic restricted problems

Stars and bars: Distributing n identical objects into r distinct bins (each bin ≥ 0): C(n+r−1, r−1). If each bin must have at least 1: C(n−1, r−1) (place one in each bin first, distribute n−r remaining).

Applications: Number of non-negative integer solutions to x₁ + x₂ + … + xₖ = n is C(n+k−1, k−1). Number of positive integer solutions: C(n−1, k−1).

Committee with restrictions:

• "At least one from group A of size a": Total − (none from A) = C(n, r) − C(n−a, r).
• "Exactly k from group A": C(a, k) × C(n−a, r−k).
• "Person P must be included": C(n−1, r−1). "P must be excluded": C(n−1, r).

Level 2 — Derangements and inclusion-exclusion

Derangements: A derangement of n objects is a permutation where no element appears in its original position. Formula: Dₙ = n! · [1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!] = n! · Σ(k=0 to n) (−1)ᵏ/k!

Small values: D₁ = 0, D₂ = 1, D₃ = 2, D₄ = 9, D₅ = 44. Recurrence: Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂).

Approximate: Dₙ ≈ n!/e for large n. Probability of derangement ≈ 1/e ≈ 0.368.

Inclusion-Exclusion Principle (PIE): |A ∪ B| = |A| + |B| − |A ∩ B| |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |B∩C| − |A∩C| + |A∩B∩C|

General: |∪Aᵢ| = Σ|Aᵢ| − Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| − …

PIE for derangements derivation: Let Aᵢ = set of permutations where element i is in its correct position. |Aᵢ| = (n−1)!, |Aᵢ∩Aⱼ| = (n−2)!, etc. By PIE and inclusion-exclusion, Dₙ = n! − nC1·(n−1)! + nC2·(n−2)! − … = n!·Σ(−1)ᵏ/k!.

Seating with restrictions:

• n people at round table, k specific people must not sit together: gaps method + complement.
• Male-female alternating at round table: fix one male → (n−1)! × n! (for equal numbers m=f=n).

JEE pattern — distribution into groups: Distributing n distinct objects into 3 groups of sizes a, b, c (a+b+c=n): n!/(a!b!c!) if groups are distinct (labelled); n!/(a!b!c!·m!) if m groups have same size.

NCERT spotlight

PIE is the underlying principle for derangements, Euler's totient function, and inclusion-exclusion in probability. Stars and bars applies to partition problems in number theory. Key: derangement probability ≈ 1/e is a JEE-favourite unexpected result linking combinatorics to analysis.

How many ways can 10 identical pens be distributed among 4 students so that each gets at least 1?

Step 1 — Give 1 pen to each student first: remaining pens = 10 − 4 = 6.
Step 2 — Distribute 6 identical pens among 4 students (0 or more each).
Step 3 — Stars and bars: C(6 + 4 − 1, 4 − 1) = C(9, 3) = 84.
Step 4 — Answer: 84 distributions.
Step 5 — Check: Without the "at least 1" constraint: C(10+3, 3) = C(13,3) = 286 (sanity check — larger as expected).

Find the number of ways 4 letters can be placed in 4 addressed envelopes such that no letter goes to its correct address (derangement).

Step 1 — D₄ = 4![1 − 1/1! + 1/2! − 1/3! + 1/4!].
Step 2 — = 24[1 − 1 + 1/2 − 1/6 + 1/24].
Step 3 — = 24[0 + 0.5 − 0.1667 + 0.0417].
Step 4 — = 24 × (12/24 − 4/24 + 1/24) = 24 × 9/24 = 9.
Step 5 — D₄ = 9. Verify via recurrence: D₄ = 3(D₃ + D₂) = 3(2 + 1) = 9. ✓

1. In how many ways can 8 identical chocolates be distributed among 3 children (each may get 0)?
2. Find D₅.
3. In a class of 30, how many students are enrolled in at least one of Maths (20), Physics (15), both (8)?
4. In how many ways can 5 people sit in a row such that persons A and B are never adjacent?
5. Stretch: Using PIE, derive the formula for Dₙ from first principles, and verify for n = 3.

Open the Practice tab for graded questions on Permutations & Combinations — Problems.

• Use the platform-native live simulation or PhET-style tool for this topic (number line, Venn, physics playground, molecule builder, sensor dashboard, etc.).
• Mirror / body / home activity: physically do the concept (count objects, measure, role-play) and photograph or describe for portfolio.
• Voice or text reflection with AI Mentor: explain the concept to a younger student or family member.

• "Explain this concept to a Class 6 student using one real example from an Indian home, school, market, or festival."
• "What is one common mistake students make here, and how would you catch yourself making it?"
• Stretch: "How does this connect to coding, robotics, money, health, environment, or a future career?"

• Complete the core practice + one extension activity (photo, table, short reflection, or mini-project) for base XP + topic badge.
• 5-7 day streak or family discussion note = multiplier + visible artifact in parent/principal dashboard.
• Best real-world application stories (anonymised) featured on class or national leaderboard.

• One hands-on project or measurement using the Drishti kit or household items that makes the concept physical.
• Direct link to at least one Future Skill track (Money Management, Green Tech, Cyber Defenders, Micro-Entrepreneurship, AI Mastery, Sustainable Living, Personality Development).
• Coding extension where relevant (simple script, simulation, or data logging).

This material emphasises experiential "learning by doing", competency (apply/create/analyse), vocational exposure, critical thinking, and multidisciplinary connections. Designed to feed live worlds, AI Mentor (with memory), gamification, robotics, parent analytics, and future skills — not just exam prep.

Portfolio Evidence Idea: Your photo/table/reflection/project + one sentence on "How this helps me in real life or a possible future path."

Open the Practice tab for aligned questions (easy/medium/hard + case-based) with full AI scaffolding.

See curriculum for cross-links and the full future-skills/robotics chapters.