Page 14 - 4660

Combinatorial Analysis

A B

S

Figure 1.6 – The shaded region show A − B, those outcomes in A that do not belong to B

when all the outcomes in event B (say) also belong to event A, but A may contain, in addition,
outcomes that do not belong to B, then B is called a subset of A, a situation that is denoted by
B ⊂ A; alternatively, one may write A ⊃ B, which states that A contains B. In this case, the
closed curve representing the event B is often drawn lying completely within the closed curve
representing the event A.
The operations ∪ and ∩ are extended straightforwardly to more than two events. If there exist
n events A 1 , A 2 , . . . , A n , in some sample space S, then the event consisting of all those outcomes
that belong to one or more of the A i is the union of A 1 , A 2 , . . . , A n and is denoted by

(1.12)
A 1 ∪ A 2 ∪ . . . ∪ A n
Similarly, the event consisting of all the outcomes that belong to every one of the A i is called the
intersection of A 1 , A 2 , . . . , A n and is denoted by

(1.13)
A 1 ∩ A 2 ∩ . . . ∩ A n
If, for any pair of values i, j with i = j,

A i ∩ A j = ∅ (1.14)

then the events A i and A j are said to be mutually exclusive or disjoint.
Consider three events A, B and C with a Venn diagram such as is shown in Fig. 1.7. It will
be clear that, in general, the diagram will be divided into eight regions and they will be of four
different types. Three regions correspond to a single event; three regions are each the intersection
of exactly two events; one region is the three-fold intersection of all three events; and finally one
region corresponds to none of the events. Let us now consider the numbers of different regions
in a general n-event Venn diagram. For one-event Venn diagrams there are two regions, for the
two-event case there are four regions and, as we have just seen, for the three-event case there are
n
eight. In the general n-event case there are 2 regions, as is clear from the fact that any particular
region R lies either inside or outside the closed curve of any particular event. With two choices
n
(inside or outside) for each of n closed curves, there are 2 different possible combinations with
which to characterize R. Once n gets beyond three it becomes impossible to draw a simple two-
dimensional Venn diagram, but this does not change the results.
Using Venn diagrams, it is straightforward to show that the operations ∩ and ∪ obey the
following algebraic laws:
1. commutativity: A ∩ B = B ∩ A, A ∪ B = B ∪ A;
2. associativity: (A ∩ B) ∩ C = A ∩ (B ∩ C), (A ∪ B) ∪ C = A ∪ (B ∪ C);
3. distributivity: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C);
4. idempotency: A ∩ A = A, A ∪ A = A.

14