When order doesn't matter Choose \(3\) pizza toppings from \(10\) .\(3! = 6\) times, once for every order, so divide:
\[\frac{_{10}P_3}{3!} = \frac{10 \cdot 9 \cdot 8}{6} = 120\]
DefinitionCombinations
The number of ways to choose \(r\) objects from \(n\) different objects, without regard to order , is
\[_nC_r = \binom{n}{r} = \frac{n!}{r!\,(n - r)!}\]
read "\(n\) choose \(r\) ".
Counting with conditions Use the counting principle to combine choices from separate groups.
ExampleA committee with conditions
A committee of \(4\) is chosen from \(6\) women and \(5\) men. How many committees have exactly \(2\) women?
Choose the women and the men separately, then multiply:
\[\binom{6}{2} \cdot \binom{5}{2} = 15 \cdot 10 = 150\]
ExampleCard hands
A \(5\) -card hand from a \(52\) -card deck can be dealt in \(\binom{52}{5} = 2\,598\,960\) ways. The number of all-heart hands is \(\binom{13}{5} = 1287\) .
Pascal's triangle RuleProperties of combinations
\[\binom{n}{0} = \binom{n}{n} = 1 \qquad\qquad \binom{n}{r} = \binom{n}{n - r} \qquad\qquad \binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r}\]
The last rule means each number is the sum of the two above it. Arranged in rows, the combinations form Pascal's triangle :
\[\begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1 \end{array}\]
Row \(n\) lists \(\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\) .
The binomial theorem ExampleExpand \((x + 2)^3\)
Row \(3\) :\(1, 3, 3, 1\) .
\[(x + 2)^3 = x^3 + 3x^2(2) + 3x(2)^2 + 2^3 = x^3 + 6x^2 + 12x + 8\]
Watch outPermutation or combination?
Choosing a president, vice president and secretary from \(10\) people: different roles, order matters, \(_{10}P_3 = 720\) .\(3\) committee members with equal roles: order doesn't matter, \(_{10}C_3 = 120\) .
Practice Quick check
What is \(\binom{n}{n}\) ?
A \(0\) B \(1\) C \(n\) D \(n!\)
There's exactly one way to choose all \(n\) objects.
Quick check
How many handshakes happen if each of \(8\) people shakes hands once with every other person?
A \(64\) B \(56\) C \(28\) D \(16\)
Each handshake is a pair: \(\binom{8}{2} = 28\) .