Permutation & Combination - Advanced Level: common mistakes to avoid ADVANCED

Step-by-Step Solution:

Concept: Gap Method - used when certain items must be separated.

Strategy:
1. Arrange the items that don't have restrictions
2. Identify gaps where restricted items can be placed
3. Place restricted items in available gaps

Given:
- Consonants: 4
- Vowels: 2
- Constraint: No two vowels together

Step 1 - Arrange Consonants:
Arrange 4 consonants: 4! = 24 ways

Step 2 - Identify Gaps:
When 4 consonants are arranged: _ C _ C _ C _ ... _ C _
Number of gaps (including ends) = 5

Visual: If we have 4 consonants, we get 5 positions where vowels can go.

Step 3 - Place Vowels in Gaps:
Choose 2 gaps from 5 available gaps: C(5,2) = 10
Arrange 2 vowels in chosen gaps: 2! = 2

Step 4 - Apply Multiplication Principle:
Total arrangements = 24 × 10 × 2
= 24 × 10 × 2
= 480

Key Technique: Gap method ensures no two restricted items are adjacent by placing them in gaps created by unrestricted items.

Verification: Check that 2 ≤ 5 (we need enough gaps).

Step-by-Step Solution:

Concept: Handshake problem - each handshake involves 2 people, and order doesn't matter.

Given: 10 people

Method 1 - Combination:
Number of handshakes = Number of ways to choose 2 people from 10
= C(10, 2) = 10! / (2! × 8!) = 10×9/2

Method 2 - Counting per person:
Each person shakes hands with 9 others
Total count: 10 × 9 = 90
But each handshake counted twice, so divide by 2: 90/2

Calculation:
= 10×9/2 = 45
= 45

Key Formula: Number of handshakes = C(n, 2) = n(n-1)/2

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$): 6
- Step 1: Normal circular arrangements (rotations same) = $(n-1)!$ = 120
- Step 2: Account for reflection (flips) by dividing by 2.

Calculation:
Arrangements = $\frac{(6-1)!}2$
= $\frac{120}2$
= 60

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 (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: Linear permutation of n distinct objects = n! (n factorial)

Analysis:
- We need to arrange 5 distinct objects in a line
- For the first position: 5 choices
- For the second position: 4 choices (one already placed)
- For the third position: 3 choices
- And so on...

Formula Application:
Number of arrangements = 5! = 5 × 4 × 3 × ... × 2 × 1

Calculation:
5! = 120

Key Concept: The factorial function represents the number of ways to arrange n distinct objects in a sequence.

Common Mistake: Don't confuse permutation (arrangement matters) with combination (arrangement doesn't matter).

Step-by-Step Solution:

Concept: Group division where groups are indistinguishable (no labels like Team A, Team B).

Given:
- Total people: 8
- Group size: 4
- Number of groups: 2

Key Question: Are the groups distinguishable?
- If groups have labels (Team A, Team B): Groups are distinguishable
- If groups have no labels: Groups are indistinguishable (our case)

Strategy for Indistinguishable Groups:

Step 1 - Select first group:
Choose 4 people from 8: C(8,4)
C(8,4) = 8!/[4! × 4!] = 70

Step 2 - Remaining people form second group:
Remaining 4 people automatically form the other group: C(4,4) = 1

Step 3 - Remove overcounting:
Since groups are indistinguishable, we've counted each division twice.
(Selecting ABCD for group 1 and EFGH for group 2 is same as selecting EFGH for group 1 and ABCD for group 2)

Divide by 2! = 2

Calculation:
Total ways = C(8,4) / 2!
= 70 / 2
= 35

General Formula:
For dividing n items into k equal groups of size m each (where n = k×m):
Ways = C(n,m) × C(n-m,m) × ... × C(m,m) / k!
= n! / [(m!)^k × k!]

For our case:
= 8! / [(4!)^2 × 2!]
= 40320 / [24^2 × 2]
= 40320 / [576 × 2]
= 35

Contrast:
- Distinguishable groups (labeled teams): 70 ways
- Indistinguishable groups (unlabeled): 35 ways

