Combinations
Selecting items where order doesn't matter
🧺 Combinations
Definition
A \(k\)-combination is a subset of \(k\) distinct elements chosen from a set of \(n\) elements. Unlike permutations, order does NOT matter.
Formula: \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)
Read as "n choose k"
Combination Calculator
🔺 Pascal's Triangle
Pascal's Triangle is a geometric arrangement of binomial coefficients. Each number is the sum of the two numbers directly above it.
Key Properties:
- Recursive Formula: \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\)
- Row Sums: The sum of the \(n\)-th row is \(2^n\).
- Symmetry: \(\binom{n}{k} = \binom{n}{n-k}\)
🥗 Combinations with Repetition
The "Salad" Problem
We have an unlimited supply of Tomatoes, Cucumbers, and Onions. We want to make a salad with 4 ingredients. How many different salads can we make?
Stars and Bars Visualization
We need to choose 4 items from 3 types. This is equivalent to arranging 4 "stars" (items) and 2 "bars" (separators).
Total Positions = 4 (items) + 2 (bars) = 6
We just need to choose where to put the 2 bars!
\(\binom{4+3-1}{3-1} = \binom{6}{2} = 15\)
General Formula
The number of combinations of size \(k\) from \(n\) types with repetition allowed is:
\(\binom{n+k-1}{k} = \binom{n+k-1}{n-1}\)
📝 Test Your Understanding
Question 1:
How many ways can you choose a committee of 3 people from a group of 10?
Question 2:
You want to buy 5 donuts from a shop that sells 3 types (Glazed, Chocolate, Jelly). How many different selections can you make?