Permutation & Combination - Advanced Level: time management ADVANCED

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: 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$): 7
- Step 1: Normal circular arrangements (rotations same) = $(n-1)!$ = 720
- Step 2: Account for reflection (flips) by dividing by 2.

Calculation:
Arrangements = $\frac{(7-1)!}2$
= $\frac{720}2$
= 360

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

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

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

Continue for all groups:
C(10,5) = 252
C(5,3) = 10
C(2,2) = 1 (last group)

Step 3 - Multiply:
Total ways = 252 × 10 × 1 (last group)
= 2520

Simplified formula:
= 10! / (5! × 3! × 2!)
= 3628800 / (120 × 6 × 2)
= 2520

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

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 (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: 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: 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: 4 options
- Second choice: 4 options
- Third choice: 2 options

Calculation:
Total ways = 4 × 4 × 2 = 32

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

Verification: Each of the 4 first choices can be paired with each of the 4 second choices (4×4=16), and each of these can be combined with any of the 2 third 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 = 6 (total items)
- r = 2 (items to select)

Calculation:
C(6,2) = 6! / [2! × 4!]
= 6! / [2 × 24]
= 720 / [2 × 24]
= 15

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

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

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

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: 8, 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 8 people from 11: C(11, 8) = 165

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

Continue for all groups:
C(11,8) = 165
C(3,2) = 3
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 165 × 3 × 1 (last group)
= 495

Simplified formula:
= 11! / (8! × 2! × 1!)
= 39916800 / (40320 × 2 × 1)
= 495

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

Given distribution: [4, 2]

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

Given distribution: [2, 2, 4]

Result: 2520 distinct necklaces.

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

Step-by-Step Solution:

Concept: Counting even/odd numbers with distinct digits.

Given: 4-digit numbers, distinct digits, even numbers.

Case Analysis for even numbers:

Case 1: Last digit = 0
- First digit: 1-9 (9 choices)
- Remaining 2 digits: choose from remaining 8 digits and arrange
- Ways = 9 × P(8, 2) = 9 × 56 = 504

Case 2: Last digit = 2,4,6,8 (4 choices)
- First digit: cannot be 0 and cannot be last digit (8 choices)
- Remaining 2 digits: choose from remaining 8 digits and arrange
- Ways = 4 × 8 × P(8, 2) = 1792

Total = 504 + 1792 = 2296

Key Principle: Always handle first digit (can't be 0) and last digit (parity constraint) separately.

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 'ROOM':
- 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: 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: 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: 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 (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 = 1 (exact fixed points)

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

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

Step 3 - Apply multiplication principle:
Total = C(5,1) × D(4)
= 5 × 9
= 45

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