44 SETS Chapter 1
that n(A u B) = 36, n(A) = 24, and n(B) = 28. By Counting Formula 1,
n(A n B) = n(A) + n(B) - n(A u B) = 24 + 28 - 36 = 16. 0
In Exercise 4 we consider the problem of extending Formula 1 to the
union of three sets, while in Exercise 3 we see an application of Venn
diagrams to solving more complex problems of the type represented by
Example 1.FUNDAMENTAL COUNTING PRINCIPLE; n(P(A))
Suppose, at registration for the fall term at a major university, a student
must elect 1 course from among 12 humanities courses, 1 from among 5
physical science courses, 1 from 6 social science courses, and either Math
105 or Computer Science 100. How many ways are there for this student
to select a slate of four courses?
This problem is typical of those whose solution is given by Counting
Formula 2.C 0 U N T l N G F 0 R M U LA 2 (Fundamental Counting Principle).
If an activity can be carried out in exactly n, ways (n, a positive integer), and for
each of these, a second activity can be carried out in n, ways, and for each of the
first two a third activity can be carried out in n, ways, and so on, then the total
number of ways of carrying out k such activities in sequence is the product
n,n2... n,.This principle is often illustrated by a tree diagram. In Figure 1.10 we
use such a diagram to illustrate the choices of a student who must choose
one of five physical science courses and one of two mathematical science
courses. In this case n, = 5 and n, = 2; a representative tree diagram looks
like the one in Figure 1.10.
The fundamental counting principle predicts that the student has a total
of n,n, = 5 x 2 = 10 possible choices; the prediction is confirmed by the
tree diagram, where we label the physical science courses A, B, C, D, and
E and the mathematical science courses X and Y.Figure 1.10 A tree diagram illustrating all possible
choices in a practical problem.
AX AY BX BYCX CYDX DYEX EY