16 1. Let’s Count!
these will be very difficult to pronounce, and are not likely to occur, but
let’s count all of them as possibilities). The second field has 2 possible
entries. The third field can be thought of as three separate fields, having
12, 31, and 100 possible entries, respectively (some combinations of these
will never occur, for example, 04-31-76 or 02-29-13, but let’s ignore this).
The last field has 13 possible entries.
Now how do we determine the number of ways these can be combined?
The argument we described above can be repeated, just “3 choices” has
to be replaced, in order, by “26^8 choices,” “2 choices,” “12 choices,” “31
choices,” “100 choices,” and “13 choices.” We get that the answer is 26^8 ·
2 · 12 · 31 · 100 ·13 = 201, 977 , 536 , 857 , 907 ,200.
We can formulate the following generalization of Theorem 1.5.1 (the
proof consists of repeating the argument above).
Theorem 1.5.2Suppose that we want to form strings of lengthnby using
any of a given set ofk 1 symbols as the first element of the string, any of
a given set ofk 2 symbols as the second element of the string, etc., any of
a given set ofknsymbols as the last element of the string. Then the total
number of strings we can form isk 1 ·k 2 ···kn.
As another special case, consider the following problem: how many non-
negative integers have exactlyndigits (in decimal)? It is clear that the first
digit can be any of 9 numbers (1, 2 ,...,9), while the second, third, etc.,
digits can be any of the 10 digits. Thus we get a special case of the previous
question withk 1 = 9 andk 2 =k 3 =···=kn= 10. Thus the answer is
9 · 10 n−^1 (cf. Exercise 1.3.4).
1.5.1Draw a tree illustrating the way we counted the number of strings of
length 2 formed from the charactersa,b, andc, and explain how it gives the
answer. Do the same for the more general problem whenn=3,k 1 =2,k 2 =3,
k 3 =2.
1.5.2In a sports shop there are T-shirts of 5 different colors, shorts of 4 different
colors, and socks of 3 different colors. How many different uniforms can you
compose from these items?
1.5.3On a Toto (soccer poll) ticket, you have to bet 1, 2, or X for each of 13
games. In how many different ways can you fill out the ticket?
1.5.4We roll a die twice; how many different outcomes can we have? (A 1
followed by a 4 is different from a 4 followed by a 1.)
1.5.5We have 20 different presents that we want to distribute to 12 children.
It is not required that every child get something; it could even happen that we
give all the presents to the same child. In how many ways can we distribute the
presents?