Permutations and Combinations

Fundamental Counting Principle

If one event can occur in m ways and another event can occur in n ways, then both events together can occur in m × n ways.

Multiply the number of choices for each step

Example 1: Outfits

3 shirts, 4 pants. How many outfits?

Calculate:

3 × 4 = 12 outfits

Example 2: Three Choices

Restaurant menu: 3 appetizers, 5 entrees, 4 desserts

How many three-course meals?

3 × 5 × 4 = 60 meals

Example 3: Passwords

Password: 2 letters then 3 digits

Letters: 26 choices each Digits: 10 choices each

Total:

26 × 26 × 10 × 10 × 10 = 676,000 passwords

Factorial Notation

Factorial: Product of all positive integers up to n

Notation: n! (read "n factorial")

Formula: n! = n × (n-1) × (n-2) × ... × 2 × 1

Special: 0! = 1 (by definition)

Examples of Factorials

5! = 5 × 4 × 3 × 2 × 1 = 120

4! = 4 × 3 × 2 × 1 = 24

3! = 3 × 2 × 1 = 6

2! = 2 × 1 = 2

1! = 1

0! = 1

Simplifying Factorial Expressions

8!/6! = (8 × 7 × 6!)/(6!) = 8 × 7 = 56

Cancel common factorial in numerator and denominator

Permutations

Permutation: Arrangement where order matters

Formula for n items taken r at a time:

nPr = n!/(n-r)!

Or: nPr = n × (n-1) × (n-2) × ... × (n-r+1) (r factors)

Example 1: Arrange All Items

Arrange 4 books on shelf. How many ways?

All 4 items, so use 4!:

4! = 4 × 3 × 2 × 1 = 24 ways

Example 2: Partial Arrangement

10 people, choose 3 for president, VP, secretary. How many ways?

Order matters (different positions)

Using formula:

10P3 = 10!/(10-3)!
     = 10!/7!
     = 10 × 9 × 8
     = 720 ways

Example 3: Starting Lineup

12 players on team, choose starting lineup of 5 (order matters for positions)

Calculate:

12P5 = 12!/7!
     = 12 × 11 × 10 × 9 × 8
     = 95,040 ways

Combinations

Combination: Selection where order does NOT matter

Formula for n items taken r at a time:

nCr = n!/[r!(n-r)!]

Also written as: (n choose r) or C(n,r)

Key difference: Combinations divide by r! to remove duplicate orderings

Example 1: Committee Selection

8 people, choose committee of 3. How many ways?

Order doesn't matter (same committee regardless of order chosen)

Using formula:

8C3 = 8!/[3!(8-3)!]
    = 8!/(3! × 5!)
    = (8 × 7 × 6)/(3 × 2 × 1)
    = 336/6
    = 56 ways

Example 2: Pizza Toppings

12 toppings available, choose 4. How many combinations?

Calculate:

12C4 = 12!/(4! × 8!)
     = (12 × 11 × 10 × 9)/(4 × 3 × 2 × 1)
     = 11,880/24
     = 495 combinations

Example 3: Card Hands

From 52-card deck, how many 5-card hands?

Calculate:

52C5 = 52!/(5! × 47!)
     = (52 × 51 × 50 × 49 × 48)/(5 × 4 × 3 × 2 × 1)
     = 311,875,200/120
     = 2,598,960 hands

Permutations vs Combinations

Ask: "Does order matter?"

Order matters → Permutation (nPr)

• Race winners (1st, 2nd, 3rd)
• Password digits
• Seating arrangements

Order doesn't matter → Combination (nCr)

• Committee members
• Pizza toppings
• Lottery numbers

Example: Same Situation, Different Question

10 students, choose 3

Question A: For president, VP, treasurer (different roles)

• Order matters: 10P3 = 720

Question B: For a committee (same role)

• Order doesn't matter: 10C3 = 120

Relationship Between P and C

nPr = nCr × r!

Permutations = Combinations × (ways to arrange r items)

Example: Verify Relationship

5P3 = 5!/(5-3)! = 60

5C3 = 5!/(3! × 2!) = 10

Check: 10 × 3! = 10 × 6 = 60 ✓

Special Cases

nCn = 1 (choose all items, only 1 way)

nC0 = 1 (choose none, only 1 way)

nC1 = n (choose 1 item, n ways)

nCr = nC(n-r) (symmetry property)

Example: Symmetry

7C2 = 7C5

Both equal:

7!/(2! × 5!) = 21

Choosing 2 to include = choosing 5 to exclude

Multiple Step Problems

Combine counting principles

Example 1: Committee with Restrictions

6 men, 4 women. Choose committee of 3 men and 2 women.

Men: 6C3 = 20 Women: 4C2 = 6

Total: 20 × 6 = 120 committees

Example 2: At Least Problems

8 people, choose committee of at least 3. (Can be 3, 4, 5, 6, 7, or 8)

Calculate each:

8C3 + 8C4 + 8C5 + 8C6 + 8C7 + 8C8
= 56 + 70 + 56 + 28 + 8 + 1
= 219 ways

Alternative: Total - (fewer than 3)

2^8 - (8C0 + 8C1 + 8C2)
= 256 - (1 + 8 + 28)
= 219 ways

Calculator Use

Most calculators have:

• nPr button
• nCr button (or combination button)

Enter: n, then nPr or nCr, then r

Example: 10P3

• Press: 10, nPr, 3, =
• Result: 720

Real-World Applications

Lottery: Combinations (order doesn't matter)

Lock combinations: Actually permutations (order matters!)

Scheduling: Permutations for ordered events

Quality control: Combinations for selecting samples

Genetics: Combinations for gene selection

Example: Lottery

Lottery: Choose 6 numbers from 1-49

How many possible tickets?

49C6 = 49!/(6! × 43!)
     = 13,983,816 possible tickets

Practice