danger of confusion. But be alert that doing this can lead to ambiguity.
Is it reasonable that (9, 10, 11) should be the same as 91011? If so, then
(9, 10, 11) = 91011 = (9,1,0,1,1), which makes no sense. We will thus almost
always adhere to the parenthesis/comma notation for lists.
Lists are important because many real-world phenomena can be de-
scribed and understood in terms of them. For example, your phone number
(with area code) can be identified as a list of ten digits. Order is essential,
for rearranging the digits can produce a different phone number. A byte is
another important example of a list. A byte is simply a length-eight list of
0’s and 1’s. The world of information technology revolves around bytes.
To continue our examples of lists, (a, 15) is a list of length two. Likewise
(0, (0, 1, 1)) is a list of length two whose second entry is a list of length three.
The list (N, Z, R) has length three, and each of its entries is a set. We
emphasize that for two lists to be equal, they must have exactly the same
entries in exactly the same order. Consequently if two lists are equal, then
they must have the same length. Said differently, if two lists have different
lengths, then they are not equal. For example, (0, 0, 0, 0, 0, 0) 6= (0, 0, 0, 0, 0).
For another example note that
bread
¡
¢
( g, r, o, c, e, r, y, l, i, s, t )
milk
eggs
6=
mustard
coffee
because the list on the left has length eleven but the list on the right has
just one entry (a piece of paper with some words on it).
There is one very special list which has no entries at all. It is called
the empty list, and is denoted (). It is the only list whose length is zero.
One often needs to count up the number of possible lists that satisfy
some condition or property. For example, suppose we need to make a list of
length three having the property that the first entry must be an element
©
©
of the set a, b, cª, the second entry must be in 5, 7ª and the third entry
©
must be in a, xª. Thus (a, 5, a) and (b, 5, a) are two such lists. How many
such lists are there all together? To answer this question, imagine making
the list by selecting the first element, then the second and finally the third.
This is described in Figure 3.1. The choices for the first list entry are
a, b or c, and the left of the diagram branches out in three directions, one
for each choice. Once this choice is made there are two choices (5 or 7)
for the second entry, and this is described graphically by two branches
from each of the three choices for the first entry. This pattern continues
Counting Lists
65
for the choice for the third entry, which is either a or x. Thus, in the
diagram there are 3 · 2 · 2 = 12 paths from left to right, each corresponding
to a particular choice for each entry in the list. The corresponding lists
are tallied at the far-right end of each path. So, to answer our original
question, there are 12 possible lists with the stated properties.
Resulting list
first choice
second choice
third choice
a
(a, 5, a)
5
x
(a, 5, x)
a
a
(a, 7, a)
7
x
(a, 7, x)
a
(b, 5, a)
5
x
(b, 5, x)
b
a
(b, 7, a)
7
x
(b, 7, x)
a
(c, 5, a)
5
x
(c, 5, x)
c
a
(c, 7, a)
7
x
(c, 7, x)
Figure 3.1. Constructing lists of length 3
We summarize the type of reasoning used above in an important fact
called the multiplication principle.
Fact 3.1
(Multiplication Principle) Suppose in making a list of length
n there are a1 possible choices for the first entry, a2 possible choices for
the second entry, a3 possible choices for the third entry and so on. Then
the total number of different lists that can be made this way is the product
a1 · a2 · a3 · ··· · an.
So, for instance, in the above example we had a1 = 3, a2 = 2 and a3 = 2,
so the total number of lists was a1 · a2 · a3 = 3 · 2 · 2 = 12. Now let’s look at
some additional examples of how the multiplication principle can be used.
Example 3.1
A standard license plate consists of three letters followed
by four numbers. For example, JRB-4412 and MMX-8901 are two standard
license plates. (Vanity plates such as LV2COUNT are not included among
the standard plates.) How many different standard license plates are
possible?
66
Counting
To answer this question, note that any standard license plate such as
JRB-4412 corresponds to a length-7 list (J,R,B,4,4,1,2), so the question
can be answered by counting how many such lists are possible. We use the
multiplication principle. There are a1 = 26 possibilities (one for each letter
of the alphabet) for the first entry of the list. Similarly, there are a2 = 26
possibilities for the second entry and a3 = 26 possibilities for the third
entry. There are a4 = 10 possibilities for the fourth entry, and likewise
a5 = a6 = a7 = 10. Therefore there are a total of a1 · a2 · a3 · a4 · a5 · a6 · a7 =
26 · 26 · 26 · 10 · 10 · 10 · 10 = 175,760,000 possible standard license plates.
There are two types of list-counting problems. On one hand, there are
situations in which the same symbol or symbols may appear multiple times
in different entries of the list. For example, license plates or telephone
numbers can have repeated symbols. The sequence CCX-4144 is a perfectly
valid license plate in which the symbols C and 4 appear more than once.
On the other hand, for some lists repeated symbols do not make sense or
are not allowed. For instance, imagine drawing 5 cards from a standard
52-card deck and laying them in a row. Since no 2 cards in the deck
are identical, this list has no repeated entries. We say that repetition is
allowed in the first type of list and repetition is not allowed in the second
kind of list. (Often we call a list in which repetition is not allowed a
non-repetitive list.) The following example illustrates the difference.
Example 3.2
Consider making lists from symbols A, B, C, D, E, F, G.
(a) How many length-4 lists are possible if repetition is allowed?
(b) How many length-4 lists are possible if repetition is not allowed?
(c) How many length-4 lists are possible if repetition is not allowed and
the list must contain an E?
(d) How many length-4 lists are possible if repetition is allowed and the
list must contain an E?
Solutions:
(a) Imagine the list as containing four boxes that we fill with selections
from the letters A,B,C,D,E,F and G, as i
llustrated below.
(
,
,
,
)
7 choices
7 choices
7 choices
7 choices
There are seven possibilities for the contents of each box, so the total
number of lists that can be made this way is 7 · 7 · 7 · 7 = 2401.
Counting Lists
67
(b) This problem is the same as the previous one except that repetition is
not allowed. We have seven choices for the first box, but once it is filled
we can no longer use the symbol that was placed in it. Hence there are
only six possibilities for the second box. Once the second box has been
filled we have used up two of our letters, and there are only five left to
choose from in filling the third box. Finally, when the third box is filled
we have only four possible letters for the last box.
(
,
,
,
)
7 choices
6 choices
5 choices
4 choices
Thus the answer to our question is that there are 7 · 6 · 5 · 4 = 840 lists in
which repetition does not occur.
(c) We are asked to count the length-4 lists in which repetition is not
allowed and the symbol E must appear somewhere in the list. Thus E
occurs once and only once in each such list. Let us divide these lists into
four categories depending on whether the E occurs as the first, second,
third or fourth entry. These four types of lists are illustrated below.
Type 1
Type 2
Type 3
Type 4
( E ,
,
,
) (
, E ,
,
) (
,
, E ,
) (
,
,
, E )
6 choices
6 choices
6 choices
6 choices
5 choices
5 choices
5 choices
5 choices
4 choices
4 choices
4 choices
4 choices
Consider lists of the first type, in which the E appears in the first entry.
We have six remaining choices ( A,B,C,D,F or G) for the second entry, five
choices for the third entry and four choices for the fourth entry. Hence
there are 6 · 5 · 4 = 120 lists having an E in the first entry. As indicated
in the above diagram, there are also 6 · 5 · 4 = 120 lists having an E in the
second, third or fourth entry. Thus there are 120 + 120 + 120 + 120 = 480
such lists all together.
(d) Now we must find the number of length-four lists where repetition
is allowed and the list must contain an E. Our strategy is as follows.
By Part (a) of this exercise there are 7 · 7 · 7 · 7 = 74 = 2401 lists where
repetition is allowed. Obviously this is not the answer to our current
question, for many of these lists contain no E. We will subtract from
2401 the number of lists that do not contain an E. In making a list that
does not contain an E, we have six choices for each list entry (because
68
Counting
we can choose any one of the six letters A,B,C,D,F or G). Thus there
are 6 · 6 · 6 · 6 = 64 = 1296 lists that do not have an E. Therefore the final
answer to our question is that there are 2401 − 1296 = 1105 lists with
repetition allowed that contain at least one E.
Perhaps you wondered if Part (d) of Example 3.2 could be solved with
a setup similar to that of Part (c). Let’s try doing it that way. We want
to count the length-4 lists (with repetition allowed) that contain at least
one E. The following diagram is adapted from Part (c), the only difference
being that there are now seven choices in each slot because we are allowed
to repeat any of the seven letters.
Type 1
Type 2
Type 3
Type 4
( E ,
,
,
) (
, E ,
,
) (
,
, E ,
) (
,
,
, E )
7 choices
7 choices
7 choices
7 choices
7 choices
7 choices
7 choices
7 choices
7 choices
7 choices
7 choices
7 choices
This gives a total of 73 + 73 + 73 + 73 = 1372 lists, an answer that is
substantially larger than the (correct) value of 1105 that we got in our
solution to Part (d) above. It is not hard to see what went wrong. The
list (E, E, A, B) is of type 1 and type 2, so it got counted twice. Similarly
(E, E, C, E) is of type 1, 3 and 4, so it got counted three times. In fact, you
can find many similar lists that were counted multiple times.
In solving counting problems, we must always be careful to avoid this
kind of double-counting or triple-counting, or worse.
Exercises for Section 3.1
Note: A calculator may be helpful for some of the exercises in this chapter. This
is the only chapter for which a calculator may be helpful. (As for the exercises in
the other chapters, a calculator makes them harder.)
1. Consider lists made from the letters T,H,E,O,R,Y, with repetition allowed.
(a) How many length-4 lists are there?
(b) How many length-4 lists are there that begin with T ?
(c) How many length-4 lists are there that do not begin with T ?
2. Airports are identified with 3-letter codes. For example, the Richmond, Virginia
airport has the code RIC, and Portland, Oregon has PDX. How many different
3-letter codes are possible?
3. How many lists of length 3 can be made from the symbols A,B,C,D,E,F if...
Counting Lists
69
(a) ... repetition is allowed.
(b) ... repetition is not allowed.
(c) ... repetition is not allowed and the list must contain the letter A.
(d) ... repetition is allowed and the list must contain the letter A.
4. Five cards are dealt off of a standard 52-card deck and lined up in a row. How
many such line-ups are there in which all 5 cards are of the same suit?
5. Five cards are dealt off of a standard 52-card deck and lined up in a row. How
many such line-ups are there in which all 5 cards are of the same color (i.e.,
all black or all red)?
6. Five cards are dealt off of a standard 52-card deck and lined up in a row. How
many such line-ups are there in which exactly one of the 5 cards is a queen?
7. This problem involves 8-digit binary strings such as 10011011 or 00001010
(i.e., 8-digit numbers composed of 0’s and 1’s).
(a) How many such strings are there?
(b) How many such strings end in 0?
(c) How many such strings have the property that their second and fourth
digits are 1’s?
(d) How many such strings have the property that their second or fourth digits
are 1’s?
8. This problem concerns lists made from the symbols A,B,C,D,E.
(a) How many such length-5 lists have at least one letter repeated?
(b) How m
any such length-6 lists have at least one letter repeated?
9. This problem concerns 4-letter codes made from the letters A,B,C,D,...,Z.
(a) How many such codes can be made?
(b) How many such codes have no two consecutive letters the same?
10. This problem concerns lists made from the letters A,B,C,D,E,F,G,H,I,J.
(a) How many length-5 lists can be made from these letters if repetition is not
allowed and the list must begin with a vowel?
(b) How many length-5 lists can be made from these letters if repetition is not
allowed and the list must begin and end with a vowel?
(c) How many length-5 lists can be made from these letters if repetition is not
allowed and the list must contain exactly one A?
11. This problem concerns lists of length 6 made from the letters A,B,C,D,E,F,G,H.
How many such lists are possible if repetition is not allowed and the list
contains two consecutive vowels?
12. Consider the lists of length six made with the symbols P, R, O, F, S, where
repetition is allowed. (For example, the following is such a list: (P,R,O,O,F,S).)
How many such lists can be made if the list must end in an S and the symbol
O is used more than once?
70
Counting
3.2 Factorials
In working the examples from Section 3.1, you may have noticed that often
we need to count the number of non-repetitive lists of length n that are
made from n symbols. In fact, this particular problem occurs with such
frequency that a special idea, called a factorial, is introduced to handle it.
The table below motivates this idea. The first column lists successive
integer values n (beginning with 0) and the second column contains a
©
set
A, B, ···ª of n symbols. The third column contains all the possible
non-repetitive lists of length n which can be made from these symbols.
Finally, the last column tallies up how many lists there are of that type.
Notice that when n = 0 there is only one list of length 0 that can be made
from 0 symbols, namely the empty list ( ). Thus the value 1 is entered in
the last column of that row.
n
Symbols
Non-repetitive lists of length n made from the symbols
n!
0
©ª
( )
1
1
© Aª
(A)
1
2
© A, Bª
(A, B), (B, A)
2
3
© A, B, Cª
(A, B, C), (A, C, B), (B, C, A), (B, A, C), (C, A, B), (C, B, A)
6
(A,B,C,D), (A,B,D,C), (A,C,B,D), (A,C,D,B), (A,D,B,C), (A,D,C,B)
4
© A, B, C, Dª
(B,A,C,D), (B,A,D,C), (B,C,A,D), (B,C,D,A), (B,D, A,C), (B,D,C,A)
Book of Proof Page 10
