Permutation & Combination - Beginner-Intermediate Level: logical deduction BEGINNER-INTERMEDIATE

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: 2, Type 2: 4, Type 3: 3, Type 4: 3, Type 5: 2

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

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

Final Calculation:
= 25225200

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: 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: 3
- 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 3 gaps from 5 available gaps: C(5,3) = 10
Arrange 3 vowels in chosen gaps: 3! = 6

Step 4 - Apply Multiplication Principle:
Total arrangements = 24 × 10 × 6
= 24 × 10 × 6
= 1440

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

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

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:

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

Calculation:
Circular arrangements = (5-1)! = 4! = 24

Intuition: Fix one person at a position (say 12 o'clock). Now arrange the remaining 4 people in the 4 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: 16
- Distribution: Type 1: 4, Type 2: 4, Type 3: 2, Type 4: 4, Type 5: 2

Step 1 - Total arrangements if all were distinct:
16! = 20922789888000

Step 2 - Account for identical objects:
16! = 20922789888000 / 4! = 24 / 4! = 24 / 2! = 2 / 4! = 24 / 2! = 2

Final Calculation:
= 378378000

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 16! = 20922789888000.

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

Given:
- Total people: 12
- Group sizes: 6, 4, 2
- 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 6 people from 12: C(12, 6) = 924

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

Continue for all groups:
C(12,6) = 924
C(6,4) = 15
C(2,2) = 1 (last group)

Step 3 - Multiply:
Total ways = 924 × 15 × 1 (last group)
= 13860

Simplified formula:
= 12! / (6! × 4! × 2!)
= 479001600 / (720 × 24 × 2)
= 13860

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

Step-by-Step Solution:

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

Given word: SMART

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 M R S T

Step-by-Step Calculation:

Position 1 (current letter: S):
Available letters: A M R S T
If we place 'A' here: 24 arrangements possible
If we place 'M' here: 24 arrangements possible
If we place 'R' here: 24 arrangements possible
Subtotal arrangements before 'S': 72
Position 2 (current letter: M):
Available letters: A M R T
If we place 'A' here: 6 arrangements possible
Subtotal arrangements before 'M': 6
Position 3 (current letter: A):
Available letters: A R T
Position 4 (current letter: R):
Available letters: R T
Position 5 (current letter: T):
Available letters: T

Final Rank: 79

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: 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: 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: 8
- Distribution: Type 1: 3, Type 2: 3, Type 3: 2

Step 1 - Total arrangements if all were distinct:
8! = 40320

Step 2 - Account for identical objects:
8! = 40320 / 3! = 6 / 3! = 6 / 2! = 2

Final Calculation:
= 560

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 8! = 40320.

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

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

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

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

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

Step 3 - Apply Multiplication Principle:
Total ways = C(6,3) × C(6,2)
= 20 × 15
= 300

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

Calculation:
C(8,2) = 8! / [2! × 6!]
= 8! / [2 × 720]
= 40320 / [2 × 720]
= 28

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

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: Derangement - permutation where no element appears in its original position. Denoted as D(n) or !n.

Given:
- Number of items: 5
- 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
D(5) = (5-1)[D(4) + D(3)] = 4 × [9 + 2] = 44

Answer: D(5) = 44

Intuitive Understanding:
Total arrangements = 5! = 120
Derangements = 44
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 5: 120/e ≈ 44 ≈ 44

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

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

Given:
- Total people: 9
- Group sizes: 5, 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 5 people from 9: C(9, 5) = 126

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

Continue for all groups:
C(9,5) = 126
C(4,3) = 4
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 126 × 4 × 1 (last group)
= 504

Simplified formula:
= 9! / (5! × 3! × 1!)
= 362880 / (120 × 6 × 1)
= 504

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: Permutation with repetition. When some objects are identical, we divide by the factorial of the number of repetitions.

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

Given:
- Total people: 12
- Group sizes: 6, 5, 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 6 people from 12: C(12, 6) = 924

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

Continue for all groups:
C(12,6) = 924
C(6,5) = 6
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 924 × 6 × 1 (last group)
= 5544

Simplified formula:
= 12! / (6! × 5! × 1!)
= 479001600 / (720 × 120 × 1)
= 5544

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