46 SETS Chapter 1
The rationale behind Formula 3, as illustrated in Example 2, is that
there are k activities to be performed and n ways of doing each of them,
thus there is a total of "n multiplied by itself k times," or nk possibilities.
The rationale behind Formula 4, illustrated in Example 3, is that n ac-
tivities are to be carried out, with n ways of performing the first, n - 1 ways
of performing the second, and so on. The problem described in Formula
4 is often called computing the number of permutations of n things taken n
at a time, abbreviated P(n, n). There is also a convenient shorthand notation
for the quantity involved in Formula 4.
REMARK 2 If n is a positive integer, we denote by the term n factorial, sym-
bolized by the notation n!, the quantity (n)(n - l)(n - 2).. (3)(2)(1).
Finally, we define O! = 1.
We may summarize the conclusion of Formula 4 by the equation
P(n, n) = n!.
EXAMPLE 4 Consider the nine digits 1,2,... ,8,9. (a) How many nine-digit
sequences can be built from these nine digits if no repeated uses of digits
is allowed? (b) How many four-digit sequences, also with no repeats,
are possible?
Solution (a) This solution follows directly from Counting Formula 4, let-
ting n = 9. That is, P(9,9) = 9! = 362,880.
(b) For this problem we must return to the fundamental counting
principle. There are nine ways of choosing the first digit, eight of choosing
the second, seven of choosing the third, six of choosing the fourth, and
we stop there. Thus there are a total of 9 x 8 x 7 x 6 = 3024 ways of
forming such a sequence. Expressed in terms of factorial notation, the
answer could be expressed as 9! divided by S!. 0
The problem described in Example 4(b) is one of counting the number of
permutations of n objects (n = 9) taken r at a time (r = 4), and is denoted
P(n, r). We may summarize the conclusion of Example 4(b) by the equation
P(n, r) = n!/(n - r)!, 0 5 r 5 n.
Counting formulas 3 and 4 are the basis of our ability to find counting
formulas for three very -important situations involving finite sets, namely:
(a) If n(A) = m, and n(B) = m,, what is n(A x B)?
(h) If n(A) = m, what is n(P(A))?
(c) If n(A) = m, what is the number of "k-element subsets" of A, where
O~ksm.Discussion (a) A x B consists of all ordered pairs of the form (a, h) where
a E A and b E B. Clearly there are m, ways of choosing the first entry
in an ordered pair and, for each of these, there are m, ways of choosing