Permutation & Combination - Intermediate Level: accuracy improvement INTERMEDIATE

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: 8
- Women available: 7
- Committee size: 7
- Constraint: At least 5 men

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

Valid Cases (Men, Women) and Calculation:

(5 Men, 2 Women): C(8,5) × C(7,2) = 56 × 21 = 1176
(6 Men, 1 Women): C(8,6) × C(7,1) = 28 × 7 = 196
(7 Men, 0 Women): C(8,7) × C(7,0) = 8 × 1 = 8

Final Calculation (Sum Rule):
Total ways = (Ways with 5 men) + (Ways with 6 men) + ...
= 1176 + 196 + 8
= 1380

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

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

Given:
- Men available: 8
- Women available: 8
- Committee size: 6
- Constraint: At least 3 men

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

Valid Cases (Men, Women) and Calculation:

(3 Men, 3 Women): C(8,3) × C(8,3) = 56 × 56 = 3136
(4 Men, 2 Women): C(8,4) × C(8,2) = 70 × 28 = 1960
(5 Men, 1 Women): C(8,5) × C(8,1) = 56 × 8 = 448
(6 Men, 0 Women): C(8,6) × C(8,0) = 28 × 1 = 28

Final Calculation (Sum Rule):
Total ways = (Ways with 3 men) + (Ways with 4 men) + ...
= 3136 + 1960 + 448 + 28
= 5572

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

Calculation:
Total ways = 5 × 6 × 2 = 60

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 2 third choices.

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

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

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

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

Step 4 - Apply Inclusion-Exclusion:
Total = (divisible by 3) + (divisible by 2) - (divisible by both)
= 4 + 6 - 2
= 8

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

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

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

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

Step 3 - Count numbers divisible by BOTH 3 AND 5:
Numbers divisible by LCM(3,5) = 15
Count = ⌊12/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)
= 4 + 2 - 0
= 6

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

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

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

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

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: 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: 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: 10
- Collinear points: 4

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 10 points: C(10,3)
C(10,3) = 10! / [3! × 7!] = 120

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

Step 3 - Apply Complementary Counting:
Valid triangles = Total selections - Invalid selections
= 120 - 4
= 116

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

Verification: Answer should be less than C(10,3) = 120 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: 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: 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: 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)^7
- Desired term: the term y^2 * z^5
- Exponents: x = 0, y = 2, z = 5

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

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

Step 3 - Calculate:
- Numerator: 7! = 5040
- Denominator: 2! × 5! = 2 × 120
- Denominator value: 240

Final Calculation:
Coefficient = 5040 / 240 = 21

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

Step-by-Step Solution:

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

Given:
- Men available: 6
- Women available: 5
- 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 6 men = C(6,3)
C(6,3) = 6! / [3! × 3!] = 20

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

Step 3 - Apply Multiplication Principle:
Total ways = C(6,3) × C(5,3)
= 20 × 10
= 200

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: For necklaces with identical beads, we use Burnside's Lemma.

Given distribution: [2, 4]

Result: 60 distinct necklaces.

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

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: 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: Rank of a word in dictionary order - counting how many words come before it alphabetically.

Given word: TIGER

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: E G I R T

Step-by-Step Calculation:

Position 1 (current letter: T):
Available letters: E G I R T
If we place 'E' here: 24 arrangements possible
If we place 'G' here: 24 arrangements possible
If we place 'I' here: 24 arrangements possible
If we place 'R' here: 24 arrangements possible
Subtotal arrangements before 'T': 96
Position 2 (current letter: I):
Available letters: E G I R
If we place 'E' here: 6 arrangements possible
If we place 'G' here: 6 arrangements possible
Subtotal arrangements before 'I': 12
Position 3 (current letter: G):
Available letters: E G R
If we place 'E' here: 2 arrangements possible
Subtotal arrangements before 'G': 2
Position 4 (current letter: E):
Available letters: E R
Position 5 (current letter: R):
Available letters: R

Final Rank: 111

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

Given:
- Total people: 11
- 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: 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 3 people from remaining 8 people:
C(8,3) = 56

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

Alternative Approach - Verification:
Think of it as: "We've used 3 spots, now choose 3 more from 8 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: 56 ways