In this article
How many ways can five people sit in a row? How many different teams of three can be chosen from the same five? The numbers are 120 and 10. They sound like the same problem, but one of them cares about order and the other does not. That one question, “does order matter?”, is the whole difference between permutations and combinations.
Factorials: the building block
The factorial of n, written n!, is n × (n−1) × (n−2) × … × 1. It counts how many ways n different things can be lined up. With three letters A, B, C there are 3 × 2 × 1 = 6 lineups, because you have 3 choices for the first spot, 2 left for the second and 1 for the last.
1, 2, 6, 24, 120, 720, 5,040. By 10! the number is already 3,628,800 and by 20! it passes two quintillion.
Any properly shuffled deck of cards is very likely to be in an order that has never existed before in history.
Permutations: order matters
Imagine a race with 5 runners where gold, silver and bronze go to different people. The first medal can go to 5 runners, the second to the 4 left and the third to the remaining 3: 5 × 4 × 3 = 60 ways. That is 5P3.
- 1Gold: 5 choicesAny of the five runners can win.
- 2Silver: 4 choicesThe gold winner is out, four are left.
- 3Bronze: 3 choices5 × 4 × 3 = 60 different podiums.
Combinations: order does not matter
Now pick a team of 3 from 5 people. The team {Asha, Ben, Chitra} is the same team no matter who was picked first. Each team appears in 3! = 6 different orders inside the 60 podium-style lists, so we divide by 6: 60 ÷ 6 = 10 teams.
- Gold, silver, bronze are different roles
- ABC and CBA count as different
- Use when order or position matters
- Just a team of three, no roles
- ABC and CBA are the same team
- Use when you only choose a group
Every team of three can be arranged in 3! = 6 ways, so 60 ÷ 6 = 10.
The formula is nCr = n! ÷ (r! × (n − r)!). A useful symmetry: choosing r items to take is the same as choosing n − r items to leave behind, so nCr = nC(n−r). That is why 5C3 = 5C2 = 10.
The counts rise to a peak at k = 10 (1,84,756) and fall symmetrically. The same shape appears in Pascal’s triangle and in the bell curve.
| Situation | Order matters? | Formula | Example answer |
|---|---|---|---|
| Podium of 3 from 5 runners | Yes | 5P3 | 60 |
| Team of 3 from 5 people | No | 5C3 | 10 |
| 4-digit PIN, digits can repeat | Yes | 10⁴ | 10,000 |
| 4-digit code, no repeated digit | Yes | 10P4 | 5,040 |
| 5-card poker hand from 52 | No | 52C5 | 25,98,960 |
| Lottery, 6 numbers from 49 | No | 49C6 | 1,39,83,816 |
Four quick questions to ask: does order matter, can items repeat, how many are available, and how many are chosen.
Four kinds of counting
Most real problems fall into the first three. The last is rarer but useful for “with replacement” selections.
Locks, lotteries and handshakes
A “combination lock” asks for an ordered code, so it is a permutation lock. With four wheels of ten digits and repeats allowed, there are 10 × 10 × 10 × 10 = 10,000 codes. A lottery really is a combination: only the set of numbers counts, not the order in which the balls come out.
If order mattered, there would be 49P6 = 10,068,347,520 tickets, which is 720 times more.
Handshakes are combinations, because a handshake between A and B is the same handshake as between B and A. For n people the number of handshakes is nC2 = n × (n − 1) ÷ 2, which grows much faster than the head count.
Doubling the people from 50 to 100 does not double the handshakes. It multiplies them by about four, from 1,225 to 4,950.
Quick practice
- How many ways can 4 books be lined on a shelf? 4! = 24.
- How many 2-person committees from 6 people? 6C2 = 15, so 15.
- How many 3-letter codes from A–Z with no repeated letter? 26P3 = 15,600.
- How many ways to pick 4 from 4? 4C4 = 1, because there is only one group.
Once you can tell whether order matters, the formula follows. Try several n and r values in the calculator and watch how quickly the numbers grow.
Questions people ask
What is the difference between a permutation and a combination?
In a permutation order matters (ABC differs from CBA). In a combination it does not (ABC and CBA are the same group).
What is the nCr formula?
nCr = n! ÷ (r! × (n − r)!), the number of ways to choose r items from n when order does not matter.
What is 0! equal to?
1. There is exactly one way to arrange nothing, and defining 0! = 1 keeps the formulas working.
How many combinations in a 6/49 lottery?
1,39,83,816, which is 49C6. A single ticket has a 1 in 1,39,83,816 chance.
Is a combination lock a permutation or a combination?
A permutation. The order of the digits matters, so 1-2-3 and 3-2-1 are different codes.
How many ways can a deck of 52 cards be shuffled?
52!, about 8 × 10⁶⁷. That is so large that a thoroughly shuffled deck has almost certainly never occurred before.