Permutation & Combination - Beginner Level: quick solving techniques BEGINNER

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 = 7 (total items)
- r = 2 (items to select)

Calculation:
C(7,2) = 7! / [2! × 5!]
= 7! / [2 × 120]
= 5040 / [2 × 120]
= 21

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

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

Verification: The answer must be less than 7! 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: 5
- Vowels: 3
- 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 3 gaps from 6 available gaps: C(6,3) = 20
Arrange 3 vowels in chosen gaps: 3! = 6

Step 4 - Apply Multiplication Principle:
Total arrangements = 120 × 20 × 6
= 120 × 20 × 6
= 14400

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

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

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

Step 4 - Apply Multiplication Principle:
Total arrangements = 120 × 20 × 6
= 120 × 20 × 6
= 14400

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

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

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)^7
- Desired term: the term x^5 * y^2
- Exponents: x = 5, y = 2

Step 1 - Verify exponent sum:
5 + 2 = 7 = 7 ✓

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

Step 3 - Calculate:
- Numerator: 7! = 5040
- Denominator: 5! × 2! = 120 × 2
- Denominator value: 240

Final Calculation:
Coefficient = 5040 / 240 = 21

Alternative interpretation: This equals the number of ways to arrange 7 items with:
5 of type x, 2 of type y

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 = 2^7 = 128

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

Calculation:
Total ways = 4 × 4 × 3 = 48

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

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 3 digits: choose and arrange from remaining 9 digits
Total = 9 × P(9, 3) = 9 × 504 = 4536

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

Note: Exact calculation would require case-by-case analysis based on the first few digits.

Step-by-Step Solution:

Concept: For necklaces with identical beads, we use Burnside's Lemma.

Given distribution: [4, 3, 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: 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: Distribution of distinct objects to distinct boxes - each object independently chooses a box.

Given:
- Distinct items: 7
- Distinct boxes: 3
- Empty boxes: Allowed

Strategy: Each item makes an independent choice of which box to go into.

Analysis:
- Item 1 can go into any of 3 boxes: 3 choices
- Item 2 can go into any of 3 boxes: 3 choices
- Item 3 can go into any of 3 boxes: 3 choices
- ...and so on for all 7 items

Formula: (number of boxes)^(number of items) = 3^7

Calculation:
Total ways = 3^7 = 2187

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: 3! × S(7,3)
where S(n,k) is the Stirling number of second kind

2. Identical items, distinct boxes:
This becomes a "stars and bars" problem: C(7+3-1, 3-1)

3. Distinct items, identical boxes (Partition):
Use Stirling numbers: Σ S(7,k) for k=1 to 3

Verification:
- With 1 box: answer should be 1 (all items in one box)
- With 7 boxes, one item: answer should be 7
- Our answer 2187 is reasonable: each item independently chooses from 3 options

Common Error: Don't use factorial or combination formulas here - items are making independent simultaneous choices.

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 x^6
- Exponents: x = 6, y = 0, z = 0

Step 1 - Verify exponent sum:
6 + 0 + 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:
6 of type x, 0 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: 12
- 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 12 points: C(12,3)
C(12,3) = 12! / [3! × 9!] = 220

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
= 220 - 1
= 219

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

Verification: Answer should be less than C(12,3) = 220 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 'BOOK':
- 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 (Sum Rule):

Concept: 'At least' problems require finding the sum of ways for all valid, mutually exclusive cases.

Given:
- Men available: 10
- Women available: 6
- 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(10,4) × C(6,2) = 210 × 15 = 3150
(5 Men, 1 Women): C(10,5) × C(6,1) = 252 × 6 = 1512
(6 Men, 0 Women): C(10,6) × C(6,0) = 210 × 1 = 210

Final Calculation (Sum Rule):
Total ways = (Ways with 4 men) + (Ways with 5 men) + ...
= 3150 + 1512 + 210
= 4872

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

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: 9
- Women available: 8
- 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(9,4) × C(8,2) = 126 × 28 = 3528
(5 Men, 1 Women): C(9,5) × C(8,1) = 126 × 8 = 1008
(6 Men, 0 Women): C(9,6) × C(8,0) = 84 × 1 = 84

Final Calculation (Sum Rule):
Total ways = (Ways with 4 men) + (Ways with 5 men) + ...
= 3528 + 1008 + 84
= 4620

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

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: 10
- Women available: 7
- Committee size: 8
- Constraint: At least 5 men

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

Valid Cases (Men, Women) and Calculation:

(5 Men, 3 Women): C(10,5) × C(7,3) = 252 × 35 = 8820
(6 Men, 2 Women): C(10,6) × C(7,2) = 210 × 21 = 4410
(7 Men, 1 Women): C(10,7) × C(7,1) = 120 × 7 = 840
(8 Men, 0 Women): C(10,8) × C(7,0) = 45 × 1 = 45

Final Calculation (Sum Rule):
Total ways = (Ways with 5 men) + (Ways with 6 men) + ...
= 8820 + 4410 + 840 + 45
= 14115

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

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

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

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

Step 3 - Apply multiplication principle:
Total = C(5,2) × D(3)
= 10 × 2
= 20

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: Handshake problem with subset participation.

Given:
- Total people: 13
- Non-participants: 2
- Participants: 11

Step 1 - Identify participants:
Only 11 people actually shake hands.

Step 2 - Calculate handshakes among participants:
Handshakes = C(11, 2) = 11×10/2

Calculation:
= 11×10/2 = 55
= 55

Key Point: Non-participants don't contribute to any handshake.

Step-by-Step Solution:

Concept: Handshake problem with subset participation.

Given:
- Total people: 12
- Non-participants: 3
- Participants: 9

Step 1 - Identify participants:
Only 9 people actually shake hands.

Step 2 - Calculate handshakes among participants:
Handshakes = C(9, 2) = 9×8/2

Calculation:
= 9×8/2 = 36
= 36

Key Point: Non-participants don't contribute to any handshake.

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 ✓