48 SETS Chapter 1
k (0 5 k 5 m), this becomes C(m, k) = P(m, k)/P(k, k) = m!/(m - k)!k!.
This is the formula for the number of k-element subsets of an m-element
set. Let us again try a few special cases. If k = 0, then C(m, 0) =
m!/m!O! = 1. The empty set is, of course, the only zero-element subset
of an m-element set! If k = 1, then C(m, 1) = m!/(m - 1)!1! = m. An m-
element set has exactly m singleton subsets!
We summarize the results of the preceding discussion in Counting
Formulas 5.
COUNTING FORMULAS 5
Let A and B be finite sets. Then:(a) n(A x B) = n(A)n(B)
(b) If n(A) = m, then n(.iP(A)) = 2".
(c) If n(A) = m, then the number of k-element subsets of A (0 I k I m) is
given by C(m, k) = m!l(m - k)!k!.
EXAMPLE 5 Suppose U = (1,2,3,... ,9,10). How many cases are cov-
ered by the statement of the associative law for union of sets, that is,
A u (B u C) = (A u B) u C for all subsets A, B, and C of U?
Solution. The question is one of counting the number of ways of choosing
three particular subsets of the ten-element universal set. By Counting
Formula 5, part (b), there are 2'' = 1024 ways of choosing the set A. Since
repeated use of sets is clearly appropriate, there are again 2'' ways of
selecting B and 2'' ways of taking a set C. By the fundamental counting
principle, with k = 3 and n, = n, = n, = 21°, there are = 230 =
(1024)3 cases of the associative law, for a universal set of ten elements.
0
EXAMPLE 6 A student at registration for fall term must select 4 courses
from a total of 25 available courses. How many choices of 4 courses
does the student have?
Solution This problem is a direct application of Formula 5(c), with m =
25 and k = 4. The total number of choices is C(25,4) = (25)!/(21)! 4! =
25 x 23 x 22 = 12,650. 0Compare the answer to Example 6 with the answer of 720 to the problem
that immediately preceded Counting Formula 2. There is a relationship be-
tween the two problems. Can you explain why the answer to the second
problem should be so much larger than the answer to the first?
There is much more that can be done with the theory of finite counting,
including the theory of finite probability. Some additional information is
contained in the exercises for this article. Our primary interest in counting,
however, is that it serve as an aid in mathematical reasoning and especially
in the writing of certain mathematical proofs. Another purpose is that the
answer to certain counting problems can shed light on the value of general-