1.5 COUNTING PROPERTIES OF FINITE SETS (OPTIONAL) 45In the problem posed just before the statement of Counting Formula 2,
we have n, = 12, n, = 5, n3 = 6, n, = 2, and the total number of potential
course elections is 12 x 5 x 6 x 2 = 720. Obviously, a tree diagram to
depict this situation would require considerable space, time, and labor.
It should be noted that, in order to apply the fundamental principle, we
must be able to assume that choices made at various stages of the sequence
do not limit, or otherwise affect, the possibilities for choices at different
stages. In real life this may not be the case. Our student at fall registration
may find that 4 of the 12 humanities courses create a time conflict with the
mathematics class. In such a case the assumptions of Counting Formula
2 do not apply so that, of course, the answer of 720 that it indicates is
incorrect.
EXAMPLE 2 How many 5-letter "words" can be formed from the 26 letters
of the alphabet, if there are no restrictions on the use of letters?
Solution Since we may use letters without restrictions (in particular, the
repeated use of a letter in the same word is allowed), we apply the fun-
damental counting principle with k = 5 and n, = n, = n, = n, = n, =
- The total number of words is then 26,. 0
EXAMPLE 3 How many 5-letter words can be formed from the vowels A,
E, I, 0, and U, if each vowel can be used exactly once in a word?
Solution As in Example 2, k = 5, since we must perform five activities to
form a word, namely, choose the first letter, then the second, and so on.
But in this case n, = 5, n, = 4, n3 = 3, n, = 2, and n, = 1. The reason
is that once we have chosen the first letter, there are only four ways of
choosing the second. Having chosen the first two letters, we have only
three ways of choosing the third, and so on. Thus there is a total of only
5 x 4 x 3 x 2 x 1 = 120 words in this case. 0
Examples 2 and 3 are representative of two classes of counting problems
whose solutions, although a consequence of the fundamental counting prin-
ciple, are of sufficient importance to warrant separate presentation.COUNTING FORMULA 3
The number of k-object arrangements that can be constructed from a set of n
objects, if there are no restrictions on the number of uses of each of the n objects
within an arrangement, is given by the formula nk.COUNTING FORMULA 4
The number of n-object arrangements that can be constructed from a set of n
objects, if each object can be used only once in each arrangement, is given by
n(n - l)(n - 2).. (3)(2)(1). Each such arrangement is called a permutation of
the set of n objects.