Math 116: Final Exam Study Guide Chapter 5

Chapter 5: The Principle of Inclusion and Exclusion
Exercise 1 Let \vert X \vert = 45 with three subsets A_1, A_2, and A_3 such that
  1. \vert A_1 \vert= 17
  2. \vert A_2 \vert= 18
  3. \vert A_3 \vert= 15
  4. \vert A_1 \cap A_2 \vert = 13
  5. \vert A_2 \cap A_3 \vert = 10
  6. \vert A_1 \cap A_3 \vert = 14
  7. \vert A_1 \cap A_2 \cap A_3 \vert = 7
Compute \vert X \setminus (A_1 \cup A_2 \cup A_3)\vert.
 Note that

    \begin{align*} \vert A_1 \cup A_2 \cup A_3 \vert =&\; \vert A_1 \vert + \vert A_2 \vert + \vert A_3 \vert \\ &- \vert A_1 \cap A_2 \vert - \vert A_1 \cap A_3 \vert - \vert A_2 \cap A_3 \vert \\ &+ \vert A_1 \cap A_2 \cap A_3\vert \\ =& \; 20 \end{align*}

Therefore, \vert X \setminus (A_1 \cup A_2 \cup A_3)\vert=45-20=25.
Exercise 2 The list of partitions of \{1,2,3,4\} are:
  1. \{1,2,3,4\}
  2. \{1\}\cup\{2,3,4\}
  3. \{2\}\cup\{1,3,4\}
  4. \{3\}\cup\{1,2,4\}
  5. \{4\}\cup\{1,2,3\}
  6. \{1,2\}\cup\{3,4\}
  7. \{1,3\}\cup\{2,4\}
  8. \{1,4\}\cup\{2,3\}
  9. \{1\}\cup\{2\}\cup\{3,4\}
  10. \{1\}\cup\{3\}\cup\{2,4\}
  11. \{1\}\cup\{4\}\cup\{2,3\}
  12. \{2\}\cup\{3\}\cup\{1,4\}
  13. \{2\}\cup\{4\}\cup\{1,3\}
  14. \{3\}\cup\{4\}\cup\{1,2\}
  15. \{1\}\cup\{2\}\cup\{3\}\cup\{4\}
What is S(4,1), S(4,2), S(4,3), S(4,4)?
S(4,1)=1
S(4,2)=7
S(4,3)=6
S(4,4)=1
Exercise 3 List the partitions of \{1,2,3\} and compute the numbers S(3,1), S(3,2), and S(3,3). There are 5. The list is given as follows:
  1. \{1,2,3\}
  2. \{1\}\cup\{2,3\}
  3. \{2\}\cup\{1,3\}
  4. \{3\}\cup\{1,2\}
  5. \{1\}\cup\{2\}\cup\{3\}
Therefore, S(3,1)=1, S(3,2)=3, and S(3,3)=1.
Exercise 4 Determine if the following permutations are even or odd:
  1. (1\;2\;3\;4)
  2. (5\;3\;7\;2\;4)
  3. (1\;2\;3\;4)^2
  4. (1\;2\;3)(3\;4)
  5. e (the identity permutation)
 (a) (1\;2\;3\;4)=(1\;4)(1\;3)(1\;2). Therefore, it is odd.
(b) (5\;3\;7\;2\;4)=(5\;4)(5\;2)(5\;7)(5\;3). Therefore, it is even.
(c) (1\;2\;3\;4)^2 = (1\;2\;3\;4)(1\;2\;3\;4) = (1\;3)(2\;4). Therefore, it is even.
(d) (1\;2\;3)(3\;4)=(1\;2\;3\;4). Therefore, it is odd.
(e) The identity e can written as a product of 0 transpositions, thus it is even.
Exercise 5 Is the composition of two even permutations even? Yes. Suppose \sigma=\tau_1\cdots \tau_{2n} and \sigma'=\tau_1'\cdots \tau'_{2m}, then \sigma\sigma'=\tau_1 \cdots \tau_{2n} \tau_1'\cdots \tau'_{2m} and thus it is the product of 2n+2m transpositions, which is even.
Exercise 6 Is the composition of two odd permutations odd? No. Suppose \sigma=\tau_1\cdots \tau_{2n+1} and \sigma'=\tau_1'\cdots \tau'_{2m+1}, then \sigma\sigma'=\tau_1 \cdots \tau_{2n+1} \tau_1'\cdots \tau'_{2m+1} and thus it is the product of 2n+1+2m+1=2(n+m+1) transpositions, which is even.