Permutations and Combinations
Counting without listing — the art of arranging and selecting objects systematically
In this chapter
6.1 Fundamental Principle of Counting
"Every body of discovery is mathematical in form because there is no other guidance we can have." — Darwin
Imagine you have a suitcase with a 4-digit number lock. You remember the first digit is 7. How many combinations might you need to try? Instead of listing them all, we can use counting principles to find the answer quickly.
The Multiplication Principle
If one event can happen in m ways, AND another event can happen in n ways, THEN both events together can happen in m × n ways.
Example: Mohan has 3 pants and 2 shirts. Total outfits = 3 × 2 = 6
For 3 events in sequence:
Total = m × n × p
Example: Sabnam has 2 bags, 3 tiffin boxes, 2 bottles.
Total ways to carry them = 2 × 3 × 2 = 12
Example: 4-Letter Words from ROSE
Fill 4 positions:
• 1st position: 4 choices (R, O, S, or E)
• 2nd position: 3 choices remaining
• 3rd position: 2 choices remaining
• 4th position: 1 choice remaining
Total = 4 × 3 × 2 × 1 = 24 words
If letters can repeat:
Each position has 4 choices, so total = 4 × 4 × 4 × 4 = 256 words
6.2 Factorial Notation
When we multiply consecutive numbers, we use factorial notation to make things shorter.
Examples
• 5! = 1 × 2 × 3 × 4 × 5 = 120
• 7! = 5040
• 0! = 1 (by definition)
Properties
• n! = n × (n-1)!
• n! = n × (n-1) × (n-2)!
• 5! = 5 × 4! = 5 × 4 × 3!
Think of it this way: arranging 0 objects can be done in exactly 1 way — do nothing! Also, it makes formulas work: n! = n × (n-1)!, so 1! = 1 × 0!, which gives 0! = 1.
6.3 Permutations
A permutation is an arrangement where order matters. ABC is different from BAC.
Formula for Permutations
This gives the number of ways to arrange r objects from n distinct objects.
Choose 2 people from 12 for Chairman and Vice-Chairman:
12P2 = 12! / (12-2)! = 12! / 10! = 12 × 11 = 132 ways
Order matters: (A=Chairman, B=Vice) is different from (B=Chairman, A=Vice)
Permutations with Repetition (Identical Objects)
If n objects include p identical objects of one kind:
Permutations = n! / p!
Example: Word ROOT has 4 letters with 2 O's.
Permutations = 4! / 2! = 24 / 2 = 12
If there are p₁ of kind 1, p₂ of kind 2, etc.:
Permutations = n! / (p₁! × p₂! × ... × pₖ!)
Example: Word INSTITUTE has 9 letters (I×2, T×3)
Permutations = 9! / (2! × 3!) = 362880 / 12 = 30240
Example: Vowels Together in DAUGHTER
Treat vowels (A, U, E) as one block:
• 5 consonants + 1 vowel block = 6 objects
• Arrange 6 objects: 6! ways
• Arrange vowels within block: 3! ways
• Total = 6! × 3! = 720 × 6 = 4320
6.4 Combinations
A combination is a selection where order doesn't matter. ABC is the same as BAC.
Formula for Combinations
Permutation: Order MATTERS (arranging people in a line)
Combination: Order DOESN'T matter (selecting a committee)
Key relationship: nPr = nCr × r!
Each combination has r! permutations.
Example: Selecting a Committee
5C3 = 5! / (3! × 2!) = 120 / (6 × 2) = 10 ways
Note: Selecting {A,B,C} is same as {C,B,A} — order doesn't matter!
Properties of Combinations
Symmetry
nCr = nC(n-r)
Selecting r is same as rejecting (n-r)
Pascal's Identity
n+1Cr = nCr + nC(r-1)
Foundation of Pascal's triangle
Choose 4 cards from 52:
52C4 = 52! / (4! × 48!) = 270,725 ways
All same suit: 4 × 13C4 = 4 × 715 = 2,860 ways
6.5 Summary
• Multiplication principle: m ways × n ways = m × n total ways
• Factorial: n! = 1 × 2 × ... × n, and 0! = 1
• Permutations (order matters): nPr = n! / (n-r)!
• With repetition allowed: n^r
• Identical objects: n! / (p₁! × p₂! × ... × pₖ!)
• Combinations (order doesn't matter): nCr = n! / (r! × (n-r)!)
• Key relationship: nPr = nCr × r!