Bridge to Abstract Mathematics: Mathematical Proof and Structures

1.5 COUNTING PROPERTIES OF FINITE SETS (OPTIONAL) 47

a1 a2 a3 am-1 am

Figure 1 .I 1 A device for representing pictorially the possible
subsets of an m-element set.

the second. By the fundamental counting principle there are m,m, ways

of selecting a first entry, followed by a second. Thus n(A x B) = n(A)n(B).

(b) The calculation of n(9(A)) involves our first clever (!) use of count-

ing principles. We have a set A with m elements; we wish to count its sub-

sets. How can we do this? We approach the problem by writing m blank

spaces in a row, one space for each of the m objects in A, which we, in

turn, represent by the symbols a,, a,,... , a,, as in Figure 1.1 1. Having

done this, we represent a subset X of A by a string of m zeros and ones,

where we write 1 in the kth place if a, E X and 0 in the kth place if

a, 6 X. The string 100 - - 000 thus represents the subset {a,); the string

1 1 1 1 1 represents A itself; the string 000. 00 represents 0. Clearly

there is a one-to-one match-up between the subsets of A and the possible

strings of m zeros and ones. (The details of this match-up constitute the

technical part of the argument if a very formal approach is taken. We

do not deal with these formalities here.) Thus we have shifted the original

problem to one covered directly by Counting Formula 3, with k = m

and n = 2 (the two objects are the symbols 0 and 1). The answer, then,

is nk = 2'".

Let us check this result with some familiar examples. If A = 0, then

m = 0, so we expect that n(9(A)) = 2' = 1. Indeed, 9(A) = {(a) which

has one element. If A = (0, {@} }, then n(A) = 2, so we expect n(9(A)) =

2, = 4. In fact, 9(A) = {a, A, {@I, {{0))), so that theory again pre-

dicts the actual result! One final note: The power set of a finite set

must be finite (recall Exercise 9(c), Article 1.1).

(c) The number of k-element subsets of an m-element set is often

called the number of combinations of m things taken k at a time, abbre-

viated C(m, k). We will arrive at a formula for C(m, k), in terms of fac-

torials, by using what we already know about permutations together

with the fundamental counting principle. Suppose, for example, we wish

to count the number of five-letter words that can be formed from the

letters A, B, C, D, E, F, G, and H, with no repeated letters allowed. On

the one hand, we know that there are P(8, 5) = 8!/(8 - 5)! = 8!/3! =

8 x 7 x 6 x 5 x 4 = 6720 such words. But we can also arrive at such

a word by first choosing five letters in no particular order [in one of

C(8,S) possible ways] and then counting the number of possible arrange-

ments of those five letters [which is P(5, 5) = 5! = 1201. By the funda-

mental counting principle, the product C(8,5) times P(5,5) should be

the number of words, namely, P(8,5) = 6720. Hence the unknown C(8,5)

must equal P(8, 5) divided by P(5, 5), or 8!/3!5!. For a general m and