How many four-digit PINs are there?
Counting in discrete maths means working out how many choices or arrangements exist without listing them all. The answer for a four-digit PIN is 10,000, and you can find it in one line.
A security team uses the same skill to judge how hard a password is to guess. This lesson gives you three tools: the product rule, permutations and combinations.
By the end of this lesson
Note
I can count choices and arrangements.
Key words
| Word | What it means | Example |
|---|---|---|
| Product rule | multiply the choices at each step | |
| Factorial | a whole number times every smaller one down to 1 | 5! = 120 |
| Permutation | a choice where the order matters | |
| Combination | a choice where the order does not matter | |
| Arrangement | one way of putting things in order |
The cells students fill in are left blank in this preview.
The product rule multiplies the choices
A PIN has four places. Each place can be any of 10 digits, whatever the other places hold. So the number of PINs is 10 times 10 times 10 times 10.
This is the product rule: when you make one choice after another, multiply the number of options at each step.
Worked example: two kinds of password
| Password | Choices at each place | Count |
|---|---|---|
| 4-digit PIN | 10 x 10 x 10 x 10 | 10,000 |
| 3 lower-case letters, then 2 digits | 26 x 26 x 26 x 10 x 10 | 1,757,600 |
| 6 lower-case letters | 26 x 26 x 26 x 26 x 26 x 26 | 308,915,776 |
The cells students fill in are left blank in this preview.
Check the first two counts
python3 -c "print(10 ** 4, 26 ** 3 * 10 ** 2)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A permutation counts orders without repeats
Five runners race. How many ways can the top three places go to different runners? Gold has 5 choices. Silver has 4 left. Bronze has 3 left. That is 5 x 4 x 3 = 60.
A choice where the order matters and nobody repeats is a permutation. Putting all 5 in order gives 5 x 4 x 3 x 2 x 1, written 5! and called 5 factorial.
Worked example: the first factorials
| n | n factorial | How it grows |
|---|---|---|
| 0 | 1 | By rule, one way to arrange nothing |
| 1 | 1 | 1 |
| 2 | 2 | 1 x 2 |
| 3 | 6 | 2 x 3 |
| 4 | 24 | 6 x 4 |
| 5 | 120 | 24 x 5 |
| 6 | 720 | 120 x 6 |
The cells students fill in are left blank in this preview.
Factorial of 5 and the podium count
python3 -c "import math; print(math.factorial(5), math.perm(5, 3))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A combination ignores the order
Now pick a team of 3 from 5 people, A to E. A team of A, B, C is the same team as C, B, A. The order does not matter.
Count the permutations, 60, then divide by the 6 orders each team can stand in. 60 / 6 = 10. That count is a combination.
Worked example: all ten teams of three
| Team 1 | Team 2 | Team 3 | Team 4 | Team 5 |
|---|---|---|---|---|
| A B C | A B D | A B E | A C D | A C E |
| A D E | B C D | B C E | B D E | C D E |
The cells students fill in are left blank in this preview.
Count them by brute force
python3 -c "import itertools; print(len(list(itertools.permutations('ABCDE', 3))), len(list(itertools.combinations('ABCDE', 3))))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people count a team with permutations. That gives 60 for a team of 3 from 5, but only 10 teams exist. Use permutations when the order matters, such as a podium. Use combinations when it does not, such as a team.
Try it: count with a loop
total = 1
for place in range(4):
total = total * 10
print("PINs:", total)
# Change range(4) to range(6). How many times bigger is the count?
teams = 1
for step in range(3):
teams = teams * (5 - step)
print("podiums:", teams, "teams:", teams // 6)