The fundamental counting principle
A suitcase lock has four dials. How can you count every possible code without writing a single one down?
Where you are 10 in Counting
When you reach for it
Many things are built by making choices one after another. A sandwich is a bread, then a filling, then a sauce. A lock code is a first digit, then a second, then a third. An organized list writes every result down, which suits six sandwiches but not the millions of license plates a country needs.
The counting principle finds the count without the list. Reach for it when the things being counted are built in stages, each stage can go a known number of ways, and that number stays the same however the earlier stages went. It answers “how many”, never “which ones” and never “how likely”: putting chances on the stages is the work of probabilities on a tree diagram.
The procedure
Two stages: multiply
The fundamental counting principle. If a first choice can be made in m ways, and then, whatever the first choice was, a second choice can be made in n ways, then the two choices together can be made in m \times n ways.
A small sandwich bar uses white or brown bread and one filling: cheese, egg or ham. Each path from the starting dot to an end of the tree below is one sandwich.
Here is why the count is a product. Sort the sandwiches by their bread. Every sandwich has exactly one bread, so it falls into exactly one of m = 2 groups. Inside a group the bread is fixed and the filling runs through its n = 3 choices, one sandwich each, so every group holds 3 sandwiches. Two groups of three make 2 \times 3 = 6, and in general m groups of n make m \times n. It is the argument that showed an organized list is complete, one block for each first choice, with the writing dropped.
Three or more stages
Add a sauce, chosen in p ways. Treat bread-and-filling as one first choice, made in m \times n ways, and the sauce as the second. The two-stage principle gives (m \times n) \times p, which is m \times n \times p because grouping does not change a product (the associative property of multiplication). Repeating the step stage by stage gives the general rule: if k stages can go n_1, n_2, \ldots, n_k ways,
“Whatever the first choice was”: how many, not which
The condition asks only that the number of ways at each stage be fixed. The choices themselves may change. In a race of 8 runners, 8 can win, and then 7 are left for second place. Which 7 depends on the winner, but there are always 7, so every block in the sorting argument has the same size and the product still counts correctly.
When the number itself changes with an earlier choice, the blocks have different sizes and a single product is wrong. Then count block by block and add, as with the café in Listing a sample space: lists and tables that would not serve milk with curry.
Strings from an alphabet
Codes, license plates and passwords are strings: rows of symbols in a fixed order, each taken from a set called the alphabet, such as the 10 digits 0 to 9 or the 26 letters A to Z. Order matters: 315 and 513 open different locks. Each position in the string is a stage.
Repeats allowed. Every position can be any of the n symbols, so a string of length k is k stages of n ways each: n \times n \times \cdots \times n with k factors, which is the power n^k.
No repeats. The first position can be any of the n symbols. Whatever it was, it is used up, so the second position has n - 1 choices, the third n - 2, and so on, giving k factors counting down from n:
For three-digit codes, that gives 10^3 = 1{,}000 codes with repeats allowed and 10 \times 9 \times 8 = 720 with all three digits different.
Looking ahead: when every symbol is used once, the product runs down to 1, and n \times (n - 1) \times \cdots \times 2 \times 1 is written n!, read “n factorial”; it belongs to arrangements and factorials.
Worked examples
Hyacinth’s sandwiches
Hyacinth’s sandwich bar makes each sandwich from one bread (white, brown or rye), one of 5 fillings and one of 4 sauces.
(a) How many different sandwiches can be made?
(b) A customer may also ask for no sauce at all. How many different sandwiches are there now?
Solution(a) There are three stages: bread, filling, sauce. The bread can be chosen in 3 ways. Whatever the bread, the filling can be chosen in 5 ways, and whatever the bread and filling, the sauce can be chosen in 4 ways. So the number of sandwiches is
Check. Stopping halfway, there are 3 \times 5 = 15 bread-and-filling pairs, and each pair goes with 4 sauces: 15 \times 4 = 60.
(b) “No sauce” is one more way the sauce stage can turn out, so that stage now has 4 + 1 = 5 ways and the count is 3 \times 5 \times 5 = 75. The extra 15 are one plain sandwich for each bread-and-filling pair.
Isambard’s suitcase lock
Isambard’s suitcase lock has four dials, and each dial shows a digit from 1 to 6.
(a) How many codes are there?
(b) How many codes use four different digits?
Solution(a) Each dial is a stage with 6 ways, whatever the other dials show. So
This is a string of length 4 from an alphabet of 6 symbols, with repeats allowed.
(b) The first dial can show any of the 6 digits. Whatever it shows, that digit is used up, so the second dial has 5 choices. The third then has 4 and the fourth 3:
Check. Every code in (b) is also a code in (a), so (b) must be smaller, and it is. The other 1{,}296 - 360 = 936 codes repeat at least one digit.
License plates
A country’s license plates show three letters followed by three digits, such as KTB 408. Any of the 26 letters and any of the 10 digits may be used, and repeats are allowed.
(a) How many plates are possible?
(b) The country decides never to use the letters I and O, which look too much like 1 and 0, and never to start the digits with 0. How many plates are possible now?
Solution(a) There are six stages, one for each position: three letter positions with 26 ways each and three digit positions with 10 ways each.
(b) Each letter position now has 26 - 2 = 24 ways. The first digit has 9 ways (1 to 9) and the other two still have 10:
The rules changed the number of ways at some stages, but each number is still the same whatever the other positions hold, so the product still works.
First, second and third
Seven runners, among them Gaius and Liesel, run a race with no ties. Ribbons go to first, second and third place.
(a) In how many ways can the three ribbons be given out?
(b) The organizers add a ribbon for fourth place. How many ways are there now?
Solution(a) First place can go to any of the 7 runners. Whoever wins cannot also come second, so second place goes to one of the 6 others, and third place to one of the 5 left:
Order matters: Gaius first and Liesel second is a different result from Liesel first and Gaius second, so both are counted. The answer is not 7 \times 7 \times 7, which would let one runner take two ribbons.
(b) Each of the 210 results can be followed by any of the 4 runners still left: 210 \times 4 = 840, which is 7 \times 6 \times 5 \times 4, one more stage in the product.
Kester’s password
Kester’s password has four characters, and each is a lowercase letter or a digit, so the alphabet has 26 + 10 = 36 symbols.
(a) How many passwords are there with no other rule?
(b) How many are there if the first character must be a letter?
Solution(a) Four stages of 36 ways: 36^4 = 1{,}679{,}616.
(b) The first stage now has only 26 ways, and the other three still have 36: 26 \times 36^3 = 26 \times 46{,}656 = 1{,}213{,}056.
Juniper’s playlist
Juniper’s playlist has 12 songs, and her player picks the first three songs at random.
(a) If the player never plays a song twice, how many orders are possible for the first three songs?
(b) A different player picks each song from all 12, so a song can come up again. How many orders are possible?
(c) How many of the orders in (b) have at least one song played more than once?
Solution(a) This is a string of length 3 from 12 songs with no repeats: 12 \times 11 \times 10 = 1{,}320.
(b) Now every pick has 12 ways: 12^3 = 1{,}728.
(c) Every order in (b) either has three different songs or repeats a song, never both. The orders with three different songs are exactly the 1{,}320 from (a), so the orders with a repeat are everything else:
Check, counting the repeats directly. All three songs the same: 12 orders. Exactly two the same: choose the place of the odd song out (3 ways), the repeated song (12 ways) and the odd song, which must differ from it (11 ways), so 3 \times 12 \times 11 = 396. Together 12 + 396 = 408. Counting what you do not want and subtracting it from the total is often the shorter road.
Boundaries
Each stage must have a fixed number of ways. The ways themselves may change with earlier choices, as the runners left for second place do. If the number changes, the product is wrong: count each case separately and add.
“And then” multiplies; “or” adds. One choice from a group of m or from a group of n, with nothing in both, is a single stage with m + n ways. Multiplying would count pairs, one from each group, which is a different question.
Each result must come from exactly one sequence of choices. If two sequences give the same result, the product counts it more than once. Choosing 2 of 6 volunteers as a first and then a second gives 6 \times 5 = 30, but if the two simply form a pair, each pair has been counted twice, once in each order, and there are only 15 pairs. Order-free choosing is the work of combinations.
Where this goes next
The no-repeat product is a permutation count, and when it runs all the way down it becomes the factorial of arrangements. Dividing out the orders that do not matter turns permutations into combinations. When a rule sits on one position, such as an odd last digit with no repeats allowed, the order in which the stages are filled starts to matter, which is counting with a restriction.
Strings also explain a law of exponents: a string of length j + k is a string of length j followed by one of length k, so n^{j+k} = n^j \times n^k. The whole family of methods lives under counting.
Exercises
Two stages
- Gaius makes a sandwich from one of 4 kinds of roll and one of 6 fillings. How many sandwiches can he make? How many if he also adds one of 3 sauces?
- A lock has two dials, and each dial shows a letter from A to H. How many codes are there?
- On a small island a license plate is one letter followed by two digits, such as R07. How many plates are possible?
Three or more stages
- A sandwich is one of 3 breads, one of 7 fillings and one of 4 sauces, and it is served toasted or not toasted. How many sandwiches are there?
- A padlock has five dials, each showing a digit from 0 to 9. How many codes are there?
- License plates show three letters followed by four digits, with repeats allowed. How many plates are possible?
- A code has five symbols, and each is one of the digits 1, 2, 3 and 4. How many codes are there?
- How many strings of length 7 can be made from the alphabet of two symbols, 0 and 1?
No repeats
- Eleven runners run a race with no ties. In how many ways can first, second and third place be filled?
- Liesel’s playlist has 9 songs. In how many orders can the first four songs be played if no song is played twice?
- A lock has four dials showing digits from 0 to 9. How many codes use four different digits?
- How many strings of length 3 can be made from the letters A, B, C, D and E if letters may repeat? How many if they may not?
- Juniper, Kester, Liesel and Isambard stand in a row for a photograph. In how many orders can they stand?
A rule at some stages
- A password is two letters followed by three digits, and the last digit must be odd. How many passwords are possible?
- A license plate is two letters, neither of them a vowel (A, E, I, O or U), followed by three digits whose first digit is not 0. How many plates are possible?
- How many whole numbers from 100 to 999 are there? Count them as strings of three digits whose first digit is not 0. How many of them have three odd digits?
- Kester’s lock has three dials showing digits from 0 to 9, and no two neighboring dials may show the same digit. How many codes are there?
- Six runners, one of them Gaius, run a race with no ties. In how many ways can first, second and third place be filled by runners other than Gaius?
Adding and subtracting
- A code is three letters, each from A to H. How many codes have at least one letter repeated?
- A country’s plates are either three letters followed by three digits or three digits followed by three letters, with repeats allowed. How many plates are possible?
- Hyacinth’s lunch bar sells either a wrap with one of 4 fillings or a roll with one of 6 fillings. How many different lunches are there? Explain why the answer is not 24.
Reasoning
- Explain, without drawing a tree, why a first choice that can be made in m ways followed by a second that can always be made in n ways gives m \times n results.
- Isambard says a three-dial lock with digits 0 to 9 has 10 + 9 + 8 = 27 codes with three different digits. Explain what is wrong and give the right count.
- Explain why doubling the size of an alphabet multiplies the number of strings of length 4 by 16.
Answers
- 4 \times 6 = 24 sandwiches; with a sauce, 24 \times 3 = 72.
- 8 \times 8 = 64 codes: A to H is 8 letters, and each dial can show any of them.
- 26 \times 10 \times 10 = 2{,}600 plates.
- 3 \times 7 \times 4 \times 2 = 168 sandwiches. Toasted or not is a fourth stage with 2 ways.
- 10^5 = 100{,}000 codes.
- 26^3 \times 10^4 = 17{,}576 \times 10{,}000 = 175{,}760{,}000 plates.
- 4^5 = 1{,}024 codes.
- 2^7 = 128 strings.
- 11 \times 10 \times 9 = 990 ways.
- 9 \times 8 \times 7 \times 6 = 3{,}024 orders.
- 10 \times 9 \times 8 \times 7 = 5{,}040 codes.
- With repeats, 5^3 = 125; without, 5 \times 4 \times 3 = 60.
- 4 \times 3 \times 2 \times 1 = 24 orders. Whoever stands first, 3 are left for the second place, and so on.
- 26 \times 26 \times 10 \times 10 \times 5 = 338{,}000 passwords. The last digit has 5 ways: 1, 3, 5, 7 or 9.
- 21 \times 21 \times 9 \times 10 \times 10 = 396{,}900 plates. Leaving out the 5 vowels leaves 21 letters, and the first digit has 9 ways.
- 9 \times 10 \times 10 = 900 numbers, which matches 999 - 100 + 1 = 900. Three odd digits: 5 \times 5 \times 5 = 125, and none can start with 0, since 0 is not odd.
- 10 \times 9 \times 9 = 810 codes. The second dial must differ from the first, so 9 ways; the third must differ only from the second, so 9 again.
- 5 \times 4 \times 3 = 60 ways: the three places are filled from the 5 runners who are not Gaius.
- 176. All codes: 8^3 = 512. Codes with three different letters: 8 \times 7 \times 6 = 336. The rest repeat a letter: 512 - 336 = 176.
- 35{,}152{,}000. Each format gives 26^3 \times 10^3 = 17{,}576{,}000 plates, and no plate fits both, since one starts with a letter and the other with a digit, so add: 2 \times 17{,}576{,}000 = 35{,}152{,}000.
- 4 + 6 = 10 lunches. A lunch is a wrap or a roll, one choice from 10 options with none in both groups. The product 4 \times 6 = 24 would count pairs of one wrap and one roll.
- Sort the results by their first choice. Each result has one first choice, so it lies in exactly one of the m groups. In each group the first choice is fixed and the second runs through its n ways, one result each, so every group has n results, and m groups of n hold m \times n results.
- Every first digit can be followed by any of 9 second digits, and every such pair by any of 8 third digits, so the counts multiply: 10 \times 9 \times 8 = 720 codes. Adding would count one choice from three separate groups, not a code built from all three.
- With an alphabet of n symbols there are n^4 strings of length 4. With 2n symbols there are (2n)^4 = 2^4 \times n^4 = 16n^4, since each of the four stages has twice as many ways and 2 \times 2 \times 2 \times 2 = 16.