Lesson 86: Counting Principles and Combinatorics
Probability problems often require us to count the number of possible outcomes. Combinatorics is the branch of mathematics that studies counting methods, including permutations and combinations.
Core Ideas
- Fundamental Counting Principle: If one event can occur in m ways and another in n ways, then the two together can occur in m × n ways.
- Permutation: The number of ways to arrange items in order. Formula: \( P(n, r) = \dfrac{n!}{(n-r)!} \)
- Combination: The number of ways to choose items without regard to order. Formula: \( C(n, r) = \dfrac{n!}{r!(n-r)!} \)
- Factorial: \( n! = n \times (n-1) \times (n-2) \times \dots \times 1 \)
Examples
Example 1 — Counting Principle:
A menu has 3 appetizers and 4 main dishes. Number of meal choices = 3 × 4 = 12.
Example 2 — Permutations:
How many ways can 5 runners finish 1st, 2nd, and 3rd? \( P(5, 3) = \dfrac{5!}{(5-3)!} = \dfrac{120}{2} = 60 \).
Example 3 — Combinations:
How many ways can a team of 3 students be chosen from 10? \( C(10, 3) = \dfrac{10!}{3! \times 7!} = 120 \).
Practice Problems
- A lock has 3 digits, each from 0–9. How many possible codes are there?
- In how many ways can 8 books be arranged on a shelf?
- How many different 5-card poker hands can be dealt from a standard 52-card deck?
- A school club has 12 members. How many ways can they elect a president, vice president, and secretary?
- How many ways can 6 students be chosen from a group of 20 to form a committee?