Common Error: Forgetting to divide by k! when groups are indistinguishable.

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 z^6
- Exponents: x = 0, y = 0, z = 6

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

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

Step 3 - Calculate:
- Numerator: 6! = 720
- Denominator: 6! = 720
- Denominator value: 720

Final Calculation:
Coefficient = 720 / 720 = 1

Alternative interpretation: This equals the number of ways to arrange 6 items with:
0 of type x, 0 of type y, 6 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: Distribution of distinct objects to distinct boxes - each object independently chooses a box.

Given:
- Distinct items: 7
- Distinct boxes: 3
- Empty boxes: Allowed

Strategy: Each item makes an independent choice of which box to go into.

Analysis:
- Item 1 can go into any of 3 boxes: 3 choices
- Item 2 can go into any of 3 boxes: 3 choices
- Item 3 can go into any of 3 boxes: 3 choices
- ...and so on for all 7 items

Formula: (number of boxes)^(number of items) = 3^7

Calculation:
Total ways = 3^7 = 2187

Key Distinction:
This is NOT a permutation or combination problem! It's a direct application of the multiplication principle.

Related Scenarios:
1. No empty boxes allowed (Surjection):
Use Inclusion-Exclusion: 3! × S(7,3)
where S(n,k) is the Stirling number of second kind

2. Identical items, distinct boxes:
This becomes a "stars and bars" problem: C(7+3-1, 3-1)

3. Distinct items, identical boxes (Partition):
Use Stirling numbers: Σ S(7,k) for k=1 to 3

Verification:
- With 1 box: answer should be 1 (all items in one box)
- With 7 boxes, one item: answer should be 7
- Our answer 2187 is reasonable: each item independently chooses from 3 options

Common Error: Don't use factorial or combination formulas here - items are making independent simultaneous choices.

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:

Concept: Linear permutation of n distinct objects = n! (n factorial)

Analysis:
- We need to arrange 4 distinct objects in a line
- For the first position: 4 choices
- For the second position: 3 choices (one already placed)
- For the third position: 2 choices
- And so on...

Formula Application:
Number of arrangements = 4! = 4 × 3 × 2 × ... × 2 × 1

Calculation:
4! = 24

Key Concept: The factorial function represents the number of ways to arrange n distinct objects in a sequence.

Common Mistake: Don't confuse permutation (arrangement matters) with combination (arrangement doesn't matter).

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 = 1 (exact fixed points)

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

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(6,1) × D(5)
= 6 × 44
= 264

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: This problem uses the Fundamental Counting Principle (Multiplication Rule). When making sequential independent choices, multiply the number of options at each step.

Analysis:
- First choice: 3 options
- Second choice: 6 options
- Third choice: 3 options

Calculation:
Total ways = 3 × 6 × 3 = 54

Key Principle: For independent sequential events, multiply the number of choices at each stage.

Verification: Each of the 3 first choices can be paired with each of the 6 second choices (3×6=18), and each of these can be combined with any of the 3 third choices.

Step-by-Step Solution:

Concept: Inclusion-Exclusion Principle - when counting elements in the union of sets, add individual counts and subtract overcounted intersections.

Formula: |A ∪ B| = |A| + |B| - |A ∩ B|

Given:
- Range: 1 to 10
- Divisors: 3 and 2

Step 1 - Count numbers divisible by 3:
Numbers divisible by 3 = ⌊10/3⌋ = 3
These are: 3, 6, 9, ..., 9

Step 2 - Count numbers divisible by 2:
Numbers divisible by 2 = ⌊10/2⌋ = 5
These are: 2, 4, 6, ..., 10

Step 3 - Count numbers divisible by BOTH 3 AND 2:
Numbers divisible by LCM(3,2) = 6
Count = ⌊10/6⌋ = 1
(These are counted twice in steps 1 and 2)

Step 4 - Apply Inclusion-Exclusion:
Total = (divisible by 3) + (divisible by 2) - (divisible by both)
= 3 + 5 - 1
= 7

