Permutation & Combination - Advanced Level: quick solving techniques ADVANCED

Step-by-Step Solution:

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

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

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

Calculation:
Total ways = 4^5 = 1024

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(5,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(5+4-1, 4-1)

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

Verification:
- With 1 box: answer should be 1 (all items in one box)
- With 5 boxes, one item: answer should be 5
- Our answer 1024 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 (Stars and Bars):

Concept: This problem is equivalent to finding the number of non-negative integer solutions to $x_1 + x_2 + \dots + x_{k} = {n}$. This is a distribution problem of identical items ({n} 'stars') into distinct containers ({k} 'bins') using {k-1} separators ('bars').

Formula: The number of solutions is $\text{C}(n + k - 1, k - 1)$.
- $n$ = number of identical items (stars) = {n}
- $k$ = number of distinct recipients (bins) = {k}

Calculation:
Total arrangements = $\text{C}({n} + {k} - 1, {k} - 1)$
= $\text{C}({n + k - 1}, {k - 1})$
= {answer}

Key Distinction:
- Identical Items, Distinct Boxes (Stars and Bars): $\text{C}(n+k-1, k-1)$
- Distinct Items, Distinct Boxes (Distribution): $k^n$

Verification: This method guarantees that all solutions are non-negative ($x_i \ge 0$).

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: Number formation with positional restrictions. The first digit cannot be 0 (otherwise it wouldn't be an 5-digit number).

Given:
- Number length: 5 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 4-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 5th digit:
Each can be any digit including 0
Count: 10 choices each

Apply Multiplication Principle:
Total numbers = 9 × 10 × 10 × ... × 10 (4 times)
= 9 × 10^4
= 9 × 10000
= 90000

Alternative Verification:
- Smallest 5-digit number: 10000 = 10000
- Largest 5-digit number: 99999 = 99999
- Total count: 99999 - 10000 + 1 = 90000

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

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: Number formation with positional restrictions. The first digit cannot be 0 (otherwise it wouldn't be an 5-digit number).

Given:
- Number length: 5 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 4-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 5th digit:
Each can be any digit including 0
Count: 10 choices each

Apply Multiplication Principle:
Total numbers = 9 × 10 × 10 × ... × 10 (4 times)
= 9 × 10^4
= 9 × 10000
= 90000

Alternative Verification:
- Smallest 5-digit number: 10000 = 10000
- Largest 5-digit number: 99999 = 99999
- Total count: 99999 - 10000 + 1 = 90000

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

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: 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: 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: 5 options
- Third choice: 2 options

Calculation:
Total ways = 5 × 5 × 2 = 50

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 5 second choices (5×5=25), and each of these can be combined with any of the 2 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: 6! = 720 ways
- But in a circle: we fix one person's position as reference
- Remaining 5 people can be arranged in 5! ways

Calculation:
Circular arrangements = (6-1)! = 5! = 120

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

Calculation:
C(10,4) = 10! / [4! × 6!]
= 10! / [24 × 720]
= 3628800 / [24 × 720]
= 210

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

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

Step 4 - Apply Multiplication Principle:
Total arrangements = 120 × 20 × 6
= 120 × 20 × 6
= 14400

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

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

Step-by-Step Solution:

Concept: Counting numbers with distinct digits greater than a threshold.

Step 1 - Total distinct-digit numbers:
First digit: 1-9 (9 choices)
Remaining 3 digits: choose and arrange from remaining 9 digits
Total = 9 × P(9, 3) = 9 × 504 = 4536

Step 2 - Count those > 5387:
Approximately half of all numbers will be greater than the median.
Answer ≈ 2268

Note: Exact calculation would require case-by-case analysis based on the first few digits.

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

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

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

Step 3 - Apply Multiplication Principle:
Total ways = C(8,3) × C(4,3)
= 56 × 4
= 224

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: Fixing a specific digit at a specific position.

Given:
- Number length: 5
- Digit 9 fixed at position 3
- All digits distinct

Step 1 - Handle position 3:

Position 3 (not first): Fixed as 9 (1 choice)
- First digit: cannot be 0 and cannot be 9 (8 choices)
- Remaining 3 positions: choose from remaining 8 digits and arrange
- Ways = 8 × P(8, 3) = 8 × 336 = 2688


Calculation: 2688

Key Point: When fixing a digit in first position, it cannot be 0.

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

Calculation:
C(8,4) = 8! / [4! × 4!]
= 8! / [24 × 24]
= 40320 / [24 × 24]
= 70

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

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 (Stars and Bars):

Concept: This problem is equivalent to finding the number of non-negative integer solutions to $x_1 + x_2 + \dots + x_{k} = {n}$. This is a distribution problem of identical items ({n} 'stars') into distinct containers ({k} 'bins') using {k-1} separators ('bars').

Formula: The number of solutions is $\text{C}(n + k - 1, k - 1)$.
- $n$ = number of identical items (stars) = {n}
- $k$ = number of distinct recipients (bins) = {k}

Calculation:
Total arrangements = $\text{C}({n} + {k} - 1, {k} - 1)$
= $\text{C}({n + k - 1}, {k - 1})$
= {answer}

Key Distinction:
- Identical Items, Distinct Boxes (Stars and Bars): $\text{C}(n+k-1, k-1)$
- Distinct Items, Distinct Boxes (Distribution): $k^n$

Verification: This method guarantees that all solutions are non-negative ($x_i \ge 0$).

Step-by-Step Solution:

Concept: Combination with mandatory inclusion constraint.

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

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

Analysis:
We need to select 5 people total, with 2 already fixed.
- Fixed positions: 2 (these specific people are already in)
- Remaining positions to fill: 5 - 2 = 3
- 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 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 2 spots, now choose 3 more from 9 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: 84 ways

Step-by-Step Solution:

Concept: Counting numbers with distinct digits greater than a threshold.

Step 1 - Total distinct-digit numbers:
First digit: 1-9 (9 choices)
Remaining 4 digits: choose and arrange from remaining 9 digits
Total = 9 × P(9, 4) = 9 × 3024 = 27216

Step 2 - Count those > 10146:
Approximately half of all numbers will be greater than the median.
Answer ≈ 13608

Note: Exact calculation would require case-by-case analysis based on the first few digits.

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

Step 1 - Total arrangements if all were distinct:
6! = 720

Step 2 - Account for identical objects:
6! = 720 / 2! = 2 / 2! = 2 / 2! = 2

Final Calculation:
= 90

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 6! = 720.