Permutation & Combination - Beginner Level: pattern recognition BEGINNER

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$): 7
- Step 1: Normal circular arrangements (rotations same) = $(n-1)!$ = 720
- Step 2: Account for reflection (flips) by dividing by 2.

Calculation:
Arrangements = $\frac{(7-1)!}2$
= $\frac{720}2$
= 360

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

Given:
- Total people: 10
- Group sizes: 5, 4, 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 10: C(10, 5) = 252

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

Continue for all groups:
C(10,5) = 252
C(5,4) = 5
C(1,1) = 1 (last group)

Step 3 - Multiply:
Total ways = 252 × 5 × 1 (last group)
= 1260

Simplified formula:
= 10! / (5! × 4! × 1!)
= 3628800 / (120 × 24 × 1)
= 1260

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 (Burnside's Lemma):

Concept: Circular permutations with identical objects and reflection symmetry require Burnside's Lemma.

Given: 4 red beads, 4 blue beads, total = 8 beads.

Formula for binary necklaces (2 colors, equal counts):
$$\text{Necklaces} = \frac{1}{2n} \sum_{d|n} \phi(d) \cdot \frac{(n/d)!}{(a/d)!(b/d)!} + \text{reflection term}$$

For our case:
- n = 8, a = 4, b = 4
- Term 1 (rotations): $\frac{1}{2n} \cdot \frac{n!}{a!b!} = \frac{1}{16} \cdot \frac{40320}{2424} = 4$
- Term 2 (reflections): 3

Total = 4 + 3 = 7

Alternative known result: For 2 red, 2 blue beads: (2-1)!/2 * something = 7

Key Principle: Burnside's Lemma averages the number of arrangements fixed by each symmetry operation (rotation and reflection).

Step-by-Step Solution:

Concept: Handshake problem with subset participation.

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

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

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

Calculation:
= 12×11/2 = 66
= 66

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

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: 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: 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 (Sum Rule):

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

Given:
- Men available: 10
- Women available: 8
- Committee size: 8
- 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 (8).

Valid Cases (Men, Women) and Calculation:

(4 Men, 4 Women): C(10,4) × C(8,4) = 210 × 70 = 14700
(5 Men, 3 Women): C(10,5) × C(8,3) = 252 × 56 = 14112
(6 Men, 2 Women): C(10,6) × C(8,2) = 210 × 28 = 5880
(7 Men, 1 Women): C(10,7) × C(8,1) = 120 × 8 = 960
(8 Men, 0 Women): C(10,8) × C(8,0) = 45 × 1 = 45

Final Calculation (Sum Rule):
Total ways = (Ways with 4 men) + (Ways with 5 men) + ...
= 14700 + 14112 + 5880 + 960 + 45
= 35697

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:

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: Rank of a word in dictionary order - counting how many words come before it alphabetically.

Given word: TIGER

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: E G I R T

Step-by-Step Calculation:

Position 1 (current letter: T):
Available letters: E G I R T
If we place 'E' here: 24 arrangements possible
If we place 'G' here: 24 arrangements possible
If we place 'I' here: 24 arrangements possible
If we place 'R' here: 24 arrangements possible
Subtotal arrangements before 'T': 96
Position 2 (current letter: I):
Available letters: E G I R
If we place 'E' here: 6 arrangements possible
If we place 'G' here: 6 arrangements possible
Subtotal arrangements before 'I': 12
Position 3 (current letter: G):
Available letters: E G R
If we place 'E' here: 2 arrangements possible
Subtotal arrangements before 'G': 2
Position 4 (current letter: E):
Available letters: E R
Position 5 (current letter: R):
Available letters: R

Final Rank: 111

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

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

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

Given distribution: [4, 3, 2]

Result: 20160 distinct necklaces.

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

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

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

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

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

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

Visualization (Venn Diagram concept):
- Circle A: divisible by 3 (3 numbers)
- Circle B: divisible by 2 (5 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 = 10 - 7 = 3

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

Given distribution: [2, 4]

Result: 60 distinct necklaces.

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