Permutations and combinations
Permutations and combinations belong to combinatorics, the branch of mathematics that counts arrangements. Both answer the question "how many ways can I pick r items from n distinct items without repeats?" The difference is whether order matters.
- A permutation is an ordered arrangement. Gold, silver and bronze medals for three runners out of eight is a permutation problem, because finishing first is different from finishing second.
- A combination is an unordered selection. Choosing three runners out of eight to advance to the final is a combination problem, because the group is the same regardless of the order in which they were picked.
A so-called combination lock is really a permutation lock, since 1-2-9 and 9-2-1 open different locks.
Permutation formula
The exclamation mark means factorial: n! = n × (n − 1) × … × 2 × 1, with 0! defined as 1. Intuitively, there are n choices for the first position, n − 1 for the second, and so on for r positions.
Example
Eight runners compete for gold, silver and bronze. The number of possible podiums is 8P3 = 8! / 5! = 8 × 7 × 6 = 336.
Combination formula
Every group of r items can be ordered in r! ways, so dividing the permutation count by r! removes the duplicates. nCr is also called the binomial coefficient and is read "n choose r".
Example
A five-card poker hand is drawn from a 52-card deck. The order the cards arrive in does not matter, so the number of possible hands is 52C5 = 52! / (5! × 47!) = 2,598,960. If order did matter, there would be 52P5 = 311,875,200 sequences, exactly 5! = 120 times as many.
Quick comparison
| n | r | nPr | nCr |
|---|---|---|---|
| 5 | 2 | 20 | 10 |
| 6 | 2 | 30 | 15 |
| 10 | 3 | 720 | 120 |
| 10 | 5 | 30,240 | 252 |
| 49 | 6 | 10,068,347,520 | 13,983,816 |
Useful properties
- nC0 = nCn = 1: there is exactly one way to choose nothing or everything.
- nCr = nC(n − r): choosing which r items to take is the same as choosing which n − r to leave.
- nPn = n!: arranging all n items in order.
- The values of nCr form Pascal's triangle, and each entry is the sum of the two above it.
When repetition is allowed
This calculator assumes each item can be used at most once. If items can repeat, the counts change: ordered selections with repetition number nr (a 4-digit PIN has 104 = 10,000 possibilities), and unordered selections with repetition number (n + r − 1)C r.
Where these counts show up
Lottery odds, card-game probabilities, password strength, tournament scheduling, committee selection and genetics problems all rely on these formulas. To turn a count into a probability, divide the number of favorable outcomes by the total number of outcomes. The chance of matching all six numbers in a 6-of-49 lottery, for instance, is 1 in 13,983,816.
Choosing the right formula
Ask one question: if you rearranged the chosen items, would that count as a different outcome? If yes, use permutations. Seating four guests in four numbered chairs, ranking your top three films, or setting a four-digit code with no repeated digits are permutation problems. If no, use combinations. Picking a five-person committee, choosing three pizza toppings, or selecting lottery numbers are combination problems.
Large numbers
Factorials grow extremely fast: 20! already exceeds 2.4 quintillion. The calculator uses exact whole-number arithmetic, so even results with dozens of digits, such as 100P30, are shown in full rather than rounded.