Solved Exercises on Advanced Combinations and Permutations in Grade 10

Master advanced combinatorics: multinomial coefficients, circular permutations, derangements, and probability applications through these 5 detailed exercises.

Solution: Exercises 1 to 3
1 Multinomial Coefficients
Exercise 1
In how many ways can 12 identical candies be distributed among 4 children if each child gets at least one candy?
Definition:

Multinomial coefficient: Number of ways to distribute n identical items into k distinct groups

Stars and bars: Method to solve distribution problems: C(n-1, k-1)

With restrictions: Adjust for minimum requirements first

Distribution method:
  1. Account for minimum requirements
  2. Adjust the problem to unconstrained distribution
  3. Apply stars and bars formula
  4. Calculate the multinomial coefficient
Initial
12 candies, 4 children, each gets ≥ 1
After restriction
8 candies, 4 children
Ways
C(11, 3) = 165
Step 1: Account for minimum requirement

Each child must get at least 1 candy, so allocate 1 candy to each child

Candies allocated: 4 × 1 = 4 candies

Remaining candies: 12 - 4 = 8 candies

Step 2: Apply stars and bars to remaining candies

Now distribute 8 identical candies among 4 children with no restrictions

This is equivalent to finding number of non-negative integer solutions to: x₁ + x₂ + x₃ + x₄ = 8

Step 3: Apply the formula

Number of ways = C(n + k - 1, k - 1) where n = 8 (remaining candies), k = 4 (children)

Number of ways = C(8 + 4 - 1, 4 - 1) = C(11, 3)

Step 4: Calculate the combination

C(11, 3) = 11!/(3! × 8!) = (11 × 10 × 9)/(3 × 2 × 1) = 990/6 = 165

165 ways
Final answer:

There are 165 ways to distribute 12 identical candies among 4 children if each child gets at least one candy

Applied rules:

• Stars and bars: C(n + k - 1, k - 1) for distributing n identical items to k groups

• Restriction handling: Allocate minimum requirements first

• Combination formula: C(n,r) = n!/(r!(n-r)!)

2 Circular Permutations
Exercise 2
In how many ways can 6 people be seated around a circular table if 2 specific people must sit next to each other?
Definition:

Circular permutation: Arrangements around a circle where rotations are equivalent

Formula: (n-1)! for n distinct objects around a circle

Treating as unit: When objects must be adjacent, treat them as one unit

Given
6 people, 2 must be adjacent
Treat as unit
5 units, arrange in circle
Total arrangements
4! × 2! = 48
Step 1: Treat the 2 specific people as one unit

Instead of arranging 6 individuals, we're arranging 5 units: {AB}, C, D, E, F

Where AB represents the 2 people who must sit together

Step 2: Arrange 5 units in a circle

For circular arrangements: (n-1)! = (5-1)! = 4! = 24 ways

Step 3: Arrange the 2 people within their unit

The 2 specific people can be arranged within their unit in 2! = 2 ways

Step 4: Apply the multiplication principle

Total arrangements = (Arrangements of units) × (Arrangements within unit)

Total = 4! × 2! = 24 × 2 = 48 ways

48 ways
Final answer:

There are 48 ways to seat 6 people around a circular table if 2 specific people must sit next to each other

Applied rules:

• Circular permutations: (n-1)! for n distinct objects

• Adjacency constraint: Treat adjacent objects as single unit

• Multiplication principle: Multiply independent arrangements

3 Derangements
Exercise 3
In how many ways can 4 letters be placed in 4 addressed envelopes so that no letter goes to its correct envelope?
Definition:

Derangement: Permutation where no element appears in its original position

Formula: !n = n!(1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n!)

Alternative: !n = floor(n!/e + 1/2) for large n

Given
4 letters, 4 envelopes, none correct
Derangement
!4
Result
9
Step 1: Identify as derangement problem

We need to find the number of ways to arrange 4 letters so that none is in its correct envelope

This is a derangement of 4 objects, denoted as !4

