What Are Permutations and Combinations?
Welcome back, my student! In the previous lesson, you learned the two basic counting principles — the Addition Principle and the Multiplication Principle. Now, we will use those principles to solve a very common type of problem: selecting and arranging objects.
Here is the key idea. Sometimes, when we select objects, the order matters. For example, if you select Abebe as president and Belete as vice president, that is DIFFERENT from Belete as president and Abebe as vice president. Other times, the order does not matter. If you select Abebe and Belete as a committee of two members, the committee {Abebe, Belete} is the SAME as {Belete, Abebe}.
These two ideas — permutation and combination — are among the most frequently tested topics in exams. Let us study each one carefully.
Part 1: Permutations
Definition of Permutation
A permutation of r objects from a set of n objects is an ordered arrangement of r of those n objects. We call this an r-permutation.
Example 1: Understanding Permutations
Consider the set S = {A, B, C, D}.
- BDCA, DCBA, ACDB are permutations of all 4 letters (4-permutations)
- BAD, ACB, DBC are permutations of 3 letters (3-permutations)
- AD, BC, CA are permutations of 2 letters (2-permutations)
Do you see? Each one is an ordered list taken from the set.
Example 2: Listing All 3-Permutations
Let S = {A, B, C, D, E} (n = 5 objects). Let us list all 3-permutations:
There are exactly 60 of them. But listing all permutations is not practical when n is large. We need a formula!
Quick Question: How many 2-permutations does the set {a, b, c} have? List them.
Answer: 6
The 2-permutations are: ab, ac, ba, bc, ca, cb. That is 6 in total. Using the Multiplication Principle: 3 choices for the first position × 2 choices for the second = 6.
The Permutation Formula
How did we get 60 for the 3-permutations of 5 objects? Let me show you the logic using the Multiplication Principle:
- First position: 5 choices (any of A, B, C, D, E)
- Second position: 4 choices (remaining 4, since no repetition)
- Third position: 3 choices (remaining 3)
This logic works for any n and r! So we get the general formula:
Using factorial notation, we can write this more compactly:
- No repetition is allowed (each object is used at most once)
- Order matters — ABC ≠ ACB ≠ BAC
- When \(r = n\), we get \(P(n,n) = n!\) — this is the number of ways to arrange ALL n objects
- \(P(n, 0) = 1\) (there is exactly one way to select and arrange zero objects: do nothing!)
- \(P(n, 1) = n\) (selecting and arranging just one object gives n choices)
Worked Examples on Permutations
Example 3: In how many ways can we arrange three students from a group of five students to stand in a line for a picture? In how many ways can we arrange all five?
Solution:
- Arranging 3 from 5: \(P(5, 3) = 5 \times 4 \times 3 = 60\) ways
- Arranging all 5: \(P(5, 5) = 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\) ways
Example 4: How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize winner from 100 people?
Solution: Order matters (first prize ≠ second prize). This is \(P(100, 3)\):
Example 5: Eight runners are in a race. Gold, silver, and bronze medals are awarded. How many different ways to award these medals?
Solution: \(P(8, 3) = 8 \times 7 \times 6 = 336\) ways.
Example 6: How many four-letter “words” can be formed using each of the letters a, b, c, d, e at most once?
Solution: We need 4-permutations of 5 letters:
If we use all 5 letters: \(P(5, 5) = 5! = 120\) words as well.
Example 7: Find n if \(P(n, 2) = 72\).
Solution:
So \(n = 9\) or \(n = -8\). Since n must be positive, n = 9.
Exam Question 1: How many different orders can five runners finish a race if no ties are allowed?
Answer: 120
Explanation: We need to arrange all 5 runners in order. This is \(P(5,5) = 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\). Each different ordering of the 5 runners is a different permutation.
Exam Question 2: There are 12 horses in a race. How many possibilities are there for the win, place, and show (first, second, third) positions?
Answer: 1,320
Explanation: We need to select and order 3 horses from 12. This is \(P(12, 3) = 12 \times 11 \times 10 = 1,320\). The first horse has 12 possibilities, the second 11 (remaining), the third 10 (remaining).
Exam Question 3: How many permutations of {a, b, c, d, e, f, g} end with the letter a?
Answer: 720
Explanation: We fix ‘a’ in the last position. The remaining 6 positions must be filled with the remaining 6 letters {b, c, d, e, f, g} in any order. The number of ways to arrange 6 letters is \(P(6, 6) = 6! = 720\).
Strategy: When a position is fixed (restricted), fill that position first, then arrange the rest.
Circular Permutations
Now, here is an interesting twist! What if the objects are arranged in a circle instead of a line?
Think about it: if 4 people sit around a round table, the arrangements ABCD, BCDA, CDAB, and DABC are actually the SAME arrangement — each person has the same neighbors! We just rotated the circle. So circular arrangements are different from linear arrangements.
In a line, n objects give \(n!\) arrangements. But in a circle, every arrangement has n equivalent rotations. So we divide by n: \(\frac{n!}{n} = (n-1)!\).
Note: Clockwise and anticlockwise arrangements are considered DIFFERENT unless stated otherwise.
Example 8: Find the number of 3-permutations of the letters p, q, r, s, t in a circle.
Solution: Using the formula with n = 5, r = 3:
Example 9: In how many ways can 5 men and 5 women sit around a table if: (i) there is no restriction? (ii) no two women sit together?
Solution:
(i) No restriction: This is a circular permutation of 10 people:
(ii) No two women together: This is a classic problem! The strategy is:
- First, seat the 5 men around the table: \((5-1)! = 4! = 24\) ways
- Once the men are seated, there are exactly 5 “gaps” between consecutive men
- Place the 5 women in these 5 gaps: \(5! = 120\) ways
Exam Question 4: In how many ways can six men and six women be seated at a round table if the men and women are to sit in alternate seats?
Answer: 86,400
Explanation: Alternate seats means men and women alternate. There are two possible patterns: M-W-M-W-… or W-M-W-M-…
Case 1: Men first, then women
- Seat 6 men in alternate seats (circular): \((6-1)! = 5! = 120\) ways
- Seat 6 women in the remaining 6 seats: \(6! = 720\) ways
- Case 1 total: \(120 \times 720 = 86,400\)
Case 2: Women first, then men
- Seat 6 women: \((6-1)! = 120\) ways
- Seat 6 men: \(6! = 720\) ways
- Case 2 total: \(120 \times 720 = 86,400\)
Grand total (Addition Principle): \(86,400 + 86,400 = 172,800\)
BUT WAIT! In a circular arrangement, the pattern M-W-M-W-… is actually the SAME as W-M-W-M-… — it is just a rotation by one seat! So Case 1 and Case 2 are the same. The correct answer is 86,400.
This is a common trap in circular permutation problems! Always check if rotating the pattern gives the same arrangement.
More Challenging Permutation Examples
Example 10: In how many ways can the letters of the English alphabet be arranged so that no two of the vowels a, e, i, o, u occur consecutively?
Solution: This is a challenging problem! We use a two-step approach:
Step 1: Arrange the 21 consonants among themselves: \(21!\) ways.
Step 2: The 21 consonants create 22 “gaps” (spaces before, between, and after the consonants):
We need to place 5 vowels in these 22 gaps (no two consecutive means each vowel goes in a different gap):
Total (Multiplication Principle):
Example 11: A man, a woman, a boy, a girl, a dog, and a cat are walking down a road one after the other. (a) In how many ways? (b) Dog comes first? (c) Dog immediately follows the boy? (d) Dog (and only the dog) is between the man and the boy?
Solution:
(a) Six creatures in a line: \(6! = 720\) ways.
(b) Dog fixed first, remaining 5 can be arranged: \(5! = 120\) ways.
(c) Treat dog-boy as a single object. Now we have 5 objects: {man, woman, girl, cat, dog-boy}. Arrange these: \(5! = 120\) ways.
(d) Two cases: man-dog-boy OR boy-dog-man. Each case: treat the triple as one object, giving 4 objects to arrange: \(4! = 48\) each. By Addition Principle: \(48 + 48 = 96\) ways.
Exam Question 5: In how many ways can 15 people be seated at a round table if person B refuses to sit next to person A?
Answer: 14! − 2 × 13! = 13!(14 − 2) = 12 × 13! = 12 × 6,227,020,800 = 74,724,249,600
Explanation: Use the subtraction method!
- Total circular arrangements of 15 people: \((15-1)! = 14!\)
- Arrangements where A and B sit TOGETHER: Treat A and B as one object. We have 14 objects to arrange circularly: \((14-1)! = 13!\). But A-B can be ordered as AB or BA (2 ways). So: \(2 \times 13!\)
- Arrangements where B does NOT sit next to A: \(14! – 2 \times 13!\)
Simplifying: \(14! – 2 \times 13! = 13! \times 14 – 2 \times 13! = 13!(14-2) = 12 \times 13!\)
Part 2: Combinations
Definition of Combination
Now let us look at the other side. A combination of r elements from a set of n elements is an unordered selection of r elements from the set. We call this an r-combination.
Example 12: Understanding Combinations
Let S = {a, b, c, d, e} (n = 5). The 3-combinations are:
There are only 10 of them. Compare this with the 60 permutations we had earlier for the same set! Can you see why combinations give a smaller number? Because many permutations correspond to the same combination.
Example 13: The 2-combinations of {a, b, c, d} are:
Compare: The 2-permutations were ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc — that is 12. Each combination gives 2! = 2 permutations. So \(12 / 2 = 6\). Do you see the relationship?
The Combination Formula
Here is the beautiful relationship between permutations and combinations:
Why? Because for each r-combination, there are \(r!\) ways to order (permute) those r elements. So:
- No repetition is allowed
- Order does NOT matter — {a,b,c} = {c,b,a}
- \(C(n, 0) = 1\) (there is exactly one way to select nothing: select nothing)
- \(C(n, 1) = n\) (selecting one element from n)
- \(C(n, n) = 1\) (selecting all n elements: only one way)
Symmetry Property
Example: \(C(10, 3) = C(10, 7)\). Why? Because selecting 3 people to be ON a committee is the same as selecting 7 people to be OFF the committee!
Worked Examples on Combinations
Example 14: How many poker hands of 5 cards can be dealt from a standard deck of 52 cards?
Solution: Order does not matter in a poker hand. This is a 5-combination of 52 cards:
Example 15: A farmer buys 3 cows from 6 available, 2 pigs from 5 available, and 4 hens from 8 available. How many choices does the farmer have?
Solution: Each selection is a combination (order does not matter within each type). By the Multiplication Principle:
Exam Question 6: A class has 10 students with 6 men and 4 women. Find: (a) Number of ways to select a 4-member committee. (b) Number of ways to select a 4-member committee with exactly 2 men and 2 women.
Answer: (a) 210 ways (b) 90 ways
Explanation:
(a) Selecting any 4 from 10 (order does not matter): \(C(10, 4) = \frac{10!}{4! \times 6!} = 210\)
(b) Select 2 men from 6 AND 2 women from 4 (Multiplication Principle):
Exam Question 7: From a group of 9 men and 3 women, a teacher selects a committee of 4. Find the number of ways if: (a) no restrictions, (b) exactly one woman, (c) at least one woman.
Answers: (a) 495 (b) 324 (c) 405
Explanation: Total people = 12.
(a) No restrictions: \(C(12, 4) = \frac{12!}{4! \times 8!} = 495\)
(b) Exactly one woman: Choose 1 woman from 3 AND 3 men from 9:
(c) At least one woman: Use subtraction method: ALL committees minus committees with NO women (all men):
Note: “At least one” problems are perfect for the subtraction method!
Part 3: Comparing Permutations and Combinations
My student, one of the most important skills is knowing WHEN to use permutation and WHEN to use combination. Let me help you with this:
| Feature | Permutation | Combination |
|---|---|---|
| Order | Matters | Does NOT matter |
| Formula | \(P(n,r) = \frac{n!}{(n-r)!}\) | \(C(n,r) = \frac{n!}{r!(n-r)!}\) |
| Relationship | \(P(n,r) = r! \times C(n,r)\) | \(C(n,r) = \frac{P(n,r)}{r!}\) |
| Keywords | Arrange, order, rank, schedule, award | Select, choose, pick, group, committee |
| Example | President and Vice President | Committee of 2 members |
| ABC vs ACB | DIFFERENT | SAME |
Part 4: Solutions to Module Exercises
Exercise 1.2, Q1: List all permutations of {a, b, c}.
Answer: abc, acb, bac, bca, cab, cba — that is \(3! = 6\) permutations.
Exercise 1.2, Q2: How many different permutations of {a, b, c, d, e, f, g}?
Answer: 5,040
All 7 letters are arranged: \(P(7,7) = 7! = 5,040\).
Exercise 1.2, Q5: Find P(6,3) and P(6,5).
Answers:
\(P(6,3) = 6 \times 5 \times 4 = 120\)
\(P(6,5) = 6 \times 5 \times 4 \times 3 \times 2 = 720\) (or \(P(6,5) = \frac{6!}{1!} = 720\))
Exercise 1.2, Q6: Find C(5,1) and C(5,3).
Answers:
\(C(5,1) = \frac{5!}{1! \times 4!} = 5\)
\(C(5,3) = \frac{5!}{3! \times 2!} = \frac{120}{12} = 10\)
Note: By symmetry, \(C(5,3) = C(5,2) = 10\).
Exercise 1.2, Q7: Find the number of 5-permutations of a set with 9 elements.
Answer: 15,120
\(P(9, 5) = \frac{9!}{(9-5)!} = \frac{9!}{4!} = 9 \times 8 \times 7 \times 6 \times 5 = 15,120\)
Exercise 1.2, Q9: Find n if: (a) P(n,2) = 110, (b) P(n,n) = 5040, (d) C(n,2) = 45, (e) C(n,3) = P(n,2), (f) C(n,5) = C(n,2).
Answers:
(a) \(n(n-1) = 110 \Rightarrow n^2 – n – 110 = 0 \Rightarrow (n-11)(n+10) = 0 \Rightarrow n = 11\)
(b) \(n! = 5040\). We know \(7! = 5040\), so \(n = 7\).
(d) \(\frac{n(n-1)}{2} = 45 \Rightarrow n(n-1) = 90 \Rightarrow n^2 – n – 90 = 0 \Rightarrow (n-10)(n+9) = 0 \Rightarrow n = 10\)
(e) \(\frac{n!}{3!(n-3)!} = \frac{n!}{(n-2)!}\). Simplifying: \(\frac{1}{6(n-3)!} = \frac{1}{(n-2)!}\). So \(6(n-3)! = (n-2)! = (n-2)(n-3)!\). Thus \(6 = n-2\), giving \(n = 8\).
(f) \(C(n,5) = C(n,2)\). By symmetry property, \(C(n,r) = C(n,n-r)\), so \(C(n,5) = C(n,n-5)\). Therefore \(n-5 = 2\), giving \(n = 7\). (Check: \(C(7,5) = C(7,2) = 21\). Correct!)
Exercise 1.2, Q10: How many integers greater than 5400 have distinct digits and the digits 2 and 7 do not occur?
Answer: 168
Explanation: Available digits (excluding 2 and 7): {0, 1, 3, 4, 5, 6, 8, 9} — that is 8 digits. We need 4-digit numbers > 5400 with distinct digits.
We have two cases based on the first digit:
Case 1: First digit is 5 (number is 5xxx, which is 5000–5999)
For the number to be > 5400, the second digit must be ≥ 4 (from our available digits: 4, 5, 6, 8, 9). But 5 is already used as first digit, so second digit: 4, 6, 8, or 9 — that is 4 choices.
- First digit: 1 choice (5)
- Second digit: 4 choices (4, 6, 8, 9)
- Third digit: 6 choices (remaining 6 digits)
- Fourth digit: 5 choices (remaining 5 digits)
Case 1: \(1 \times 4 \times 6 \times 5 = 120\)
Case 2: First digit is 6, 8, or 9 (number is automatically > 5400)
- First digit: 3 choices (6, 8, 9)
- Second digit: 7 choices (remaining 7 digits)
- Third digit: 6 choices
- Fourth digit: 5 choices
Case 2: \(3 \times 7 \times 6 \times 5 = 630\)
Wait — let me recheck Case 2. After picking first digit from {6,8,9}, the remaining available digits are 7 (from the 8 total minus the one used). So second: 7, third: 6, fourth: 5. That gives \(3 \times 7 \times 6 \times 5 = 630\).
But this seems too large. Let me re-examine. Total 4-digit numbers with distinct digits from 8 available digits: \(P(8,4) = 8 \times 7 \times 6 \times 5 = 1,680\). Of these, we need those > 5400. Subtracting those ≤ 5400 should give us the answer.
Numbers ≤ 5400 with first digit from {0,1,3,4,5,6,8,9}: First digit must be 0,1,3,4, or 5. But 0 cannot be first digit of a 4-digit number. So first digit: {1,3,4,5} — 4 choices.
If first digit is 1, 3, or 4: the number is automatically < 5400. Count: \(3 \times 7 \times 6 \times 5 = 630\).
If first digit is 5: second digit must be 0, 1, 3 (to keep number ≤ 5400). That is 3 choices. Count: \(1 \times 3 \times 6 \times 5 = 90\).
Numbers ≤ 5400: \(630 + 90 = 720\). Numbers > 5400: \(1,680 – 720 = 960\).
I made errors in my first attempt. The correct answer is 960.
Exercise 1.2, Q11: In how many ways can four men and eight women be seated at a round table if there are two women between consecutive men?
Answer: 604,800
Explanation: With 4 men and 8 women, and exactly 2 women between consecutive men, the pattern around the table is fixed: M-W-W-M-W-W-M-W-W-M-W-W. The 4 men partition the 8 women into 4 groups of 2.
Step 1: Seat the 4 men circularly: \((4-1)! = 3! = 6\) ways.
Step 2: After placing the men, the 8 women must fill the 8 specific positions (2 between each pair of men). The 8 women can be arranged in these positions: \(8! = 40,320\) ways.
Step 3: Within each pair of 2 women between consecutive men, the order matters (left vs right position). Wait — actually, the 8 positions are specific (there are exactly 8 slots), so arranging 8 women in 8 slots is just \(8!\). The two positions between any two men are distinguishable (one is clockwise from man 1, one is counterclockwise).
Corrected Answer: 241,920
Exercise 1.2, Q14: Consider all 5-letter “words” from letters a through h. (a) How many total? (b) No repeated letters? (c) Start with “aha”? (d) Start with “aha” OR end with “bah”?
Answers:
Available letters: {a, b, c, d, e, f, g, h} — 8 letters.
(a) Total words: Repetition allowed. \(8^5 = 32,768\)
(b) No repeated letters: \(P(8, 5) = 8 \times 7 \times 6 \times 5 \times 4 = 6,720\)
(c) Start with “aha”: First three letters are fixed: a-h-a. Remaining 2 positions: \(8 \times 8 = 64\) (repetition allowed since only first case specifies)
(d) Start with “aha” OR end with “bah”:
- Start with “aha”: 64 (from part c)
- End with “bah”: Last three letters fixed. First 2 positions: \(8 \times 8 = 64\)
- Both (start with “aha” AND end with “bah”): Only possible if the word is “ahabah” (5 letters). But “ahabah” starts with “aha” (positions 1-3) and ends with “bah” (positions 3-5). Position 3 must be ‘a’ (from “aha”) AND ‘b’ (from “bah”) — contradiction! So 0 ways for both.
By Addition Principle (disjoint): \(64 + 64 = 128\)
Exercise 1.2, Q15: Let S = {1,2,3,4,5,6}. (a) How many subsets total? (b) How many subsets contain at least one odd number? (c) How many subsets contain exactly one even number?
Answers:
(a) A set with 6 elements has \(2^6 = 64\) subsets.
(b) Use subtraction: ALL subsets minus subsets with NO odd numbers. Odd numbers in S: {1,3,5}. Even numbers: {2,4,6}. Subsets with no odd numbers = subsets of {2,4,6} = \(2^3 = 8\). Answer: \(64 – 8 = 56\).
(c) Choose exactly 1 even number from {2,4,6}: \(C(3,1) = 3\) ways. Then choose any subset of the odd numbers {1,3,5}: \(2^3 = 8\) ways. By Multiplication Principle: \(3 \times 8 = 24\).
Quick Revision — Permutations and Combinations
1. Permutation (Order Matters)
Example: Awarding gold, silver, bronze to 8 runners: \(P(8,3) = 336\)
2. Combination (Order Does NOT Matter)
Example: Choosing 5 cards from 52: \(C(52,5) = 2,598,960\)
3. Key Relationship
4. Circular Permutation
5. Decision Flowchart
6. Common Exam Patterns
- “At least one” → Subtraction: Total − “none”
- Fixed position → Fill it first: Reduce the problem
- “Exactly k from group A” → Multiplication: C(group A, k) × C(group B, r−k)
- Circular + restriction → Fix one person, then arrange
- Find n if P(n,r) or C(n,r) = given value → Set up equation, solve
Mini Revision Quiz
Q1: Is “selecting a president and a secretary from 10 students” a permutation or combination?
Answer: Permutation
Because president and secretary are different positions. Swapping them gives a different outcome. So order matters: \(P(10, 2) = 90\).
Q2: Is “selecting 2 students to clean the classroom” a permutation or combination?
Answer: Combination
Both students do the same job. {Abebe, Belete} = {Belete, Abebe}. Order does not matter: \(C(10, 2) = 45\).
Q3: Evaluate: (a) P(7,3) (b) C(7,3) (c) C(7,4)
Answers:
(a) \(P(7,3) = 7 \times 6 \times 5 = 210\)
(b) \(C(7,3) = \frac{210}{3!} = \frac{210}{6} = 35\)
(c) \(C(7,4) = C(7,3) = 35\) (by symmetry, since 4 = 7−3)
Q4: In how many ways can 7 people sit around a circular table?
Answer: 720
\((7-1)! = 6! = 720\).
Q5: True or False: \(C(n, r) \leq P(n, r)\) for all valid n and r.
Answer: TRUE
Since \(P(n,r) = r! \times C(n,r)\) and \(r! \geq 1\) for all \(r \geq 1\), we always have \(P(n,r) \geq C(n,r)\). When \(r = 0\) or \(r = 1\), they are equal. For \(r \geq 2\), permutation is strictly greater.
Challenge Exam Questions — Permutations and Combinations
These questions match the difficulty level of midterm and final exams. Try each one before checking the answer!
Part A: Multiple Choice Questions (MCQs)
Q1. In how many ways can 4 different books be arranged on a shelf?
A) 16
B) 24
C) 256
D) 4
Answer: B) 24
Explanation: Arranging all 4 books means order matters. \(P(4,4) = 4! = 4 \times 3 \times 2 \times 1 = 24\).
Q2. How many 3-member committees can be formed from 8 people?
A) 336
B) 56
C) 24
D) 512
Answer: B) 56
Explanation: A committee has no order (no president/secretary). This is a combination: \(C(8,3) = \frac{8!}{3! \times 5!} = \frac{8 \times 7 \times 6}{6} = 56\). Option A (336) is \(P(8,3)\), which would be wrong because order does not matter for a committee.
Q3. The value of \(C(10, 2)\) equals:
A) 90
B) 45
C) 20
D) 100
Answer: B) 45
Explanation: \(C(10, 2) = \frac{10 \times 9}{2 \times 1} = 45\). Alternatively, \(C(10, 2) = C(10, 8)\) by symmetry.
Q4. In how many ways can 5 people be seated around a circular table?
A) 120
B) 60
C) 24
D) 20
Answer: A) 120
Explanation: Circular permutation: \((5-1)! = 4! = 24\). Wait — \(4! = 24\), not 120. So the correct answer is C) 24. Option A (120) is \(5!\), which is for a LINEAR arrangement. Common exam trap: don’t forget to subtract 1 for circular!
Q5. If \(P(n, 4) = 12 \times P(n, 2)\), then n equals:
A) 6
B) 8
C) 10
D) 12
Answer: A) 6
Explanation: \(P(n,4) = n(n-1)(n-2)(n-3)\) and \(P(n,2) = n(n-1)\). So:
Dividing both sides by \(n(n-1)\) (valid since \(n \geq 4\)):
So \(n = 6\) (positive solution).
Q6. A class has 9 men and 3 women. How many 4-member committees have exactly one woman?
A) 252
B) 495
C) 324
D) 36
Answer: A) 252
Explanation: Choose 1 woman from 3 AND 3 men from 9: \(C(3,1) \times C(9,3) = 3 \times 84 = 252\). Option C (324) would be for exactly 2 women and 2 men, and option B (495) is the total without restrictions.
Part B: Short Answer and Difficult Problems
Q7. How many bit strings of length 10 contain exactly four 1s?
Answer: 210
Explanation: A bit string of length 10 with exactly four 1s means we choose 4 positions (out of 10) to place the 1s. The remaining 6 positions get 0s. Since the order of the positions does not create different types (we are just selecting which positions get 1s), this is a combination: \(C(10, 4) = \frac{10!}{4! \times 6!} = 210\).
Q8. How many subsets with an odd number of elements does a set with 10 elements have?
Answer: 512
Explanation: A set with 10 elements has \(2^{10} = 1024\) total subsets. Exactly half of them have an odd number of elements and half have an even number. So: \(1024 / 2 = 512\). This is because for every subset with k elements, its complement has 10−k elements (one is odd when the other is even), creating a perfect pairing.
Q9. A coin is flipped 8 times. How many outcomes contain: (a) exactly three heads? (b) at least three heads?
Answers: (a) 56 (b) 219
Explanation:
(a) Choose 3 positions (out of 8) for heads: \(C(8, 3) = 56\).
(b) “At least 3 heads” means 3, 4, 5, 6, 7, or 8 heads. Use subtraction: ALL outcomes minus those with 0, 1, or 2 heads:
Q10. How many subsets with more than 2 elements does a set with 100 elements have?
Answer: \(2^{100} – C(100,0) – C(100,1) – C(100,2) = 2^{100} – 1 – 100 – 4,950 = 2^{100} – 5,051\)
Explanation: Total subsets: \(2^{100}\). Subtract subsets with 0, 1, or 2 elements. This equals approximately \(1.27 \times 10^{30}\).
Q11. Find the number of permutations of the letters in the word QUEUE.
Answer: 60
Explanation: QUEUE has 5 letters with repetitions: U appears 2 times, and E, Q appear once each. The number of distinct permutations is:
Note: When letters repeat, we divide by the factorial of the count of each repeated letter. This is covered under “permutations with indistinguishable objects.”
Q12. Find the number of permutations of the letters in the word MISSISSIPPI.
Answer: 34,650
Explanation: MISSISSIPPI has 11 letters: M (1), I (4), S (4), P (2). The formula for permutations with indistinguishable objects:
Q13. Find the number of permutations of the letters in the word COMMITTEE.
Answer: 45,360
Explanation: COMMITTEE has 9 letters: C (1), O (1), M (1), I (1), T (2), E (2). Using the formula:
Wait, let me recount the letters: C-O-M-M-I-T-T-E-E. That is: M(2), T(2), E(2), and C,O,I each once. So:
Corrected Answer: 45,360
Q14. Find the number of positive integers greater than a million that can be formed with the digits 2, 3, 0, 3, 4, 2, 3.
Answer: 360
Explanation: We have 7 digits: 2 (appears 2 times), 3 (appears 3 times), 0 (1 time), 4 (1 time). Numbers greater than a million must be 7-digit numbers (all digits used).
Total 7-digit arrangements (with repetitions):
But some of these start with 0, making them 6-digit numbers (less than a million). Numbers starting with 0: fix 0 in first position, arrange remaining 6 digits (2 appears twice, 3 appears three times, 4 once):
Valid numbers: \(420 – 60 = 360\).
Q15. In how many ways can the letters of the English alphabet be arranged so that there are exactly ten letters between a and z?
Answer: \(2 \times P(24, 10) \times 15!\)
Explanation: We need exactly 10 letters between a and z. Think of a and z with 10 letters between them as a “block” of 12 characters. The 10 middle letters can be chosen and ordered from the remaining 24 letters (excluding a and z) in \(P(24, 10)\) ways. The block can start with a or z (2 ways). After forming this 12-character block, we have 14 remaining objects (the block + 14 remaining letters) to arrange: \(15!\) ways. Total: \(2 \times P(24, 10) \times 15!\).
Q16. How many ways can a set of five letters be selected from the English alphabet?
Answer: 65,780
Explanation: Selecting 5 letters from 26, order does not matter: \(C(26, 5) = \frac{26!}{5! \times 21!} = 65,780\).
Q17. A group contains n men and n women. How many ways are there to arrange these people in a row if the men and women alternate?
Answer: \(2 \times (n!)^2\)
Explanation: Two patterns: M-W-M-W-… or W-M-W-M-…
Pattern 1 (men first): Arrange n men in n positions: \(n!\) ways. Arrange n women in n positions: \(n!\) ways. Subtotal: \(n! \times n! = (n!)^2\).
Pattern 2 (women first): Similarly: \((n!)^2\) ways.
Total (Addition Principle): \(2 \times (n!)^2\).
Note: Unlike circular arrangement, in a LINEAR arrangement the two patterns are genuinely different (MWMW… is not a rotation of WMWM…).
Q18. Suppose A and B are sets with \(|A| = 10\) and \(|B| = 15\). What is the largest possible value for \(|A \cap B|\)? What is the smallest possible value for \(|A \cap B|\)? What are the possible values for \(|A \cup B|\)?
Answers:
Largest \(|A \cap B|\): 10. A can be a subset of B, so all 10 elements of A can be in B.
Smallest \(|A \cap B|\): 0. A and B can be disjoint.
Possible values of \(|A \cup B|\): By Inclusion-Exclusion: \(|A \cup B| = 10 + 15 – |A \cap B| = 25 – |A \cap B|\). Since \(0 \leq |A \cap B| \leq 10\), we get \(15 \leq |A \cup B| \leq 25\). So all integers from 15 to 25.
Q19. If \(|A| = 8\) and \(|B| = 5\), what is \(|A \cup B| + |A \cap B|\)?
Answer: 13
Explanation: By the Inclusion-Exclusion Principle: \(|A \cup B| = |A| + |B| – |A \cap B|\). Therefore:
This is a neat trick! The sum of the union and intersection always equals the sum of the individual sizes.
Q20. A coin is flipped 10 times. How many possible outcomes: (a) in total? (b) contain exactly two heads? (c) contain at most three tails? (d) contain the same number of heads and tails?
Answers:
(a) \(2^{10} = 1,024\) outcomes.
(b) Exactly 2 heads means 8 tails. Choose 2 positions for heads: \(C(10, 2) = 45\).
(c) “At most 3 tails” means 0, 1, 2, or 3 tails (equivalently, 10, 9, 8, or 7 heads):
(d) Same number of heads and tails means 5 heads and 5 tails: \(C(10, 5) = 252\).
Q21. How many ways can 15 people be seated at a round table if B only refuses to sit on A’s right (but can sit on A’s left)?
Answer: \(14! – 13! = 13!(14-1) = 13 \times 13!\)
Explanation: Total arrangements: \((15-1)! = 14!\). In how many arrangements is B sitting on A’s right? Fix A in a position (circular, so A’s position doesn’t matter). Then B must be in the specific seat to A’s right. The remaining 13 people can be arranged in \(13!\) ways. So the number where B is on A’s right = \(13!\). Subtract: \(14! – 13! = 13!(14 – 1) = 13 \times 13!\).
Compare with the previous version where B refused to sit NEXT to A (either side): that answer was \(14! – 2 \times 13!\). Here only one side is forbidden, so we subtract only \(13!\).
Q22. Find the number of permutations of the letters in the word PROPOSITION.
Answer: 1,663,200
Explanation: PROPOSITION has 11 letters. Let me count each: P(2), R(1), O(3), S(1), I(2), T(1), N(1). Wait, let me recount: P-R-O-P-O-S-I-T-I-O-N. That is: P(2), R(1), O(3), S(1), I(2), T(1), N(1). Total = 2+1+3+1+2+1+1 = 11. Correct!
Q23. In how many ways can a set of two positive integers less than 100 be chosen?
Answer: 4,851
Explanation: Positive integers less than 100: {1, 2, …, 99} — that is 99 numbers. We choose 2 (order does not matter since it is a “set”): \(C(99, 2) = \frac{99 \times 98}{2} = 4,851\).
Q24. How many permutations of the letters in the word BASEBALL?
Answer: 5,040
Explanation: BASEBALL has 8 letters: B(2), A(2), S(1), E(1), L(2).
Q25. Let S = {1, 2, 3, 4, 5, 6}. How many subsets of cardinality 4: (a) are there total? (b) contain {2, 3, 5} as a subset? (c) contain at least one odd number?
Answers: (a) 15 (b) 3 (c) 15
Explanation:
(a) \(C(6, 4) = C(6, 2) = 15\).
(b) If {2,3,5} must be in the subset, we need 1 more element from the remaining {1, 4, 6}: \(C(3, 1) = 3\). The subsets are {1,2,3,5}, {2,3,4,5}, {2,3,5,6}.
(c) Odd numbers in S: {1, 3, 5}. Use subtraction: all 4-subsets minus those with NO odd numbers (all from {2,4,6}): \(C(6,4) – C(3,4)\). But \(C(3,4) = 0\) (cannot choose 4 from 3). So the answer is \(15 – 0 = 15\). This makes sense: every 4-element subset of {1,2,3,4,5,6} MUST contain at least one odd number, since there are only 3 even numbers!