Permutation & Combination - Intermediate-Advanced Level: pattern recognition INTERMEDIATE-ADVANCED

Step-by-Step Solution:

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

Given:
- Men available: 8
- Women available: 4
- 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 8 men = C(8,2)
C(8,2) = 8! / [2! × 6!] = 28

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

Step 3 - Apply Multiplication Principle:
Total ways = C(8,2) × C(4,2)
= 28 × 6
= 168

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: 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 8
- Divisors: 2 and 5

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

Step 2 - Count numbers divisible by 5:
Numbers divisible by 5 = ⌊8/5⌋ = 1
These are: 5, 10, 15, ..., 5

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

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

Visualization (Venn Diagram concept):
- Circle A: divisible by 2 (4 numbers)
- Circle B: divisible by 5 (1 numbers)
- Intersection: divisible by both (0 numbers)
- Union: 5 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 = 8 - 5 = 3

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 8
- Divisors: 2 and 5

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

Step 2 - Count numbers divisible by 5:
Numbers divisible by 5 = ⌊8/5⌋ = 1
These are: 5, 10, 15, ..., 5

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

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

Visualization (Venn Diagram concept):
- Circle A: divisible by 2 (4 numbers)
- Circle B: divisible by 5 (1 numbers)
- Intersection: divisible by both (0 numbers)
- Union: 5 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 = 8 - 5 = 3

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 (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 = 5 (total elements)
- k = 2 (exact fixed points)

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

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

Step 3 - Apply multiplication principle:
Total = C(5,2) × D(3)
= 10 × 2
= 20

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=5:
- D(5,0) = 44
- D(5,1) = 45
- D(5,2) = 20
- ... and so on.

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

Step-by-Step Solution:

Concept: Geometrical combination with constraint. Three collinear points cannot form a triangle.

Strategy: Use complementary counting:
Total valid triangles = All possible triangles - Invalid triangles

Given:
- Total points: 12
- Collinear points: 3

Triangle Formation Rule: We need exactly 3 non-collinear points to form a triangle.

Step 1 - Calculate Total Possible Selections:
Selecting any 3 points from 12 points: C(12,3)
C(12,3) = 12! / [3! × 9!] = 220

Step 2 - Calculate Invalid Triangles:
3 collinear points don't form a triangle.
Selecting 3 points from 3 collinear points: C(3,3)
C(3,3) = 3! / [3! × 0!] = 1

Step 3 - Apply Complementary Counting:
Valid triangles = Total selections - Invalid selections
= 220 - 1
= 219

Key Technique: Complementary counting is often easier than direct counting when dealing with restrictions.

Verification: Answer should be less than C(12,3) = 220 since we have a constraint.

Related Concepts:
- For lines from n points: C(n,2) - (collinear points consideration)
- For quadrilaterals: C(n,4) with appropriate constraints

Step-by-Step Solution:

Concept: Combination with mandatory inclusion constraint.

Given:
- Total people: 11
- Committee size: 5
- Must include: 3 specific people

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

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

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 2 people from remaining 8 people:
C(8,2) = 28

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

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

Related Problem Types:

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

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

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

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

Answer: 28 ways

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

Step 1 - Total arrangements if all were distinct:
15! = 1307674368000

Step 2 - Account for identical objects:
15! = 1307674368000 / 4! = 24 / 4! = 24 / 3! = 6 / 3! = 6

Final Calculation:
= 63063000

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 15! = 1307674368000.

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 9
- Divisors: 3 and 5

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

Step 2 - Count numbers divisible by 5:
Numbers divisible by 5 = ⌊9/5⌋ = 1
These are: 5, 10, 15, ..., 5

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

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

Visualization (Venn Diagram concept):
- Circle A: divisible by 3 (3 numbers)
- Circle B: divisible by 5 (1 numbers)
- Intersection: divisible by both (0 numbers)
- Union: 4 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 = 9 - 4 = 5

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: 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 (Sum Rule):

Concept: 'At least' problems require finding the sum of ways for all valid, mutually exclusive cases.

Given:
- Men available: 9
- Women available: 7
- Committee size: 7
- Constraint: At least 4 men

Strategy: We sum the ways for all cases from exactly 4 men up to the maximum possible number of men (7).

Valid Cases (Men, Women) and Calculation:

(4 Men, 3 Women): C(9,4) × C(7,3) = 126 × 35 = 4410
(5 Men, 2 Women): C(9,5) × C(7,2) = 126 × 21 = 2646
(6 Men, 1 Women): C(9,6) × C(7,1) = 84 × 7 = 588
(7 Men, 0 Women): C(9,7) × C(7,0) = 36 × 1 = 36

Final Calculation (Sum Rule):
Total ways = (Ways with 4 men) + (Ways with 5 men) + ...
= 4410 + 2646 + 588 + 36
= 7680

Key Principle: Use the Sum Rule (addition) because the cases are mutually exclusive (you cannot simultaneously select exactly $k$ men and exactly $j$ men, where $k
e j$).

Step-by-Step Solution:

Concept: Combination with mandatory inclusion constraint.

Given:
- Total people: 12
- 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: 12 - 3 = 9

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 9 people:
C(9,3) = 84

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

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

Related Problem Types:

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

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

Step-by-Step Solution:

Concept: Permutation with restriction - specific position must have certain type of letter.

Strategy: Fix the restricted position first, then arrange the remaining letters.

Analysis of 'EQUATION':
- Total letters: 8
- Vowels: E, U, A, I, O = 5 vowels
- First position must be a vowel

Step 1 - Fix First Position:
Choose a vowel for first position: 5 choices

Step 2 - Arrange Remaining:
Remaining 7 letters can be arranged in 7! ways
7! = 5040

Calculation:
Total arrangements = 5 × 5040 = 10080

Key Strategy: When dealing with restrictions:
1. Handle the restriction first (fix the constrained position)
2. Arrange the remaining elements freely
3. Multiply the results

Verification: This should be less than the total arrangements (8! = 40320) since we've added a constraint.

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

Step 1 - Total arrangements if all were distinct:
13! = 6227020800

Step 2 - Account for identical objects:
13! = 6227020800 / 2! = 2 / 2! = 2 / 4! = 24 / 3! = 6 / 2! = 2

Final Calculation:
= 5405400

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 13! = 6227020800.

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 11
- Divisors: 3 and 2

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

Step 2 - Count numbers divisible by 2:
Numbers divisible by 2 = ⌊11/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 = ⌊11/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 = 11 - 7 = 4

Step-by-Step Solution:

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

Given:
- Distinct items: 6
- 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 6 items

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

Calculation:
Total ways = 3^6 = 729

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(6,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(6+3-1, 3-1)

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

Verification:
- With 1 box: answer should be 1 (all items in one box)
- With 6 boxes, one item: answer should be 6
- Our answer 729 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 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.