Step 2: Apply the derangement formula

!n = n!(1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n!)

!4 = 4!(1 - 1/1! + 1/2! - 1/3! + 1/4!)

Step 3: Calculate each term

4! = 24

1 - 1/1! + 1/2! - 1/3! + 1/4! = 1 - 1 + 1/2 - 1/6 + 1/24

= 0 + 0.5 - 0.1667 + 0.0417 = 0.375

Step 4: Calculate final result

!4 = 24 × 0.375 = 9

!4 = 9
Final answer:

There are 9 ways to place 4 letters in 4 addressed envelopes so that no letter goes to its correct envelope

Applied rules:

• Derangement formula: !n = n!∑(k=0 to n)(-1)ᵏ/k!

• Subfactorial notation: !n represents nth derangement

• Principle of inclusion-exclusion: Used in derivation of formula

Advanced Combinatorics Formulas
\(!n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}, C(n,r) = \frac{n!}{r!(n-r)!}, P(n,r) = \frac{n!}{(n-r)!}\)
Key Combinatorial Formulas
Permutations
P(n,r) = n!/(n-r)!
Order matters
Combinations
C(n,r) = n!/[r!(n-r)!]
Order doesn't matter
Derangement
!n = n!∑(-1)ᵏ/k!
No element in original position
Key definitions:

Multinomial Coefficient: Generalization of binomial coefficient for multiple categories

Circular Permutation: Arrangement of objects around a circle where rotations are equivalent

Derangement: Permutation with no fixed points (no element in original position)

Advanced combinatorics methodology:
  1. Problem identification: Determine if order matters, repetitions allowed
  2. Constraint analysis: Identify any restrictions or special conditions
  3. Formula selection: Choose appropriate combinatorial formula
  4. Adjustment: Modify for constraints if necessary
  5. Calculation:
    Apply formula systematically
Tip 1: For circular arrangements, fix one object to eliminate rotational equivalence.
Tip 2: When objects must be adjacent, treat them as a single unit.
Tip 3: For derangements, use inclusion-exclusion principle.
Tip 4: Stars and bars works for distributing identical objects to distinct groups.
Common errors: Confusing permutations with combinations, forgetting circular adjustments, misapplying formulas.
Exam preparation: Memorize formulas, practice constraint problems, work with real-world scenarios.
Essential formulas:

• Permutations: P(n,r) = n!/(n-r)!

• Combinations: C(n,r) = n!/(r!(n-r)!)

• Circular permutations: (n-1)! for n distinct objects

• Derangement: !n = n!∑(k=0 to n)(-1)ᵏ/k!

• Stars and bars: C(n+r-1, r-1) for n identical items to r groups

Solution: Exercises 4 to 5
4 Probability with Combinations
Exercise 4
A committee of 5 people is to be selected from 8 men and 7 women. What is the probability that the committee has at least 3 women?
Definition:

At least problems: Calculate complement or sum of favorable cases

Probability: P(E) = Number of favorable outcomes / Total number of outcomes

Case analysis: Break complex problems into simpler cases

Given
8M, 7W, select 5, at least 3W
Cases
(3W,2M), (4W,1M), (5W,0M)
Probability
119/195
Step 1: Identify total number of ways to select committee

Total people = 8 men + 7 women = 15 people

Total ways to select 5 people = C(15, 5) = 15!/(5!×10!) = 3,003

Step 2: Identify favorable cases (at least 3 women)

Case 1: Exactly 3 women and 2 men = C(7,3) × C(8,2)

Case 2: Exactly 4 women and 1 man = C(7,4) × C(8,1)

Case 3: Exactly 5 women and 0 men = C(7,5) × C(8,0)

Step 3: Calculate each case

Case 1: C(7,3) × C(8,2) = 35 × 28 = 980

Case 2: C(7,4) × C(8,1) = 35 × 8 = 280

Case 3: C(7,5) × C(8,0) = 21 × 1 = 21

