Permutation & Combination - Beginner Level: core concepts BEGINNER

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 = 2 (exact fixed points)

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

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

Step 3 - Apply multiplication principle:
Total = C(7,2) × D(5)
= 21 × 44
= 924

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

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

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

Continue for all groups:
C(12,6) = 924
C(6,5) = 6
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 924 × 6 × 1 (last group)
= 5544

Simplified formula:
= 12! / (6! × 5! × 1!)
= 479001600 / (720 × 120 × 1)
= 5544

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: 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 12
- Divisors: 3 and 5

Step 1 - Count numbers divisible by 3:
Numbers divisible by 3 = ⌊12/3⌋ = 4
These are: 3, 6, 9, ..., 12

Step 2 - Count numbers divisible by 5:
Numbers divisible by 5 = ⌊12/5⌋ = 2
These are: 5, 10, 15, ..., 10

Step 3 - Count numbers divisible by BOTH 3 AND 5:
Numbers divisible by LCM(3,5) = 15
Count = ⌊12/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)
= 4 + 2 - 0
= 6

Visualization (Venn Diagram concept):
- Circle A: divisible by 3 (4 numbers)
- Circle B: divisible by 5 (2 numbers)
- Intersection: divisible by both (0 numbers)
- Union: 6 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 = 12 - 6 = 6

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: 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: 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+z)^6
- Desired term: the term y^6
- Exponents: x = 0, y = 6, z = 0

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

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

Step 3 - Calculate:
- Numerator: 6! = 720
- Denominator: 6! = 720
- Denominator value: 720

Final Calculation:
Coefficient = 720 / 720 = 1

Alternative interpretation: This equals the number of ways to arrange 6 items with:
0 of type x, 6 of type y, 0 of type z

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 = 3^6 = 729

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: Permutation with repetition. When some objects are identical, we divide by the factorial of the number of repetitions.

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

Given distribution: [3, 4, 4]

Result: 1814400 distinct necklaces.

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

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

Step 4 - Apply Multiplication Principle:
Total arrangements = 24 × 10 × 6
= 24 × 10 × 6
= 1440

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

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

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

Step 1 - Total arrangements if all were distinct:
15! = 1307674368000

Step 2 - Account for identical objects:
15! = 1307674368000 / 3! = 6 / 4! = 24 / 2! = 2 / 4! = 24 / 2! = 2

Final Calculation:
= 94594500

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 15! = 1307674368000.

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

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

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

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

Step 4 - Apply Inclusion-Exclusion:
Total = (divisible by 2) + (divisible by 3) - (divisible by both)
= 6 + 4 - 2
= 8

Visualization (Venn Diagram concept):
- Circle A: divisible by 2 (6 numbers)
- Circle B: divisible by 3 (4 numbers)
- Intersection: divisible by both (2 numbers)
- Union: 8 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 = 12 - 8 = 4

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 'BALL':
- 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 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: Handshake problem with selective participation.

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

Step 1 - Total possible handshakes without restrictions:
Total possible = C(8, 2) = 8×7/2 = 28

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 = 4 × 4 = 16

Step 3 - Subtract restricted handshakes:
Actual handshakes = Total possible - Forbidden handshakes
= 28 - 16
= 12

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

Verification: Both methods give the same result.

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

Calculation:
Total ways = 6 × 7 × 3 = 126

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 7 second choices (6×7=42), and each of these can be combined with any of the 3 third choices.

Step-by-Step Solution:

Concept: Combination with mandatory inclusion constraint.

Given:
- Total people: 12
- Committee size: 5
- Must include: 3 specific people

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

Analysis:
We need to select 5 people total, with 3 already fixed.
- Fixed positions: 3 (these specific people are already in)
- Remaining positions to fill: 5 - 3 = 2
- People available for remaining positions: 12 - 3 = 9

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 2 people from remaining 9 people:
C(9,2) = 36

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

Alternative Approach - Verification:
Think of it as: "We've used 3 spots, now choose 2 more from 9 remaining"

Related Problem Types:

1. Must EXCLUDE specific people:
Select all 5 from remaining 12 - (people to exclude)

2. At least one specific person:
Total ways - Ways without that person
= C(12,5) - C(12-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: 36 ways

Step-by-Step Solution:

Concept: Counting even/odd numbers with distinct digits.

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

Case Analysis for even numbers:

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

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

Total = 3024 + 10752 = 13776

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