Permutation & Combination - Expert Level: exam-oriented practice EXPERT

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: Linear permutation of n distinct objects = n! (n factorial)

Analysis:
- We need to arrange 4 distinct objects in a line
- For the first position: 4 choices
- For the second position: 3 choices (one already placed)
- For the third position: 2 choices
- And so on...

Formula Application:
Number of arrangements = 4! = 4 × 3 × 2 × ... × 2 × 1

Calculation:
4! = 24

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: 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: 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: 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: 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: Permutation with restriction - specific position must have certain type of letter.

Strategy: Fix the restricted position first, then arrange the remaining letters.

Analysis of 'EQUATION':
- Total letters: 8
- Vowels: E, U, A, I, O = 5 vowels
- First position must be a vowel

Step 1 - Fix First Position:
Choose a vowel for first position: 5 choices

Step 2 - Arrange Remaining:
Remaining 7 letters can be arranged in 7! ways
7! = 5040

Calculation:
Total arrangements = 5 × 5040 = 10080

Key Strategy: When dealing with restrictions:
1. Handle the restriction first (fix the constrained position)
2. Arrange the remaining elements freely
3. Multiply the results

Verification: This should be less than the total arrangements (8! = 40320) since we've added a constraint.

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

Step 4 - Apply Multiplication Principle:
Total arrangements = 120 × 15 × 2
= 120 × 15 × 2
= 3600

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

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

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

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

Continue for all groups:
C(10,9) = 10
C(1,1) = 1 (last group)

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

Simplified formula:
= 10! / (9! × 1!)
= 3628800 / (362880 × 1)
= 10

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

Step 3 - Apply Complementary Counting:
Valid triangles = Total selections - Invalid selections
= 56 - 4
= 52

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

Step 3 - Apply Multiplication Principle:
Total ways = C(8,2) × C(4,2)
= 28 × 6
= 168

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: Linear permutation of n distinct objects = n! (n factorial)

Analysis:
- We need to arrange 4 distinct objects in a line
- For the first position: 4 choices
- For the second position: 3 choices (one already placed)
- For the third position: 2 choices
- And so on...

Formula Application:
Number of arrangements = 4! = 4 × 3 × 2 × ... × 2 × 1

Calculation:
4! = 24

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

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 5:
Numbers divisible by 5 = ⌊11/5⌋ = 2
These are: 5, 10, 15, ..., 10

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

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

Visualization (Venn Diagram concept):
- Circle A: divisible by 2 (5 numbers)
- Circle B: divisible by 5 (2 numbers)
- Intersection: divisible by both (1 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 = 11 - 6 = 5

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

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

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(6,2) × D(4)
= 15 × 9
= 135

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=6:
- D(6,0) = 265
- D(6,1) = 264
- D(6,2) = 135
- ... and so on.

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