Step 4: Calculate total favorable outcomes

Total favorable = 980 + 280 + 21 = 1,281

Step 5: Calculate probability

P(at least 3 women) = 1,281/3,003 = 119/195 ≈ 0.610

P(at least 3 women) = 119/195
Final answer:

The probability that the committee has at least 3 women is 119/195 or approximately 61.0%

Applied rules:

• Probability formula: P(E) = favorable/total

• Multiplication principle: For independent selections

• Case analysis: Break complex conditions into simpler parts

5 Multinomial Theorem
Exercise 5
Find the coefficient of x²y³z⁴ in the expansion of (x + y + z)⁹.
Definition:

Multinomial theorem: (x₁ + x₂ + ... + xₖ)ⁿ = Σ(n!/(n₁!n₂!...nₖ!))x₁ⁿ¹x₂ⁿ²...xₖⁿᵏ

Multinomial coefficient: n!/(n₁!n₂!...nₖ!) where n₁ + n₂ + ... + nₖ = n

Term selection: Find specific term in multinomial expansion

Given
(x+y+z)⁹, find x²y³z⁴
Exponents
2+3+4=9 ✓
Coefficient
9!/(2!3!4!) = 1260
Step 1: Apply multinomial theorem

(x + y + z)⁹ = Σ(n!/(n₁!n₂!n₃!))xⁿ¹yⁿ²zⁿ³ where n₁ + n₂ + n₃ = 9

Step 2: Identify required exponents

We need the term with x²y³z⁴, so n₁ = 2, n₂ = 3, n₃ = 4

Check: n₁ + n₂ + n₃ = 2 + 3 + 4 = 9 ✓

Step 3: Calculate multinomial coefficient

Coefficient = 9!/(2!3!4!) = 362,880/(2 × 6 × 24) = 362,880/288 = 1,260

Step 4: Verify the calculation

9! = 362,880

2! = 2, 3! = 6, 4! = 24

2! × 3! × 4! = 2 × 6 × 24 = 288

362,880 ÷ 288 = 1,260

Coefficient = 1260
Final answer:

The coefficient of x²y³z⁴ in the expansion of (x + y + z)⁹ is 1,260

Applied rules:

• Multinomial theorem: Generalization of binomial theorem

• Multinomial coefficient: n!/(n₁!n₂!...nₖ!)

• Exponent sum: Must equal the power of the original expression

Detailed Summary: Advanced Combinations and Permutations
\(D_n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}, C(n+r-1,r-1) = \text{stars and bars}, (n-1)! = \text{circular permutations}\)
Advanced Combinatorial Formulas
Comprehensive definitions:

Multinomial Coefficient: Generalization of binomial coefficient for multiple categories, represents number of ways to partition n objects into k distinct groups

Circular Permutation: Arrangement of objects around a circle where rotations are considered identical, leading to (n-1)! distinct arrangements

Derangement: Permutation where no element appears in its original position, denoted as !n

Stars and Bars: Technique for solving distribution problems of identical objects to distinct groups

Complete advanced combinatorics methodology:
  1. Problem classification: Determine if it's a permutation, combination, or special case
  2. Constraint identification: Note any restrictions, requirements, or special conditions
  3. Formula selection: Choose appropriate combinatorial formula
  4. Adjustment for constraints: Modify the problem if needed
  5. Systematic calculation: Apply the formula carefully
  6. Verification: Check that answer makes sense in context
Tip 1: For circular arrangements, always consider if rotations are equivalent (divide by n).
Tip 2: When objects must be adjacent, treat them as a single entity then arrange internally.
Tip 3: For "at least" problems, consider the complement or break into cases.
Tip 4: In multinomial problems, ensure the sum of exponents equals the power of the expression.
Common applications: Committee formation, seating arrangements, probability calculations, combinatorial proofs.
Key principles: Multiplication principle, addition principle, inclusion-exclusion, bijection.
Essential formulas and rules:

