Combinations
Unordered Selections of $k$ Objects from $n$ Distinct Objects (Without Repetition)
1. What Is a Combination?
A combination is a way of selecting a subset of items from a larger set where only the composition of the group matters, not the order in which items are chosen.
Key Idea: When we choose a $k$-element subset from an $n$-element set, we care about which items are selected, not in what order they were picked.
Everyday Examples
- Committees: Choosing 3 people from 10 to form a committee — the group {Alice, Bob, Carol} is the same regardless of who was picked first.
- Hands of cards: A poker hand of 5 cards from a 52-card deck — the hand {A♠, K♥, Q♦, J♣, 10♠} is the same no matter the dealing order.
- Pizza toppings: Choosing 3 toppings from a menu of 8 — pepperoni-mushroom-olive is the same pizza as olive-pepperoni-mushroom.
- Lottery numbers: Picking 6 numbers from 49 — the winning set is the same regardless of the order drawn.
Order Doesn't Matter
Selecting {A, B, C} from {A, B, C, D, E}:
| Arrangement | Same Combination? |
|---|---|
| A, B, C | ✓ All the same combination {A, B, C} |
| A, C, B | |
| B, A, C | |
| B, C, A | |
| C, A, B | |
| C, B, A |
These 6 = $3!$ arrangements all collapse into one combination.
2. Deriving the Combination Formula
Step-by-Step Derivation
We already know the permutation formula for choosing and arranging $k$ items from $n$:
$$ P(n,k) = \frac{n!}{(n-k)!} $$Now, every combination (unordered group) of $k$ items can be internally rearranged in $k!$ ways. So the total number of permutations equals the number of combinations times the number of internal orderings: