(problem 1) How many numbers from the given set are multiples of the given
numbers and ?
a)
b)
c)
d)
We use De Morgan’s Law to enumerate sets.
We begin by counting the number of elements in the union of two sets.
- Proof
- Let . Then is in or both.
Case 1. ( is in both) If is in both and , then the right hand side of the formula accounts for twice, once as an element of and again as an element of . But then, since is in both and , is in their intersection, . The coefficient of being , is “de-accounted” for once in the right hand side of the formula. In total, is accounted for twice and de-accounted for once, thereby accounting for it just once in total.
Case 2. ( is in only) If but , then the right hand side of the formula accounts for such exactly once, as a member of . Note that such an is not a member of and so it is not de-accounted for by the right hand side of the formula.
Case 3. ( is in only) This is the same as case 2 with the roles of and reversed.
Finally, we need to be sure that the right hand side of the formula does not count elements that are not in .
Case 4. ( is in neither nor ) In this case, none of the terms on the right hand side of the formula will either account for or de-account for (since either).
In our discussion of partitions, we did not have a subtraction term. This is because
for each pair of sets in a partition, and hence .
example 1 How many numbers in the set are multiples of either 2 or 5?
Let be the subset of consisting of the multiples of 2, and be the subset of consisting of the multiples of 5. We seek . According to the proposition, We have and and since the set consists of the multiples of 10. Using the Inclusion-Exclusion Principle (for two sets), we can conclude that the number of elements of that are either multiples of 2 or 5 is
Let be the subset of consisting of the multiples of 2, and be the subset of consisting of the multiples of 5. We seek . According to the proposition, We have and and since the set consists of the multiples of 10. Using the Inclusion-Exclusion Principle (for two sets), we can conclude that the number of elements of that are either multiples of 2 or 5 is
Recall set complements from section 1.2:
De Morgan’s Law gives us a formula for the complement of a union in terms of the intersection of their complements.
- Proof
- First, let . Then which implies that and . By definition of complement,
this means that and . Finally, by definition of intersection, . Thus .
Next, let . By definition of intersection, and . Then, and which implies that . Thus and we have shown that .
By virtue of being subsets of each other, the two sets are equal and De Morgan’s Law is proved.
There are actually two of De Morgan’s Laws. The second is The proof of this second
law follows immediately from the first law by replacing and with and and using
the fact that for any set .
The next example uses De Morgan’s Law in conjunction with the Rule for Complements and the Inclusion-Exclusion Principle (for two sets).
example 2 Computer passwords are eight characters long where a character can be
either an upper case letter, lower case letter, digit 0-9, or one of 8 special symbols.
How many passwords are possible if a password must contain at least one digit and
at least one special symbol?
Let be the set of passwords that do not contain any digits and let be the set of passwords that do not contain any special symbols. Since our passwords must contain a digit and a special symbol, we seek . By De Morgan’s Law, Then according to the Rule for Complements, where is the set of all possible passwords with no restrictions. Combining the two equations above with the Inclusion-Exclusion Principle (for two sets), we have Each of the terms on the right hand side can be computed using the Fundamental Principle of Counting. Since there are 70 different characters in total with 10 digits and 8 special symbols, Note that the passwords in the set do not contain either digits or special symbols, so there are available characters for them. In conclusion, the number of acceptable passwords is
(problem 2) Computer passwords are eight characters long where a character
can be either an upper case letter, lower case letter, digit 0-9, or one of
8 special symbols. How many passwords are possible if a password must
contain:
a) at least one digit and at least one upper case letter?
b) at least one special symbol and at least one lower case letter?
c) at least one letter?
a) at least one digit and at least one upper case letter?
b) at least one special symbol and at least one lower case letter?
c) at least one letter?
example 3 How many permutations are there of the letters in the phrase
MATH ROCKS in which neither the word MATH nor the word ROCKS
appears?
Such permutations include MRAOTCHKS and SKCORHTAM, but not RKMATHSOC, HROCKSMTA, or ROCKSMATH. Let be the set of permutations which include the word MATH and let be the set of permutations which include the word ROCKS. We seek . By De Morgan’s Law, this is the same as . Let be the set of all permutations of the letters in the phrase. Then, applying the Rule for Complements, and the Inclusion-Exclusion Principle (for two sets), we have \begin{align*} |A^c \cap B^c| &= |(A \cup B)^c|\\ &= |S| - |A\cup B|\\ &= |S| - \Big (|A| + |B| -|A\cap B|\Big )\\ &= |S| - |A| - |B| + |A\cap B| \end{align*}
Such permutations include MRAOTCHKS and SKCORHTAM, but not RKMATHSOC, HROCKSMTA, or ROCKSMATH. Let be the set of permutations which include the word MATH and let be the set of permutations which include the word ROCKS. We seek . By De Morgan’s Law, this is the same as . Let be the set of all permutations of the letters in the phrase. Then, applying the Rule for Complements, and the Inclusion-Exclusion Principle (for two sets), we have \begin{align*} |A^c \cap B^c| &= |(A \cup B)^c|\\ &= |S| - |A\cup B|\\ &= |S| - \Big (|A| + |B| -|A\cap B|\Big )\\ &= |S| - |A| - |B| + |A\cap B| \end{align*}
The number of elements in is the number of permutations of the symbols MATH, R, O, C, K, S. Since this is 6 distinct symbols, . The number of elements in is the number of permutations of the symbols M, A, T, H, ROCKS. Since this is 5 distinct symbols, . The number of elements in is 2 and the number of elements in is . Hence, the total number of ways to permute the letters in the phrase MATH ROCKS which do not include either of the words MATH or ROCKS is
(problem 3) How many permutations are there of the letters in the phrase
DOGS RULE in which neither the word DOGS nor the word RULE appears?
example 4 How many permutations are there of the numbers 1-7 such that the 1 is
not in the first position and the 2 is not in the second position?
Let be the permutations with 1 in the first position, be the permutations with 2 in the second position and be the set of all permutations. We seek . De Morgan’s Law, the Rule for Complements and the Inclusion-Exclusion Principle (for two sets) gives: \begin{align*} |A^c \cap B^c| &= |(A \cup B)^c|\\ &= |S| - |A\cup B|\\ &= |S| - \Big (|A| + |B| - |A\cap B|\Big )\\ &= |S| - |A| - |B| + |A\cap B|\\ &= 7! - 6! - 6! + 5!\\ &= 3720 \end{align*}
Let be the permutations with 1 in the first position, be the permutations with 2 in the second position and be the set of all permutations. We seek . De Morgan’s Law, the Rule for Complements and the Inclusion-Exclusion Principle (for two sets) gives: \begin{align*} |A^c \cap B^c| &= |(A \cup B)^c|\\ &= |S| - |A\cup B|\\ &= |S| - \Big (|A| + |B| - |A\cap B|\Big )\\ &= |S| - |A| - |B| + |A\cap B|\\ &= 7! - 6! - 6! + 5!\\ &= 3720 \end{align*}
(problem 4) How many permutations are there of the letters in the word ABCDEF in
which the letter A is not first and the letter F is not last?
example 5 How many non-negative integer solutions are there to the equation if and
?
With no restrictions on the variables (except that they be non-negative integers), the total number of solutions is by the stars and bars method. Let be the set of all solutions which have and let be the set of all solutions with . We wish to find . De Morgan’s Law, the Rule for Complements and the Inclusion-Exclusion Principle (for two sets) gives: \begin{align*} |A^c \cap B^c| &= |(A \cup B)^c|\\ &= |S| - |A\cup B|\\ &= |S| - \Big (|A| + |B| - |A\cap B|\Big )\\ &= |S| - |A| - |B| + |A\cap B|\\ \end{align*}
2024-09-27 14:04:16 With no restrictions on the variables (except that they be non-negative integers), the total number of solutions is by the stars and bars method. Let be the set of all solutions which have and let be the set of all solutions with . We wish to find . De Morgan’s Law, the Rule for Complements and the Inclusion-Exclusion Principle (for two sets) gives: \begin{align*} |A^c \cap B^c| &= |(A \cup B)^c|\\ &= |S| - |A\cup B|\\ &= |S| - \Big (|A| + |B| - |A\cap B|\Big )\\ &= |S| - |A| - |B| + |A\cap B|\\ \end{align*}
where is the set of all non-negative integer solutions. By letting , we see that the number of elements in the set is the number of non-negative integer solutions to the equation: which is . By letting , we see that the number of elements in the set is the number of non-negative integer solutions to the equation: which is . Finally, by letting and we see that the number of elements in the set is the number of non-negative integer solutions to the equation: which is . Thus the total number of non-negative integer solutions to the equation with and is