• Permutations: P(n,r) = n!/(n-r)! when order matters

• Combinations: C(n,r) = n!/(r!(n-r)!) when order doesn't matter

• Circular permutations: (n-1)! for n distinct objects

• Derangement: !n = n!∑(k=0 to n)(-1)ᵏ/k!

• Stars and bars: C(n+r-1, r-1) for distributing n identical items to r groups

• Multinomial coefficient: n!/(n₁!n₂!...nₖ!) for partitioning n objects

Visualization: Combinatorial Concepts
Combinatorial Relationships
Explore advanced combinatorial relationships:
Permutations vs combinations, circular arrangements, derangements
Stars and bars, multinomial coefficients

Analysis: The chart shows different combinatorial concepts and their applications.

  • Permutations count ordered arrangements
  • Combinations count unordered selections
  • Derangements count arrangements with no fixed points

Questions & Answers

Question: When do I use permutations vs combinations? It's always confusing!

Answer: The key is to ask: "Does the order of selection matter?"

  • Permutations: Order matters - arranging, ranking, scheduling, sequences
  • Combinations: Order doesn't matter - selecting, choosing, grouping, committees

Examples:

  • Permutations: Seating 3 people in 3 chairs (ABC ≠ BAC), creating passwords
  • Combinations: Selecting 3 people from 10 for a team (same 3 people regardless of order)

Ask yourself: "Would changing the order create a different outcome?" If yes, use permutations; if no, use combinations.

Question: Why do we divide by (n-1)! for circular permutations instead of n!?

Answer: In circular arrangements, rotations of the same arrangement are considered identical.

For example, if Alice, Bob, and Carol are seated around a round table:

  • Alice-Bob-Carol is the same as Bob-Carol-Alice and Carol-Alice-Bob (rotations)
  • Each unique circular arrangement corresponds to n linear arrangements

So we divide by n to account for these equivalent rotations: n!/n = (n-1)!

An alternative way to think about it: Fix one person's position (to eliminate rotational equivalence), then arrange the remaining (n-1) people in (n-1)! ways.

Question: What is a derangement and where is it used in real life?

Answer: A derangement is a permutation where no element appears in its original position.

Real-life applications:

  • Secret Santa: Ensuring no one draws their own name
  • Testing: Ensuring answers don't match the questions in order
  • Computer science: Hash functions, cryptography algorithms
  • Biology: Genetic mutations where genes don't stay in original positions

The formula !n = n!(1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n!) approaches n!/e as n increases, which is approximately 36.8% of all permutations.

Question: How does the stars and bars method work?

Answer: Stars and bars is a visual method for distributing identical objects into distinct groups.

The method:

  • Stars (*): Represent the identical objects to be distributed
  • Bars (|): Represent dividers between different groups

Example: Distributing 5 identical candies to 3 children

Represent as: **|*|** (child 1 gets 2, child 2 gets 1, child 3 gets 2)

Formula: To distribute n identical objects to k groups, we need n stars and (k-1) bars

Total positions: n + k - 1, choose k-1 positions for bars: C(n+k-1, k-1)

Alternatively: C(n+k-1, n) - choose n positions for stars

Question: What's the difference between the multinomial theorem and binomial theorem?

Answer: The binomial theorem is a special case of the multinomial theorem.

Binomial theorem:

(x + y)ⁿ = Σ(k=0 to n) C(n,k) xⁿ⁻ᵏ yᵏ

Multinomial theorem:

(x₁ + x₂ + ... + xₖ)ⁿ = Σ(all n₁+...+nₖ=n) [n!/(n₁!n₂!...nₖ!)] x₁ⁿ¹x₂ⁿ²...xₖⁿᵏ

The multinomial theorem generalizes to any number of terms, while the binomial theorem is specifically for two terms.

When k=2 (two terms), the multinomial coefficient becomes C(n,n₁) = C(n,k), which is the binomial coefficient.

Both use factorial ratios to count the number of ways terms can combine in the expansion.