Permutation & Combination - Expert Level: logical deduction EXPERT

Step-by-Step Solution:

Concept: Permutation with fixed position constraint.

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

Given:
- Total people: 8
- 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 7 people can be arranged in 7! ways

Calculation:
Total arrangements = 1 × 7!
= 5040
= 5040

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

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

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 (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: 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: Combination with constraints - selection from multiple groups with specific requirements.

Given:
- Men available: 6
- Women available: 5
- Committee size: 4
- Required: 2 men and 2 women

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

Step 1 - Select Men:
Choose 2 men from 6 men = C(6,2)
C(6,2) = 6! / [2! × 4!] = 15

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

Step 3 - Apply Multiplication Principle:
Total ways = C(6,2) × C(5,2)
= 15 × 10
= 150

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: Combination with mandatory inclusion constraint.

Given:
- Total people: 10
- Committee size: 6
- Must include: 3 specific people

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

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

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

Step 2 - Select Remaining Members:
Choose 3 people from remaining 7 people:
C(7,3) = 35

Calculation:
C(7,3) = (7)! / [3! × (4)!]
= 5040 / [6 × 24]
= 35

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

Related Problem Types:

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

2. At least one specific person:
Total ways - Ways without that person
= C(10,6) - C(10-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: 35 ways

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: Partitioning into groups of specified sizes. When group sizes are different, groups are automatically distinguishable by size.

Given:
- Total people: 10
- Group sizes: 4, 3, 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 10: C(10, 4) = 210

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

Continue for all groups:
C(10,4) = 210
C(6,3) = 20
C(3,2) = 3
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 210 × 20 × 3 × 1 (last group)
= 12600

Simplified formula:
= 10! / (4! × 3! × 2! × 1!)
= 3628800 / (24 × 6 × 2 × 1)
= 12600

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

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)^5
- Desired term: the term x^3 * y^2
- Exponents: x = 3, y = 2

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

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

Step 3 - Calculate:
- Numerator: 5! = 120
- Denominator: 3! × 2! = 6 × 2
- Denominator value: 12

Final Calculation:
Coefficient = 120 / 12 = 10

Alternative interpretation: This equals the number of ways to arrange 5 items with:
3 of type x, 2 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^5 = 32

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: 5 options
- Second choice: 6 options
- Third choice: 3 options

Calculation:
Total ways = 5 × 6 × 3 = 90

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

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

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: 8! = 40320 ways
- But in a circle: we fix one person's position as reference
- Remaining 7 people can be arranged in 7! ways

Calculation:
Circular arrangements = (8-1)! = 7! = 5040

Intuition: Fix one person at a position (say 12 o'clock). Now arrange the remaining 7 people in the 7 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: 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: 5
- Vowels: 2
- Constraint: No two vowels together

Step 1 - Arrange Consonants:
Arrange 5 consonants: 5! = 120 ways

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

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

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

Step 4 - Apply Multiplication Principle:
Total arrangements = 120 × 15 × 2
= 120 × 15 × 2
= 3600

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

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

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: Counting even/odd numbers with distinct digits.

Given: 5-digit numbers, distinct digits, odd numbers.

Case Analysis for odd numbers:

- Last digit: 1,3,5,7,9 (5 choices)
- First digit: cannot be 0 and cannot be last digit (8 choices)
- Remaining 3 digits: choose from remaining 8 digits and arrange
- Ways = 5 × 8 × P(8, 3) = 5 × 8 × 336 = 13440

Key Principle: Always handle first digit (can't be 0) and last digit (parity constraint) separately.

Step-by-Step Solution:

Concept: Distribution of distinct objects to distinct boxes - each object independently chooses a box.

Given:
- Distinct items: 6
- Distinct boxes: 4
- Empty boxes: Allowed

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

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

Formula: (number of boxes)^(number of items) = 4^6

Calculation:
Total ways = 4^6 = 4096

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: 4! × S(6,4)
where S(n,k) is the Stirling number of second kind

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

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

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

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

Step-by-Step Solution:

Concept: For necklaces with identical beads, we use Burnside's Lemma.

Given distribution: [2, 3, 3]

Result: 2520 distinct necklaces.

Note: Full calculation requires summing over all rotation and reflection symmetries, which is complex for general cases.

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 = 3 (items to select)

Calculation:
C(9,3) = 9! / [3! × 6!]
= 9! / [6 × 720]
= 362880 / [6 × 720]
= 84

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

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: 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:

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

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

Given:
- n = 6 (total items)
- r = 2 (items to select)

Calculation:
C(6,2) = 6! / [2! × 4!]
= 6! / [2 × 24]
= 720 / [2 × 24]
= 15

Alternative Method (using simplified calculation):
C(6,2) = (6 × 5 × ... × 5) / 2!

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

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

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: 8! = 40320 ways
- But in a circle: we fix one person's position as reference
- Remaining 7 people can be arranged in 7! ways

Calculation:
Circular arrangements = (8-1)! = 7! = 5040

Intuition: Fix one person at a position (say 12 o'clock). Now arrange the remaining 7 people in the 7 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.