Combinations & Permutations
Count in how many ways you can choose r things from n: with or without order, with or without repetition. Every step is shown — filling the places one by one, dividing out the orders for combinations — with all four answers side by side and the exact value, however large.
Which Formula Do I Need?
Ask two questions. Does the order matter? A podium (gold, silver, bronze) or a PIN code: yes, that is a permutation. A lottery ticket, a hand of cards or pizza toppings: no, only the group counts, that is a combination. Can the same item come back? Digits in a PIN and scoops of the same ice-cream flavour can; lottery balls and runners cannot.
| No repetition | Repetition allowed | |
|---|---|---|
| Order matters | podium, line-up | PIN code, password |
| Order does not matter | lottery, card hand | ice-cream scoops, coins |
Counting, Step by Step
waysStep-by-Step Solution
Worked Techniques
Gold, silver and bronze among 10 runners: 10 choices for gold, then 9 left for silver, then 8 for bronze.
A lottery ticket is a group: the 6 balls can come out in 6! = 720 orders, which all give the same ticket.
3 scoops from 5 flavours: write the scoops as stars and put 4 bars between the flavours. Every order of 3 stars and 4 bars is one choice.
Sources & Verification
- S. M. Ross, A First Course in Probability, 10th ed., Pearson, 2019 — Ch. 1 (Combinatorial Analysis: permutations, combinations, the number of integer solutions of equations).
- R. A. Brualdi, Introductory Combinatorics, 5th ed., Pearson, 2010 — Ch. 2 (Permutations and Combinations, including with repetition).
Frequently Asked Questions
What is the difference between a combination and a permutation?
In a permutation the order matters, in a combination it does not. Gold, silver and bronze for 3 of 10 runners is a permutation: P(10, 3) = 10 × 9 × 8 = 720 podiums. Choosing 3 of 10 people for a team is a combination: every team of 3 was counted 3! = 6 times among those 720 line-ups, so there are 720 ÷ 6 = 120 teams.
How do you calculate nCr?
Multiply the first r numbers counting down from n, then divide by r!. Example: the lottery, 6 numbers from 49.
1. Line-ups of 6 balls: 49 × 48 × 47 × 46 × 45 × 44 = 10,068,347,520.
2. The same 6 balls can come out in 6! = 720 orders, all giving the same ticket.
3. 10,068,347,520 ÷ 720 = 13,983,816 different tickets.
In one formula: C(n, r) = n! / (r! (n − r)!). The same way, a 5-card poker hand from 52 cards can be dealt in C(52, 5) = 2,598,960 ways.
What are the odds of winning a 6 out of 49 lottery?
There are C(49, 6) = 13,983,816 possible tickets and exactly one wins the jackpot, so the chance is 1 in 13,983,816, about 0.0000072%. Buying 10 different tickets makes it 10 in 13,983,816: still about 1 in 1.4 million.
How many 4-digit PIN codes are there?
A digit may come back and the order matters, so every one of the 4 places has 10 choices: 10⁴ = 10,000 codes, from 0000 to 9999. If all 4 digits had to be different, there would be P(10, 4) = 10 × 9 × 8 × 7 = 5,040.
How do you count combinations with repetition?
Use stars and bars: C(n + r − 1, r). Three scoops of ice cream from 5 flavours, where a flavour may be chosen more than once and the order in the cone does not matter: write the 3 scoops as stars and put 4 bars between the 5 flavours, for example ★★||★|| (two of the first flavour, one of the third). Every arrangement of 3 stars and 4 bars is one choice, so there are C(7, 3) = 35.
Why is there exactly one way to choose nothing?
Choosing 0 items from n can only be done one way: take nothing. That is why 0! = 1 and C(n, 0) = 1, which keeps the formulas working, for example C(5, 5) = 5! / (5! · 0!) = 1: there is one way to take all 5.