Permutation & Combination - Intermediate-Advanced Level: problem decomposition INTERMEDIATE-ADVANCED

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

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

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

Calculation:
C(9,2) = 9! / [2! × 7!]
= 9! / [2 × 5040]
= 362880 / [2 × 5040]
= 36

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

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

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

Step-by-Step Solution:

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

Given:
- Men available: 8
- Women available: 5
- Committee size: 5
- Required: 2 men and 3 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 3 women from 5 women = C(5,3)
C(5,3) = 5! / [3! × 2!] = 10

Step 3 - Apply Multiplication Principle:
Total ways = C(8,2) × C(5,3)
= 28 × 10
= 280

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: [4, 3, 3]

Result: 181440 distinct necklaces.

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

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

Given:
- Men available: 7
- Women available: 6
- Committee size: 5
- Required: 2 men and 3 women

Strategy: Select from each group independently, then multiply (Multiplication Principle).

Step 1 - Select Men:
Choose 2 men from 7 men = C(7,2)
C(7,2) = 7! / [2! × 5!] = 21

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

Step 3 - Apply Multiplication Principle:
Total ways = C(7,2) × C(6,3)
= 21 × 20
= 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: 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: 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: 3 options

Calculation:
Total ways = 5 × 6 × 3 = 90

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

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: 6
- Women available: 5
- Committee size: 5
- Required: 2 men and 3 women

Strategy: Select from each group independently, then multiply (Multiplication Principle).

Step 1 - Select Men:
Choose 2 men from 6 men = C(6,2)
C(6,2) = 6! / [2! × 4!] = 15

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,2) × C(5,3)
= 15 × 10
= 150

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

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

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

Step 3 - Apply multiplication principle:
Total = C(7,1) × D(6)
= 7 × 265
= 1855

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=7:
- D(7,0) = 1854
- D(7,1) = 1855
- D(7,2) = 924
- ... and so on.

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

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

Calculation:
Total ways = 4 × 4 × 5 = 80

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 5 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: 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: 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 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 3 collinear points: C(3,3)
C(3,3) = 3! / [3! × 0!] = 1

Step 3 - Apply Complementary Counting:
Valid triangles = Total selections - Invalid selections
= 120 - 1
= 119

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: 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: 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: Derangement - permutation where no element appears in its original position. Denoted as D(n) or !n.

Given:
- Number of items: 4
- 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

Answer: D(4) = 9

Intuitive Understanding:
Total arrangements = 4! = 24
Derangements = 9
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 4: 24/e ≈ 9 ≈ 9

Common Error: Don't subtract n! - n, that's not derangement count.

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

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

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

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

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

Visualization (Venn Diagram concept):
- Circle A: divisible by 2 (5 numbers)
- Circle B: divisible by 3 (3 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: 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: 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 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 3 collinear points: C(3,3)
C(3,3) = 3! / [3! × 0!] = 1

Step 3 - Apply Complementary Counting:
Valid triangles = Total selections - Invalid selections
= 120 - 1
= 119

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: 7, 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 7 people from 10: C(10, 7) = 120

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

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

Step 3 - Multiply:
Total ways = 120 × 3 × 1 (last group)
= 360

Simplified formula:
= 10! / (7! × 2! × 1!)
= 3628800 / (5040 × 2 × 1)
= 360

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 ✓