Permutation & Combination - Intermediate Level: data interpretation 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: 9
- Women available: 8
- Committee size: 8
- 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 (8).

Valid Cases (Men, Women) and Calculation:

(5 Men, 3 Women): C(9,5) × C(8,3) = 126 × 56 = 7056
(6 Men, 2 Women): C(9,6) × C(8,2) = 84 × 28 = 2352
(7 Men, 1 Women): C(9,7) × C(8,1) = 36 × 8 = 288
(8 Men, 0 Women): C(9,8) × C(8,0) = 9 × 1 = 9

Final Calculation (Sum Rule):
Total ways = (Ways with 5 men) + (Ways with 6 men) + ...
= 7056 + 2352 + 288 + 9
= 9705

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: 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: 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: 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: 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: This is a combination problem because the order of selection doesn't matter.

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

Given:
- n = 10 (total items)
- r = 3 (items to select)

Calculation:
C(10,3) = 10! / [3! × 7!]
= 10! / [6 × 5040]
= 3628800 / [6 × 5040]
= 120

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

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

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

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

Step 1 - Total arrangements if all were distinct:
7! = 5040

Step 2 - Account for identical objects:
7! = 5040 / 2! = 2 / 3! = 6 / 2! = 2

Final Calculation:
= 210

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 7! = 5040.

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:

Concept: Permutation with repetition. When some objects are identical, we divide by the factorial of the number of repetitions.

Analysis of 'TREE':
- 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: 8
- Women available: 6
- 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 6 women = C(6,2)
C(6,2) = 6! / [2! × 4!] = 15

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

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: 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: This is a combination problem because the order of selection doesn't matter.

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

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

Calculation:
C(7,2) = 7! / [2! × 5!]
= 7! / [2 × 120]
= 5040 / [2 × 120]
= 21

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

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

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

Step-by-Step Solution:

Concept: Number formation with positional restrictions. The first digit cannot be 0 (otherwise it wouldn't be an 6-digit number).

Given:
- Number length: 6 digits
- Available digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (10 digits)
- Repetition: Allowed
- Constraint: First digit cannot be 0

Position-by-Position Analysis:

First digit (leftmost):
Cannot be 0 (would make it 5-digit number)
Choices: 1, 2, 3, 4, 5, 6, 7, 8, 9
Count: 9 choices

Second digit:
Can be any digit including 0
Choices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Count: 10 choices

Third digit through 6th digit:
Each can be any digit including 0
Count: 10 choices each

Apply Multiplication Principle:
Total numbers = 9 × 10 × 10 × ... × 10 (5 times)
= 9 × 10^5
= 9 × 100000
= 900000

Alternative Verification:
- Smallest 6-digit number: 100000 = 100000
- Largest 6-digit number: 999999 = 999999
- Total count: 999999 - 100000 + 1 = 900000

Related Problems:
1. No repetition: 9 × P(9,5) = 9 × 9!/4!
2. Odd numbers only: 9 × 10^4 × 5 (last digit: 1,3,5,7,9)
3. Even numbers only:
- If last digit 0: 9 × 10^4 × 1
- If last digit 2,4,6,8: 8 × 10^4 × 4
- Total: 9 × 10^4 + 8 × 4 × 10^4

Key Principle: When forming numbers:
- First digit has special restriction (can't be 0)
- Handle positional constraints carefully
- Use multiplication principle for independent choices

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

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

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

Step 3 - Calculate:
- Numerator: 5! = 120
- Denominator: 5! = 120
- Denominator value: 120

Final Calculation:
Coefficient = 120 / 120 = 1

Alternative interpretation: This equals the number of ways to arrange 5 items with:
5 of type x, 0 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: Number formation with positional restrictions. The first digit cannot be 0 (otherwise it wouldn't be an 7-digit number).

Given:
- Number length: 7 digits
- Available digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (10 digits)
- Repetition: Allowed
- Constraint: First digit cannot be 0

Position-by-Position Analysis:

First digit (leftmost):
Cannot be 0 (would make it 6-digit number)
Choices: 1, 2, 3, 4, 5, 6, 7, 8, 9
Count: 9 choices

Second digit:
Can be any digit including 0
Choices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Count: 10 choices

Third digit through 7th digit:
Each can be any digit including 0
Count: 10 choices each

Apply Multiplication Principle:
Total numbers = 9 × 10 × 10 × ... × 10 (6 times)
= 9 × 10^6
= 9 × 1000000
= 9000000

Alternative Verification:
- Smallest 7-digit number: 1000000 = 1000000
- Largest 7-digit number: 9999999 = 9999999
- Total count: 9999999 - 1000000 + 1 = 9000000

Related Problems:
1. No repetition: 9 × P(9,6) = 9 × 9!/3!
2. Odd numbers only: 9 × 10^5 × 5 (last digit: 1,3,5,7,9)
3. Even numbers only:
- If last digit 0: 9 × 10^5 × 1
- If last digit 2,4,6,8: 8 × 10^5 × 4
- Total: 9 × 10^5 + 8 × 4 × 10^5

Key Principle: When forming numbers:
- First digit has special restriction (can't be 0)
- Handle positional constraints carefully
- Use multiplication principle for independent choices

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

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

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

Continue for all groups:
C(11,5) = 462
C(6,3) = 20
C(3,2) = 3
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 462 × 20 × 3 × 1 (last group)
= 27720

Simplified formula:
= 11! / (5! × 3! × 2! × 1!)
= 39916800 / (120 × 6 × 2 × 1)
= 27720

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

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

Calculation:
Total ways = 6 × 4 × 3 = 72

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

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