Combinations & Permutations

How many ways can you arrange a group of objects? How many ways can you choose a team? These questions are at the heart of counting, and the answers depend on one critical question: does order matter?

The Fundamental Counting Principle

If one event has m outcomes and a second event has n outcomes, then together they have m × n possible outcomes.

Worked Example 1: Counting Principle

A restaurant offers 4 appetizers, 6 entrees, and 3 desserts. How many different 3-course meals are possible?

Appetizer choices: 4
Entree choices: 6
Dessert choices: 3
Total: 4 × 6 × 3 = 72 different meals

Factorials

The factorial of a positive integer n, written n!, is the product of all positive integers from 1 to n:

n! = n \times (n-1) \times (n-2) \times ... \times 2 \times 1

n	n!
0	1 (by definition)
1	1
3	6
5	120
7	5,040
10	3,628,800

Permutations: Order Matters

A permutation is an arrangement of objects where order matters. Choosing president, vice-president, and treasurer from a group is a permutation problem -- the same three people in different roles count as different outcomes.

P(n, r) = n! / (n - r)!

This counts the number of ways to arrange r items chosen from n total items.

Worked Example 2: Permutation

From 8 runners, how many ways can gold, silver, and bronze medals be awarded?

Order matters (gold is different from silver), so use permutations.
P(8, 3) = 8! / (8-3)! = 8! / 5!
= (8 × 7 × 6 × 5!) / 5! = 8 × 7 × 6 = 336

Combinations: Order Does Not Matter

A combination is a selection where order does not matter. Choosing 3 people for a committee (no specific roles) is a combination problem -- the same three people in any order form the same committee.

C(n, r) = n! / [r! \times (n - r)!]

Worked Example 3: Combination

From 10 students, how many ways can a committee of 4 be formed?

Order does not matter, so use combinations.
C(10, 4) = 10! / (4! × 6!)
= (10 × 9 × 8 × 7) / (4 × 3 × 2 × 1) = 5,040 / 24 = 210

How to Decide: Permutation or Combination?

Ask: "If I rearrange the selected items, do I get a different outcome?" If yes, use permutations (order matters). If no, use combinations (order does not matter). Assigning roles = permutation. Choosing a group = combination.

Common Mistake: Forgetting to Divide for Combinations

The difference between P(n, r) and C(n, r) is dividing by r!. When order does not matter, many permutations represent the same group. Dividing by r! accounts for duplicate arrangements. Choosing A-B-C is the same committee as C-B-A; there are 3! = 6 ways to arrange 3 people, so we divide by 6.

Practice Problems

1. A lock has 3 dials, each with digits 0-9. How many possible codes are there?

Show Solution

Fundamental counting principle: 10 × 10 × 10 = 1,000 codes.

2. How many ways can 5 books be arranged on a shelf?

Show Solution

This is P(5, 5) = 5! = 120.

3. From 12 players, a coach selects 5 starters. How many different starting lineups are possible?

Show Solution

Order does not matter (no assigned positions): C(12, 5) = 12! / (5! × 7!) = (12 × 11 × 10 × 9 × 8) / 120 = 792.

4. How many 3-letter "words" (arrangements) can be made from the letters A, B, C, D, E with no repeats?

Show Solution

Order matters: P(5, 3) = 5 × 4 × 3 = 60.

5. A pizza shop offers 8 toppings. How many 3-topping pizzas are possible?

Show Solution

Order does not matter: C(8, 3) = 8! / (3! × 5!) = (8 × 7 × 6) / 6 = 56.

Lesson Summary

Fundamental counting principle: multiply the number of options at each stage.
n! = n × (n-1) × ... × 1, and 0! = 1.
Permutations (order matters): P(n, r) = n! / (n-r)!
Combinations (order does not matter): C(n, r) = n! / [r!(n-r)!]
The key question: does rearranging the selection create a different outcome?