What are Permutations and Combinations?
Permutations and combinations are fundamental counting techniques in mathematics used to calculate the number of ways to arrange or select items from a set. The key difference is whether the order matters.
The Key Difference
Permutation (Order Matters)
ABC ≠ BAC ≠ CAB
6 different arrangements of 3 items
Combination (Order Doesn't Matter)
ABC = BAC = CAB
All the same selection of 3 items
Permutation Formula (nPr)
P(n, r) = n! / (n - r)!
Where n = total items, r = items to arrange
A permutation counts the number of ways to arrange r items from a set of n items where the order of arrangement matters. Use permutations when you need to consider different sequences as different outcomes.
Why Does the Permutation Formula Work?
When arranging r items from n items where order matters, we use the multiplication principle:
For P(5, 3) - choosing 3 items from 5:
- • 1st position: 5 choices (any of the 5 items)
- • 2nd position: 4 choices (one item already used)
- • 3rd position: 3 choices (two items already used)
Total = 5 × 4 × 3 = 60
This equals n × (n-1) × (n-2) × ... × (n-r+1), which simplifies to n! / (n-r)! because dividing by (n-r)! cancels the terms we don't need.
Permutation Example: P(5, 3) = ?
P(5, 3) = 5! / (5 - 3)!
P(5, 3) = 5! / 2!
P(5, 3) = (5 × 4 × 3 × 2 × 1) / (2 × 1)
P(5, 3) = 120 / 2
P(5, 3) = 60 arrangements
Combination Formula (nCr)
C(n, r) = n! / (r! × (n - r)!)
Where n = total items, r = items to select
A combination counts the number of ways to select r items from a set of n items where the order does NOT matter. Use combinations when you only care about which items are selected, not the order in which they are selected.
Why Does the Combination Formula Work?
Combinations build on permutations but remove duplicate orderings. Since we don't care about order, we divide by the number of ways to arrange the selected items.
For C(5, 3) - selecting 3 items from 5:
- • P(5, 3) = 60 arrangements (with order)
- • But ABC, ACB, BAC, BCA, CAB, CBA are all the same selection
- • There are 3! = 6 ways to arrange 3 items
- • So we divide: 60 ÷ 6 = 10 unique selections
C(n, r) = P(n, r) / r! = n! / (r! × (n-r)!)
The r! in the denominator accounts for removing all the duplicate orderings of the r selected items.
Visual Proof: Why C(5, 3) = 10
Selecting 3 letters from {A, B, C, D, E} - all 10 unique combinations:
Note: ABC = ACB = BAC = BCA = CAB = CBA (all counted as ONE combination)
Combination Example: C(5, 3) = ?
C(5, 3) = 5! / (3! × (5 - 3)!)
C(5, 3) = 5! / (3! × 2!)
C(5, 3) = 120 / (6 × 2)
C(5, 3) = 120 / 12
C(5, 3) = 10 selections
Relationship Between P and C
P(n, r) = C(n, r) × r!
Permutations = Combinations × (ways to arrange r items)
Notice that P(5,3) = 60 and C(5,3) = 10. The relationship is: 60 = 10 × 6, where 6 = 3! (the number of ways to arrange 3 items). This makes sense because permutations count every arrangement, while combinations count each unique selection only once.
Mathematical Derivation of Formulas
Deriving P(n, r) from First Principles
For n items, choosing r positions with order:
Position 1: n choices
Position 2: (n-1) choices
Position 3: (n-2) choices
...
Position r: (n-r+1) choices
P(n,r) = n × (n-1) × (n-2) × ... × (n-r+1)
= n! / (n-r)! (multiply top and bottom by (n-r)!)
Deriving C(n, r) from P(n, r)
Start with permutations:
P(n, r) counts all arrangements
Each combination is counted r! times
(because r items can be arranged r! ways)
C(n, r) = P(n, r) / r!
= [n! / (n-r)!] / r!
= n! / [r! × (n-r)!]
Important Identities & Properties
Symmetry Property
C(n, r) = C(n, n-r)
Choosing r items = Choosing which (n-r) to leave out
Pascal's Identity
C(n, r) = C(n-1, r-1) + C(n-1, r)
Include item n or exclude it
Sum of Row
Σ C(n, k) = 2ⁿ (for k=0 to n)
Total subsets of n items
Boundary Cases
C(n, 0) = C(n, n) = 1
One way to choose nothing or everything
When to Use Permutations vs Combinations
Use Permutations When:
- Arranging items in a specific order (e.g., books on a shelf)
- Creating passwords or PINs
- Race finishing positions (1st, 2nd, 3rd)
- Seating arrangements
- Scheduling tasks in order
Use Combinations When:
- Selecting team members from a group
- Choosing lottery numbers
- Picking pizza toppings
- Forming committees
- Card hands (poker, bridge)
Quick Decision Guide
Ask yourself: "If I rearrange the selected items, do I get a different outcome?"
- YES → Use Permutation (order matters)
- NO → Use Combination (order doesn't matter)
Real-World Applications
- Probability: Calculating odds in games, lotteries, and statistical experiments
- Computer Science: Algorithm analysis, generating all possible combinations/permutations
- Cryptography: Calculating password strength and encryption key possibilities
- Sports: Determining playoff brackets, round-robin tournament schedules
- Genetics: Calculating genetic combinations and trait inheritance patterns
Real-World Problems with Step-by-Step Solutions
Practice identifying whether to use permutations or combinations with these real-world examples.
Problem 1: Creating a Password
Question: A website requires a 4-character password using only uppercase letters (A-Z). No letter can be repeated. How many different passwords are possible?
Step 1: Identify the type
Does order matter? YES! "ABCD" is a different password than "DCBA". → Use Permutation
Step 2: Identify n and r
n = 26 (total letters A-Z)
r = 4 (characters in password)
Step 3: Apply the formula
P(26, 4) = 26! / (26 - 4)!
P(26, 4) = 26! / 22!
↳ Cancel 22! from numerator and denominator:
= (26 × 25 × 24 × 23 × 22!) / 22!
= 26 × 25 × 24 × 23
P(26, 4) = 358,800 passwords
Answer: 358,800 different passwords are possible.
Problem 2: Lottery Numbers
Question: A lottery requires you to pick 6 numbers from 1 to 49. How many different lottery tickets are possible?
Step 1: Identify the type
Does order matter? NO! Picking {3, 7, 12, 25, 33, 41} is the same as {41, 33, 25, 12, 7, 3}. → Use Combination
Step 2: Identify n and r
n = 49 (total numbers to choose from)
r = 6 (numbers to pick)
Step 3: Apply the formula
C(49, 6) = 49! / (6! × 43!)
↳ Cancel 43! from numerator and denominator:
= (49 × 48 × 47 × 46 × 45 × 44 × 43!) / (6! × 43!)
= (49 × 48 × 47 × 46 × 45 × 44) / (6 × 5 × 4 × 3 × 2 × 1)
↳ Simplify: 48÷6=8, 45÷5=9, 44÷4=11, 46÷2=23
= 49 × 8 × 47 × 23 × 9 × 11
C(49, 6) = 13,983,816 tickets
Answer: 13,983,816 different lottery combinations. Your odds of winning are about 1 in 14 million!
Problem 3: Race Results
Question: In a race with 10 runners, how many different ways can the gold, silver, and bronze medals be awarded?
Step 1: Identify the type
Does order matter? YES! Runner A getting gold and Runner B getting silver is different from Runner B getting gold and Runner A getting silver. → Use Permutation
Step 2: Identify n and r
n = 10 (total runners)
r = 3 (medal positions: gold, silver, bronze)
Step 3: Apply the formula
P(10, 3) = 10! / (10 - 3)!
P(10, 3) = 10! / 7!
↳ Cancel 7! from numerator and denominator:
= (10 × 9 × 8 × 7!) / 7!
= 10 × 9 × 8
P(10, 3) = 720 ways
Answer: There are 720 different ways to award the medals.
Problem 4: Team Selection
Question: A teacher needs to select 4 students from a class of 20 to form a study group. How many different groups are possible?
Step 1: Identify the type
Does order matter? NO! A group with Alice, Bob, Carol, and Dave is the same as a group with Dave, Carol, Bob, and Alice. → Use Combination
Step 2: Identify n and r
n = 20 (total students)
r = 4 (students to select)
Step 3: Apply the formula
C(20, 4) = 20! / (4! × 16!)
↳ Cancel 16! from numerator and denominator:
= (20 × 19 × 18 × 17 × 16!) / (4! × 16!)
= (20 × 19 × 18 × 17) / (4 × 3 × 2 × 1)
↳ Simplify: 20÷4=5, 18÷3=6, then 6÷2=3
= 5 × 19 × 3 × 17
C(20, 4) = 4,845 groups
Answer: 4,845 different study groups are possible.
Problem 5: Poker Hands
Question: How many different 5-card poker hands can be dealt from a standard 52-card deck?
Step 1: Identify the type
Does order matter? NO! The hand {A♠, K♠, Q♠, J♠, 10♠} is the same regardless of the order dealt. → Use Combination
Step 2: Identify n and r
n = 52 (cards in deck)
r = 5 (cards in hand)
Step 3: Apply the formula
C(52, 5) = 52! / (5! × 47!)
↳ Cancel 47! from numerator and denominator:
= (52 × 51 × 50 × 49 × 48 × 47!) / (5! × 47!)
= (52 × 51 × 50 × 49 × 48) / (5 × 4 × 3 × 2 × 1)
↳ Simplify: 50÷5=10, 52÷4=13, 51÷3=17, 48÷2=24
= 13 × 17 × 10 × 49 × 24
C(52, 5) = 2,598,960 hands
Answer: 2,598,960 different poker hands. A royal flush (only 4 possible) has odds of about 1 in 650,000!
Problem 6: Seating Arrangement
Question: A family of 5 is taking a photo. How many different ways can they arrange themselves in a single row?
Step 1: Identify the type
Does order matter? YES! Having Mom on the left and Dad on the right is different from Dad on the left and Mom on the right. → Use Permutation
Step 2: Identify n and r
n = 5 (family members)
r = 5 (all members are being arranged)
Note: When n = r, we're arranging ALL items
Step 3: Apply the formula
P(5, 5) = 5! / (5 - 5)!
P(5, 5) = 5! / 0!
P(5, 5) = 5! / 1 = 5!
P(5, 5) = 5 × 4 × 3 × 2 × 1
P(5, 5) = 120 arrangements
Answer: 120 different photo arrangements are possible.
Problem 7: PIN Code (Repetition Allowed)
Question: A bank ATM requires a 4-digit PIN using digits 0-9. Digits CAN be repeated (like 1234, 1111, or 1221). How many different PINs are possible?
Step 1: Understand the difference
This is different from Problem 1 (passwords)! Here, digits CAN repeat.
Order matters: "1234" ≠ "4321", AND we can use "1111" or "1221".
→ Use Permutation with Repetition
Step 2: The new formula
With Repetition: nr (n to the power r)
n = 10 (digits 0-9)
r = 4 (positions in PIN)
Each position can independently be any of the n choices!
Step 3: Apply the formula
Permutation with Repetition = nr
= 104
= 10 × 10 × 10 × 10
= 10,000 PINs
Step 4: Why does this work?
Using the multiplication principle:
• 1st digit: 10 choices (0-9)
• 2nd digit: 10 choices (same digit can repeat!)
• 3rd digit: 10 choices
• 4th digit: 10 choices
Total = 10 × 10 × 10 × 10 = 10,000
Answer: 10,000 different PINs are possible (from 0000 to 9999).
Key Comparison: With vs Without Repetition
WITHOUT Repetition (Problem 1)
4-letter password from A-Z, no repeats
P(26,4) = 26 × 25 × 24 × 23 = 358,800
WITH Repetition (This Problem)
4-digit PIN from 0-9, repeats allowed
104 = 10 × 10 × 10 × 10 = 10,000
Notice: If we had a 4-digit PIN WITHOUT repetition, it would be P(10,4) = 10 × 9 × 8 × 7 = 5,040. With repetition gives us nearly twice as many possibilities!
Problem 8: Ice Cream Scoops (Combination with Repetition)
Question: An ice cream shop has 5 flavors: Vanilla, Chocolate, Strawberry, Mint, and Mango. You want to buy 3 scoops. You CAN pick the same flavor multiple times (like 3 Vanilla scoops, or 2 Chocolate + 1 Mint). How many different combinations are possible?
Step 1: Identify the type
Does order matter? NO! (V, C, M) = (M, C, V) = (C, V, M)
Can items repeat? YES! (V, V, V) is allowed
→ Use Combination with Repetition
Step 2: The special formula
Combination with Repetition: C(n + r - 1, r) = (n + r - 1)! / (r! × (n - 1)!)
n = 5 (flavors)
r = 3 (scoops to choose)
Step 3: Apply the formula
C(n + r - 1, r) = C(5 + 3 - 1, 3)
= C(7, 3) = 7! / (3! × 4!)
↳ Cancel 4! from numerator and denominator:
= (7 × 6 × 5 × 4!) / (3! × 4!)
= (7 × 6 × 5) / (3 × 2 × 1)
↳ Simplify: 6÷3=2, then 2÷2=1
= 7 × 5 = 35
= 35 combinations
Step 4: Verify by listing (Stars and Bars method)
This formula uses the "Stars and Bars" technique. Imagine 3 stars (scoops) and 4 bars (dividers between 5 flavors):
★★★|||| = 3 Vanilla, 0 others
★|★|★|| = 1V, 1C, 1S, 0M, 0Ma
||★★|★| = 0V, 0C, 2S, 1M, 0Ma
We're arranging 7 symbols (3 stars + 4 bars), choosing where to place 3 stars = C(7,3)
Answer: 35 different ice cream combinations are possible.
Summary: All Four Counting Types
| Type | Order? | Repeat? | Formula | Example |
|---|---|---|---|---|
| Permutation | Yes | No | n!/(n-r)! | Race medals |
| Combination | No | No | n!/(r!(n-r)!) | Lottery picks |
| Perm. w/ Rep. | Yes | Yes | nr | PIN codes |
| Comb. w/ Rep. | No | Yes | C(n+r-1, r) | Ice cream scoops |
Tips for Solving P&C Problems
- Always ask: "Does the order/arrangement matter?"
- Look for keywords: "arrange", "order", "sequence", "first/second/third" suggest Permutation. "Select", "choose", "pick", "group", "committee" suggest Combination.
- Test with small numbers: If unsure, try with n=3, r=2 and list all possibilities manually.
- Remember: P(n,r) is always ≥ C(n,r) because permutations count more arrangements.
Common Values Reference
| n | r | P(n,r) | C(n,r) |
|---|---|---|---|
| 5 | 2 | 20 | 10 |
| 6 | 3 | 120 | 20 |
| 10 | 3 | 720 | 120 |
| 10 | 5 | 30,240 | 252 |
| 52 | 5 | 311,875,200 | 2,598,960 |