Combinations: Selections Without Order
What you'll learn: How to count selections when the order doesn't matter, like choosing team members or pizza toppings.
The Core Idea
When you studied Permutations: Arrangements Without Repetition (the previous lesson), order mattered—ABC was different from BAC. But what if you're simply choosing 3 students out of 10 to form a study group? Alice-Bob-Carol is the same group as Carol-Alice-Bob. This is a combination: selecting items where order is irrelevant.
Why Combinations Are Different
Think of permutations as arranging books on a shelf (order matters), and combinations as grabbing books to put in a bag (order doesn't matter). Since permutations count every arrangement, they overcount combinations by a factor equal to the number of ways to rearrange the selected items.
The Binomial Coefficient Formula
We write combinations as C(n, r) or nCr, also called the binomial coefficient:
C(n, r) = n! / (r! × (n - r)!)
- n = total items available
- r = items to select
- The division by
r!removes the overcounting from order
Example
How many ways can you choose 2 toppings from 4 options (pepperoni, mushrooms, olives, onions)?
C(4, 2) = 4! / (2! × 2!) = 24 / (2 × 2) = 6
The six combinations: {pepperoni, mushrooms}, {pepperoni, olives}, {pepperoni, onions}, {mushrooms, olives}, {mushrooms, onions}, {olives, onions}.
Notice: We'd have 12 permutations (P(4,2) = 12), but only 6 combinations because order doesn't matter.
Key Takeaway: Use combinations C(n, r) = n! / (r! × (n - r)!) when selecting items and order doesn't matter—essential for counting subsets, committee formations, and many algorithmic problems.