Section 4.2 Counting
255
example 31
Let A and B be disjoint finite sets. Then 0 A c B 0 = 0 A 0 + 0 B 0 .
Finding 0 A c B 0 can be done by the disjoint cases of counting the number of
elements in A, 0 A 0 , and the number of elements in B, 0 B 0 . By the addition principle,
we sum these two numbers.
example 32
If A and B are finite sets, then
0 A − B 0 = 0 A 0 − 0 A d B 0
and
0 A − B 0 = 0 A 0 − 0 B 0 if B # A
To prove the first equality, note that
(A − B) c (A d B) = (A d B′) c (A d B)
= A d (B′ c B)
= A d S
= A
so that A = (A − B) c (A d B). Also, A − B and A d B are disjoint sets; therefore,
by Example 31,
0 A 0 = 0 (A − B) c (A d B) 0 = 0 A − B 0 + 0 A d B 0
or
0 A − B 0 = 0 A 0 − 0 A d B 0
The second equation follows from the first, because if B # A then A d B = B.
Using the Principles together
Frequently the addition principle is used in conjunction with the multiplication
principle.
example 33
Referring to Example 24, suppose we want to find how many different ways the
child can choose the candy, rather than the number of sets of candy the child can
have. Then choosing a red jellybean followed by a yellow gummy bear is not the
same as choosing a yellow gummy bear followed by a red jellybean. We can consider two disjoint cases—choosing jellybeans first or choosing gummy bears first.
Each of these cases (by the multiplication principle) has six outcomes, so (by the
addition principle) there are 6 + 6 = 12 possible ways to choose the candy.
255
example 31
Let A and B be disjoint finite sets. Then 0 A c B 0 = 0 A 0 + 0 B 0 .
Finding 0 A c B 0 can be done by the disjoint cases of counting the number of
elements in A, 0 A 0 , and the number of elements in B, 0 B 0 . By the addition principle,
we sum these two numbers.
example 32
If A and B are finite sets, then
0 A − B 0 = 0 A 0 − 0 A d B 0
and
0 A − B 0 = 0 A 0 − 0 B 0 if B # A
To prove the first equality, note that
(A − B) c (A d B) = (A d B′) c (A d B)
= A d (B′ c B)
= A d S
= A
so that A = (A − B) c (A d B). Also, A − B and A d B are disjoint sets; therefore,
by Example 31,
0 A 0 = 0 (A − B) c (A d B) 0 = 0 A − B 0 + 0 A d B 0
or
0 A − B 0 = 0 A 0 − 0 A d B 0
The second equation follows from the first, because if B # A then A d B = B.
Using the Principles together
Frequently the addition principle is used in conjunction with the multiplication
principle.
example 33
Referring to Example 24, suppose we want to find how many different ways the
child can choose the candy, rather than the number of sets of candy the child can
have. Then choosing a red jellybean followed by a yellow gummy bear is not the
same as choosing a yellow gummy bear followed by a red jellybean. We can consider two disjoint cases—choosing jellybeans first or choosing gummy bears first.
Each of these cases (by the multiplication principle) has six outcomes, so (by the
addition principle) there are 6 + 6 = 12 possible ways to choose the candy.