Visualization (Venn Diagram concept):
- Circle A: divisible by 3 (3 numbers)
- Circle B: divisible by 2 (5 numbers)
- Intersection: divisible by both (1 numbers)
- Union: 7 numbers

Key Principle: Subtract the intersection to avoid double counting.

Extension to Three Sets:
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |B ∩ C| - |A ∩ C| + |A ∩ B ∩ C|

Common Application: Finding numbers NOT divisible by either = 10 - 7 = 3

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: 9
- Group sizes: 8, 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 8 people from 9: C(9, 8) = 9

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

Continue for all groups:
C(9,8) = 9
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 9 × 1 (last group)
= 9

Simplified formula:
= 9! / (8! × 1!)
= 362880 / (40320 × 1)
= 9

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 = 9 = 9 ✓

Step-by-Step Solution:

Concept: Linear permutation of n distinct objects = n! (n factorial)

Analysis:
- We need to arrange 6 distinct objects in a line
- For the first position: 6 choices
- For the second position: 5 choices (one already placed)
- For the third position: 4 choices
- And so on...

Formula Application:
Number of arrangements = 6! = 6 × 5 × 4 × ... × 2 × 1

Calculation:
6! = 720

Key Concept: The factorial function represents the number of ways to arrange n distinct objects in a sequence.

Common Mistake: Don't confuse permutation (arrangement matters) with combination (arrangement doesn't matter).

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: 7
- Group sizes: 4, 2, 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 4 people from 7: C(7, 4) = 35

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

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

Step 3 - Multiply:
Total ways = 35 × 3 × 1 (last group)
= 105

Simplified formula:
= 7! / (4! × 2! × 1!)
= 5040 / (24 × 2 × 1)
= 105

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 = 7 = 7 ✓

Step-by-Step Solution:

Concept: Combination with constraints - selection from multiple groups with specific requirements.

Given:
- Men available: 7
- Women available: 6
- Committee size: 6
- Required: 3 men and 3 women

Strategy: Select from each group independently, then multiply (Multiplication Principle).

Step 1 - Select Men:
Choose 3 men from 7 men = C(7,3)
C(7,3) = 7! / [3! × 4!] = 35

Step 2 - Select Women:
Choose 3 women from 6 women = C(6,3)
C(6,3) = 6! / [3! × 3!] = 20

Step 3 - Apply Multiplication Principle:
Total ways = C(7,3) × C(6,3)
= 35 × 20
= 700

Key Principle: When selecting from different independent groups with specific requirements from each:
- Calculate selections from each group separately
- Multiply the results

Common Error: Don't add the combinations - multiply them! Each selection from one group can be paired with each selection from the other.

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
= 720

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

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

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: Distribution of distinct objects to distinct boxes - each object independently chooses a box.

Given:
- Distinct items: 7
- Distinct boxes: 3
- Empty boxes: Allowed

Strategy: Each item makes an independent choice of which box to go into.

Analysis:
- Item 1 can go into any of 3 boxes: 3 choices
- Item 2 can go into any of 3 boxes: 3 choices
- Item 3 can go into any of 3 boxes: 3 choices
- ...and so on for all 7 items

Formula: (number of boxes)^(number of items) = 3^7

Calculation:
Total ways = 3^7 = 2187

Key Distinction:
This is NOT a permutation or combination problem! It's a direct application of the multiplication principle.

Related Scenarios:
1. No empty boxes allowed (Surjection):
Use Inclusion-Exclusion: 3! × S(7,3)
where S(n,k) is the Stirling number of second kind

2. Identical items, distinct boxes:
This becomes a "stars and bars" problem: C(7+3-1, 3-1)

3. Distinct items, identical boxes (Partition):
Use Stirling numbers: Σ S(7,k) for k=1 to 3

Verification:
- With 1 box: answer should be 1 (all items in one box)
- With 7 boxes, one item: answer should be 7
- Our answer 2187 is reasonable: each item independently chooses from 3 options

Common Error: Don't use factorial or combination formulas here - items are making independent simultaneous choices.