Permutation & Combination - Intermediate Level: speed building INTERMEDIATE

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

Calculation:
Total ways = 3 × 6 × 2 = 36

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

Verification: Each of the 3 first choices can be paired with each of the 6 second choices (3×6=18), and each of these can be combined with any of the 2 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 '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: Handshake problem with selective participation.

Given:
- Total: 10 people
- VIPs: 4 (shake with everyone)
- Non-VIPs: 6 (only shake with other non-VIPs)

Step 1 - Total possible handshakes without restrictions:
Total possible = C(10, 2) = 10×9/2 = 45

Step 2 - Handshakes that DON'T occur:
Non-VIPs shaking with VIPs (these don't happen because non-VIPs only shake with non-VIPs)
Non-VIP to VIP handshakes = 6 × 4 = 24

Step 3 - Subtract restricted handshakes:
Actual handshakes = Total possible - Forbidden handshakes
= 45 - 24
= 21

Alternative direct count:
- VIP to VIP: C(4, 2) = 6
- VIP to Non-VIP: 0 (forbidden)
- Non-VIP to Non-VIP: C(6, 2) = 15
Total = 6 + 15 = 21

Verification: Both methods give the same result.

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 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: Counting numbers with distinct digits greater than a threshold.

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

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

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: 12
- Group sizes: 5, 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 5 people from 12: C(12, 5) = 792

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

Continue for all groups:
C(12,5) = 792
C(7,4) = 35
C(3,2) = 3
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 792 × 35 × 3 × 1 (last group)
= 83160

Simplified formula:
= 12! / (5! × 4! × 2! × 1!)
= 479001600 / (120 × 24 × 2 × 1)
= 83160

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

Step-by-Step Solution:

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

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

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

Step 1 - Select Men:
Choose 3 men from 7 men = C(7,3)
C(7,3) = 7! / [3! × 4!] = 35

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

Step 3 - Apply Multiplication Principle:
Total ways = C(7,3) × C(5,2)
= 35 × 10
= 350

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: Handshake problem - each handshake involves 2 people, and order doesn't matter.

Given: 13 people

Method 1 - Combination:
Number of handshakes = Number of ways to choose 2 people from 13
= C(13, 2) = 13! / (2! × 11!) = 13×12/2

Method 2 - Counting per person:
Each person shakes hands with 12 others
Total count: 13 × 12 = 156
But each handshake counted twice, so divide by 2: 156/2

Calculation:
= 13×12/2 = 78
= 78

Key Formula: Number of handshakes = C(n, 2) = n(n-1)/2

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: 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: 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: 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: Counting numbers with distinct digits and divisibility constraint.

Given:
- Number length: 4 digits
- Digits must be distinct
- Constraint: Divisible by 10

Step 1 - Determine last digit constraint:
Divisible by 10 means:
Last digit must be 0

Step 2 - Count valid numbers:
For divisor 10, the count is 648

Step 3 - Verify distinctness:
All digits in the number are different (no repetition allowed).

Calculation: 648

Key Principle: When forming numbers with distinct digits:
- First digit cannot be 0
- Handle last digit constraints first
- Use permutations for remaining positions

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:

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

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
= 56 - 1
= 55

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

Verification: Answer should be less than C(8,3) = 56 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 (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: 6
- Constraint: At least 4 men

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

Valid Cases (Men, Women) and Calculation:

(4 Men, 2 Women): C(8,4) × C(7,2) = 70 × 21 = 1470
(5 Men, 1 Women): C(8,5) × C(7,1) = 56 × 7 = 392
(6 Men, 0 Women): C(8,6) × C(7,0) = 28 × 1 = 28

Final Calculation (Sum Rule):
Total ways = (Ways with 4 men) + (Ways with 5 men) + ...
= 1470 + 392 + 28
= 1890

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$).