Lesson 4 โข 40 min read
Combinatorics
In This Lesson
1Fundamental Counting Principle
The Multiplication Principle
If one event can happen in m ways, and another event can happen in n ways, then both events can happen in m ร n ways.
Total Ways = nโ ร nโ ร nโ ร ... ร nโ
Example 1: Outfit
3 shirts and 4 pants
3 ร 4 = 12 outfits
Example 2: Password
4-digit PIN (0-9)
10โด = 10,000 PINs
The Addition Principle
If one event can happen in m ways OR another event can happen in n ways (mutually exclusive), then one of the events can happen in m + n ways.
Example: Choosing a red card (26) OR a face card that's not red (6) = 26 + 6 = 32 ways
2Factorials
Definition
n! = n ร (n-1) ร (n-2) ร ... ร 3 ร 2 ร 1
Read as "n factorial" - the product of all positive integers from 1 to n.
Common Factorials
0!
1
1!
1
2!
2
3!
6
4!
24
5!
120
6!
720
7!
5,040
Key Properties
- 0! = 1 (by definition)
- n! = n ร (n-1)! (recursive property)
- n!/n = (n-1)!
3Permutations
Definition
A permutation is an arrangement of objects where ORDER MATTERS.
P(n,r) = n! / (n-r)!
Arrange r objects from n objects
All Objects
Arranging all n objects:
P(n,n) = n!
Example: 5 books on a shelf = 5! = 120 ways
Some Objects
Choosing r from n objects:
P(n,r) = n!/(n-r)!
Example: Top 3 from 10 runners = P(10,3) = 720
Permutation with Repetition
When some objects are identical:
n! / (nโ! ร nโ! ร ... ร nโ!)
Example: Arrange MISSISSIPPI = 11!/(4! ร 4! ร 2!) = 34,650
Practice Problem:
How many 3-letter "words" from ABCDE?
P(5,3) = 5!/(5-3)! = 5!/2!
= (5 ร 4 ร 3 ร 2 ร 1)/(2 ร 1)
= 60 arrangements
4Combinations
Definition
A combination is a selection of objects where ORDER DOES NOT MATTER.
C(n,r) = n! / [r!(n-r)!]
Also written as โฟCแตฃ or (n choose r)
Permutation vs Combination
| Permutation | Combination |
|---|---|
| Order matters | Order doesn't matter |
| ABC โ BAC | ABC = BAC = CAB |
| Arrangements, rankings | Groups, teams, selections |
| P(n,r) = n!/(n-r)! | C(n,r) = n!/[r!(n-r)!] |
Key Properties
- C(n,0) = C(n,n) = 1
- C(n,1) = C(n,n-1) = n
- C(n,r) = C(n,n-r) (symmetry)
- C(n,r) = P(n,r)/r!
Practice Problem:
Choose 3 students from 10 for a committee
C(10,3) = 10!/(3! ร 7!)
= (10 ร 9 ร 8)/(3 ร 2 ร 1)
= 120 ways
5Special Arrangements
Circular Permutation
Arranging objects in a circle:
(n-1)!
Example: 6 people around a table = 5! = 120
Circular with Identical Positions
When rotations and reflections are same:
(n-1)!/2
Example: Beads on a bracelet = (n-1)!/2
Objects with Restrictions
Objects Must Be Together
Treat as one unit, then arrange within
Example: 5 people, 2 must sit together: 4! ร 2! = 48
Objects Cannot Be Together
Total - (arrangements with them together)
Example: 5 people, 2 cannot sit together: 5! - 48 = 72
Quick Reference
| Type | Formula | Example |
|---|---|---|
| Linear arrangement | n! | Books on shelf |
| Circular arrangement | (n-1)! | People at round table |
| Selection (order matters) | P(n,r) | Race winners |
| Selection (order doesn't) | C(n,r) | Team members |