Permutation & Combination - Intermediate Level: complex scenario handling INTERMEDIATE

Step-by-Step Solution:

Concept: Permutation with fixed position constraint.

Strategy: Fix the restricted position, then arrange remaining elements.

Given:
- Total people: 7
- Constraint: One specific person must be first

Step 1 - Fix First Position:
First position has only 1 choice (the specific person)

Step 2 - Arrange Remaining:
Remaining 6 people can be arranged in 6! ways

Calculation:
Total arrangements = 1 × 6!
= 720
= 2160

Alternative Approach:
Total arrangements without restriction = 7! = 5040
Fraction with specific person first = 5040 / 7 = 2160

Key Principle: Fixing one position reduces the problem to arranging (n-1) elements.

Step-by-Step Solution:

Concept: This is a combination problem because the order of selection doesn't matter.

Formula: C(n,r) = n! / [r!(n-r)!]

Given:
- n = 9 (total items)
- r = 4 (items to select)

Calculation:
C(9,4) = 9! / [4! × 5!]
= 9! / [24 × 120]
= 362880 / [24 × 120]
= 126

Alternative Method (using simplified calculation):
C(9,4) = (9 × 8 × ... × 6) / 4!

Key Distinction:
- Use COMBINATION when order doesn't matter (selecting)
- Use PERMUTATION when order matters (arranging)

Verification: The answer must be less than 9! since we're selecting, not arranging.

Step-by-Step Solution:

Concept: Multinomial theorem expansion:
$$(x_1 + x_2 + ... + x_k)^n = \sum_{a_1+...+a_k=n} \frac{n!}{a_1! a_2! ... a_k!} x_1^{a_1} x_2^{a_2} ... x_k^{a_k}$$

Given:
- Expression: (x+y+z)^6
- Desired term: the term x^3 * y^2 * z^1
- Exponents: x = 3, y = 2, z = 1

Step 1 - Verify exponent sum:
3 + 2 + 1 = 6 = 6 ✓

Step 2 - Apply multinomial coefficient formula:
Coefficient = $\frac{6!}{3! × 2! × 1!}$

Step 3 - Calculate:
- Numerator: 6! = 720
- Denominator: 3! × 2! × 1! = 6 × 2 × 1
- Denominator value: 12

Final Calculation:
Coefficient = 720 / 12 = 60

Alternative interpretation: This equals the number of ways to arrange 6 items with:
3 of type x, 2 of type y, 1 of type z

Key Principle: Multinomial coefficients generalize binomial coefficients:
- Binomial: C(n, k) = n!/(k!(n-k)!)
- Multinomial: n!/(a! b! c! ...) where a+b+c+... = n

Quick Check: The sum of all multinomial coefficients for given n is k^n = 3^6 = 729

Step-by-Step Solution:

Concept: Partitioning into groups of specified sizes. When group sizes are different, groups are automatically distinguishable by size.

Given:
- Total people: 11
- Group sizes: 7, 3, 1
- Groups are unlabeled (no names like Team A, Team B)

Formula:
$$\frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}$$

Step 1 - Choose first group:
Choose 7 people from 11: C(11, 7) = 330

Step 2 - Choose second group:
From remaining 4 people, choose 3: C(4, 3) = 4

Continue for all groups:
C(11,7) = 330
C(4,3) = 4
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 330 × 4 × 1 (last group)
= 1320

Simplified formula:
= 11! / (7! × 3! × 1!)
= 39916800 / (5040 × 6 × 1)
= 1320

Key Insight: Since groups have different sizes, we don't divide by k! (they're naturally distinguishable by their sizes).

Contrast with equal groups:
- If groups were same size: would divide by k!
- Here, sizes differ: no division needed

Verification: Sum of group sizes = 11 = 11 ✓

Step-by-Step Solution:

Concept: Number formation with positional restrictions. The first digit cannot be 0 (otherwise it wouldn't be an 5-digit number).

Given:
- Number length: 5 digits
- Available digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (10 digits)
- Repetition: Allowed
- Constraint: First digit cannot be 0

Position-by-Position Analysis:

First digit (leftmost):
Cannot be 0 (would make it 4-digit number)
Choices: 1, 2, 3, 4, 5, 6, 7, 8, 9
Count: 9 choices

Second digit:
Can be any digit including 0
Choices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Count: 10 choices

Third digit through 5th digit:
Each can be any digit including 0
Count: 10 choices each

Apply Multiplication Principle:
Total numbers = 9 × 10 × 10 × ... × 10 (4 times)
= 9 × 10^4
= 9 × 10000
= 90000

Alternative Verification:
- Smallest 5-digit number: 10000 = 10000
- Largest 5-digit number: 99999 = 99999
- Total count: 99999 - 10000 + 1 = 90000

Related Problems:
1. No repetition: 9 × P(9,4) = 9 × 9!/5!
2. Odd numbers only: 9 × 10^3 × 5 (last digit: 1,3,5,7,9)
3. Even numbers only:
- If last digit 0: 9 × 10^3 × 1
- If last digit 2,4,6,8: 8 × 10^3 × 4
- Total: 9 × 10^3 + 8 × 4 × 10^3

Key Principle: When forming numbers:
- First digit has special restriction (can't be 0)
- Handle positional constraints carefully
- Use multiplication principle for independent choices

Step-by-Step Solution (Stars and Bars):

Concept: This problem is equivalent to finding the number of non-negative integer solutions to $x_1 + x_2 + \dots + x_{k} = {n}$. This is a distribution problem of identical items ({n} 'stars') into distinct containers ({k} 'bins') using {k-1} separators ('bars').

Formula: The number of solutions is $\text{C}(n + k - 1, k - 1)$.
- $n$ = number of identical items (stars) = {n}
- $k$ = number of distinct recipients (bins) = {k}

Calculation:
Total arrangements = $\text{C}({n} + {k} - 1, {k} - 1)$
= $\text{C}({n + k - 1}, {k - 1})$
= {answer}

Key Distinction:
- Identical Items, Distinct Boxes (Stars and Bars): $\text{C}(n+k-1, k-1)$
- Distinct Items, Distinct Boxes (Distribution): $k^n$

Verification: This method guarantees that all solutions are non-negative ($x_i \ge 0$).

Step-by-Step Solution:

Concept: Combination with mandatory inclusion constraint.

Given:
- Total people: 11
- Committee size: 6
- Must include: 2 specific people

Strategy: Fix the mandatory selections first, then choose remaining from available pool.

Analysis:
We need to select 6 people total, with 2 already fixed.
- Fixed positions: 2 (these specific people are already in)
- Remaining positions to fill: 6 - 2 = 4
- People available for remaining positions: 11 - 2 = 9

Step 1 - Fix Mandatory Members:
2 specific people must be included: C(2,2) = 1 way
(This is automatic - we have no choice here)

Step 2 - Select Remaining Members:
Choose 4 people from remaining 9 people:
C(9,4) = 126

Calculation:
C(9,4) = (9)! / [4! × (5)!]
= 362880 / [24 × 120]
= 126

Alternative Approach - Verification:
Think of it as: "We've used 2 spots, now choose 4 more from 9 remaining"

Related Problem Types:

1. Must EXCLUDE specific people:
Select all 6 from remaining 11 - (people to exclude)

2. At least one specific person:
Total ways - Ways without that person
= C(11,6) - C(11-1,6)

3. Exactly k from group A, rest from group B:
C(|A|,k) × C(|B|,6-k)

Common Error: Don't forget to reduce both the total pool and the selection size by the number of mandatory inclusions.

Answer: 126 ways

Step-by-Step Solution:

Concept: Permutation with repetition. When some objects are identical, we divide by the factorial of the number of repetitions.

Analysis of 'ROOM':
- Total letters: 4
- Some letters are repeated

Formula: n! / (p! × q! × ...)
where p, q, ... are the frequencies of repeated letters

Calculation:
If all letters were distinct: 4! = 24 arrangements

But some letters are repeated, so we have overcounted.
We must divide by 2! for the repeated letters.

Answer = 24 / 2 = 12

Key Principle: Identical objects create duplicate arrangements. We divide by their factorial to remove duplicates.

Why divide?: The repeated letters can be swapped among themselves without creating a new arrangement. We divide to account for this overcounting.

Step-by-Step Solution:

Concept: Derangement - permutation where no element appears in its original position. Denoted as D(n) or !n.

Given:
- Number of items: 4
- Constraint: No item in its correct position

Derangement Formula:
D(n) = n! × [1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n!]

Or recursively: D(n) = (n-1)[D(n-1) + D(n-2)]

Step-by-Step Calculation:
D(0) = 1 (convention)
D(1) = 0 (one item must be in its position)
D(2) = 1 (only one swap possible)

For n ≥ 3, we use: D(n) = (n-1)[D(n-1) + D(n-2)]

Let's calculate:
D(0) = 1
D(1) = 0
D(2) = 1
D(3) = (3-1)[D(2) + D(1)] = 2 × [1 + 0] = 2
D(4) = (4-1)[D(3) + D(2)] = 3 × [2 + 1] = 9

Answer: D(4) = 9

Intuitive Understanding:
Total arrangements = 4! = 24
Derangements = 9
Probability of derangement ≈ 1/e ≈ 0.368 (for large n)

Real-World Application:
- Secret Santa where no one gets their own name
- Permutation ciphers in cryptography
- Hat-check problem in probability

Key Formula Memory Aid:
D(n) ≈ n!/e for large n (within 1 unit)
For 4: 24/e ≈ 9 ≈ 9

Common Error: Don't subtract n! - n, that's not derangement count.

Step-by-Step Solution:

Concept: This is a combination problem because the order of selection doesn't matter.

Formula: C(n,r) = n! / [r!(n-r)!]

Given:
- n = 8 (total items)
- r = 3 (items to select)

Calculation:
C(8,3) = 8! / [3! × 5!]
= 8! / [6 × 120]
= 40320 / [6 × 120]
= 56

Alternative Method (using simplified calculation):
C(8,3) = (8 × 7 × ... × 6) / 3!

Key Distinction:
- Use COMBINATION when order doesn't matter (selecting)
- Use PERMUTATION when order matters (arranging)

Verification: The answer must be less than 8! since we're selecting, not arranging.

Step-by-Step Solution:

Concept: Handshake problem with subset participation.

Given:
- Total people: 14
- Non-participants: 3
- Participants: 11

Step 1 - Identify participants:
Only 11 people actually shake hands.

Step 2 - Calculate handshakes among participants:
Handshakes = C(11, 2) = 11×10/2

Calculation:
= 11×10/2 = 55
= 55

Key Point: Non-participants don't contribute to any handshake.

Step-by-Step Solution:

Concept: Circular permutation formula = (n-1)! when clockwise and anticlockwise are considered different, and rotations are considered the same.

Why (n-1)! and not n!?
In a circle, there's no fixed starting point. Rotations of the same arrangement are identical.

Analysis:
- If arranged in a line: 7! = 5040 ways
- But in a circle: we fix one person's position as reference
- Remaining 6 people can be arranged in 6! ways

Calculation:
Circular arrangements = (7-1)! = 6! = 720

Intuition: Fix one person at a position (say 12 o'clock). Now arrange the remaining 6 people in the 6 positions clockwise.

Formula Summary:
- Linear permutation: n!
- Circular permutation (rotations same): (n-1)!
- Circular permutation (reflections also same): (n-1)!/2

Common Error: Don't use n! for circular arrangements - this counts rotations as different arrangements.

Step-by-Step Solution:

Concept: Permutations with identical objects. When objects of the same type are indistinguishable, we divide by the factorial of each type's count.

Formula:
$$\frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}$$
where $n$ is total objects and $n_i$ is the count of type $i$.

Given Data:
- Total objects: 14
- Distribution: Type 1: 3, Type 2: 2, Type 3: 4, Type 4: 4, Type 5: 1

Step 1 - Total arrangements if all were distinct:
14! = 87178291200

Step 2 - Account for identical objects:
14! = 87178291200 / 3! = 6 / 2! = 2 / 4! = 24 / 4! = 24

Final Calculation:
= 12612600

Key Principle: Each group of identical objects overcounts by a factor of (count)!. Division corrects this.

Verification: The result is an integer and less than 14! = 87178291200.

Step-by-Step Solution:

Concept: Permutation with repetition. When some objects are identical, we divide by the factorial of the number of repetitions.

Analysis of 'BALL':
- Total letters: 4
- Some letters are repeated

Formula: n! / (p! × q! × ...)
where p, q, ... are the frequencies of repeated letters

Calculation:
If all letters were distinct: 4! = 24 arrangements

But some letters are repeated, so we have overcounted.
We must divide by 2! for the repeated letters.

Answer = 24 / 2 = 12

Key Principle: Identical objects create duplicate arrangements. We divide by their factorial to remove duplicates.

Why divide?: The repeated letters can be swapped among themselves without creating a new arrangement. We divide to account for this overcounting.

Step-by-Step Solution (Rencontres Numbers):

Concept: This is a partial derangement problem. We want exactly k fixed points, with the remaining n-k elements deranged.

Formula:
$$D(n, k) = \binom{n}{k} \cdot !(n-k)$$
where $!(m)$ is the derangement number.

Given:
- n = 6 (total elements)
- k = 2 (exact fixed points)

Step 1 - Choose which positions are fixed:
Choose 2 positions out of 6: C(6,2) = 15

Step 2 - Derange the remaining elements:
Remaining 4 elements must have NO fixed points
Derangement number D(4) = 9

Step 3 - Apply multiplication principle:
Total = C(6,2) × D(4)
= 15 × 9
= 135

Verification:
- When k=0: D(n,0) = derangement(n) ✓
- When k=n-1: D(n,n-1) = 0 (can't have all but one fixed) ✓
- When k=n: D(n,n) = 1 (identity permutation) ✓

Rencontres numbers table for n=6:
- D(6,0) = 265
- D(6,1) = 264
- D(6,2) = 135
- ... and so on.

Key Insight: The sum of all rencontres numbers for given n equals n! (total permutations).

Step-by-Step Solution:

Concept: Circular Permutation with reflection symmetry. This is used for arrangements like necklaces or keyrings where flipping the arrangement produces the same result (Clockwise = Anticlockwise).

Formula: $\text{Total Ways} = \frac{(n-1)!}2$

Analysis:
- Total items ($n$): 5
- Step 1: Normal circular arrangements (rotations same) = $(n-1)!$ = 24
- Step 2: Account for reflection (flips) by dividing by 2.

Calculation:
Arrangements = $\frac{(5-1)!}2$
= $\frac{24}2$
= 12

Formula Summary:
- Linear: $n!$
- Circular (no reflection): $(n-1)!$
- Circular (with reflection): $\frac{(n-1)!}2$

Key Principle: Dividing by 2 removes the overcounting caused by the symmetry when the arrangement can be flipped.

Step-by-Step Solution (Rencontres Numbers):

Concept: This is a partial derangement problem. We want exactly k fixed points, with the remaining n-k elements deranged.

Formula:
$$D(n, k) = \binom{n}{k} \cdot !(n-k)$$
where $!(m)$ is the derangement number.

Given:
- n = 7 (total elements)
- k = 2 (exact fixed points)

Step 1 - Choose which positions are fixed:
Choose 2 positions out of 7: C(7,2) = 21

Step 2 - Derange the remaining elements:
Remaining 5 elements must have NO fixed points
Derangement number D(5) = 44

Step 3 - Apply multiplication principle:
Total = C(7,2) × D(5)
= 21 × 44
= 924

Verification:
- When k=0: D(n,0) = derangement(n) ✓
- When k=n-1: D(n,n-1) = 0 (can't have all but one fixed) ✓
- When k=n: D(n,n) = 1 (identity permutation) ✓

Rencontres numbers table for n=7:
- D(7,0) = 1854
- D(7,1) = 1855
- D(7,2) = 924
- ... and so on.

Key Insight: The sum of all rencontres numbers for given n equals n! (total permutations).

Step-by-Step Solution:

Concept: Multinomial theorem expansion:
$$(x_1 + x_2 + ... + x_k)^n = \sum_{a_1+...+a_k=n} \frac{n!}{a_1! a_2! ... a_k!} x_1^{a_1} x_2^{a_2} ... x_k^{a_k}$$

Given:
- Expression: (x+y)^4
- Desired term: the term x^4
- Exponents: x = 4, y = 0

Step 1 - Verify exponent sum:
4 + 0 = 4 = 4 ✓

Step 2 - Apply multinomial coefficient formula:
Coefficient = $\frac{4!}{4!}$

Step 3 - Calculate:
- Numerator: 4! = 24
- Denominator: 4! = 24
- Denominator value: 24

Final Calculation:
Coefficient = 24 / 24 = 1

Alternative interpretation: This equals the number of ways to arrange 4 items with:
4 of type x, 0 of type y

Key Principle: Multinomial coefficients generalize binomial coefficients:
- Binomial: C(n, k) = n!/(k!(n-k)!)
- Multinomial: n!/(a! b! c! ...) where a+b+c+... = n

Quick Check: The sum of all multinomial coefficients for given n is k^n = 2^4 = 16

Step-by-Step Solution:

Concept: Rank of a word in dictionary order - counting how many words come before it alphabetically.

Given word: MANGO

Strategy:
1. For each position, count arrangements starting with letters smaller than the actual letter
2. Add these counts to find rank
3. The rank is 1 + (number of words before it)

Letters in alphabetical order: A G M N O

Step-by-Step Calculation:

Position 1 (current letter: M):
Available letters: A G M N O
If we place 'A' here: 24 arrangements possible
If we place 'G' here: 24 arrangements possible
Subtotal arrangements before 'M': 48
Position 2 (current letter: A):
Available letters: A G N O
Position 3 (current letter: N):
Available letters: G N O
If we place 'G' here: 2 arrangements possible
Subtotal arrangements before 'N': 2
Position 4 (current letter: G):
Available letters: G O
Position 5 (current letter: O):
Available letters: O

Final Rank: 51

Verification Strategy:
1. Rank starts at 1 (not 0)
2. We count all words that come alphabetically before our word
3. Our word's rank = 1 + count of words before it

Key Principle:
- At each position, consider all possible smaller letters
- For each smaller letter, count permutations of remaining letters
- Account for repeated letters by dividing by their factorials

General Formula for Position Counting:
At position i, add: Σ (arrangements with smaller letter at position i)

Common Errors:
- Forgetting to start rank from 1
- Not accounting for repeated letters
- Counting arrangements after the word instead of before

Step-by-Step Solution:

Concept: Multinomial theorem expansion:
$$(x_1 + x_2 + ... + x_k)^n = \sum_{a_1+...+a_k=n} \frac{n!}{a_1! a_2! ... a_k!} x_1^{a_1} x_2^{a_2} ... x_k^{a_k}$$

Given:
- Expression: (x+y)^4
- Desired term: the term x^1 * y^3
- Exponents: x = 1, y = 3

Step 1 - Verify exponent sum:
1 + 3 = 4 = 4 ✓

Step 2 - Apply multinomial coefficient formula:
Coefficient = $\frac{4!}{1! × 3!}$

Step 3 - Calculate:
- Numerator: 4! = 24
- Denominator: 1! × 3! = 1 × 6
- Denominator value: 6

Final Calculation:
Coefficient = 24 / 6 = 4

Alternative interpretation: This equals the number of ways to arrange 4 items with:
1 of type x, 3 of type y

Key Principle: Multinomial coefficients generalize binomial coefficients:
- Binomial: C(n, k) = n!/(k!(n-k)!)
- Multinomial: n!/(a! b! c! ...) where a+b+c+... = n

Quick Check: The sum of all multinomial coefficients for given n is k^n = 2^4 = 16