Discrete-math 19

Inclusion-Exclusion Principle #definition

\begin{matrix} Let A_{1}, \dots, A_{n} be finite sets \\ Then | ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} (- 1)^{k - 1} \sum_{\begin{matrix} B \subseteq [n] \\ | B | = k \end{matrix}} | ⋂_{j \in B} A_{j} | = \\ = \sum_{k = 1}^{n} (- 1)^{k - 1} \sum_{1 \leq i_{1} < i_{2} < \dots < i_{k} \leq n} | A_{i_{1}} \cap A_{i_{2}} \cap \dots \cap A_{i_{k}} | \\ Proof: \\ Let x \in U \\ Let m be a number of sets which contain x \\ Let m = 0 \\ ⟹ {\begin{matrix} x \notin ⋃_{i = 1}^{n} A_{i} \\ \forall k \in [n] : \forall B \subseteq [n], | B | = k : x \notin ⋂_{j \in B} A_{j} \end{matrix} \\ ⟹ x is counted zero times on both sides \\ Let m > 0 \\ x \in A_{i_{1}}, A_{i_{2}}, \dots, A_{i_{m}} \\ Let D = {i \in [n] | x \in A_{i}} \\ | D | = m \\ x \in ⋃_{i = 1}^{n} A_{i} ⟹ x is counted once on the left side \\ \forall B ⊈ D : x \notin ⋂_{j \in B} A_{j} ⟹ \forall B ⊈ D : x is counted zero times on the right side \\ Total contribution of x to the sum on the right side: \\ \sum_{k = 1}^{m} (- 1)^{k - 1} \sum_{\begin{matrix} B \subseteq D \\ | B | = k \end{matrix}} 1 = \sum_{k = 1}^{m} (- 1)^{k - 1} (\binom{m}{k}) = - \sum_{k = 1}^{m} (- 1)^{k} (\binom{m}{k}) = 1 - \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) = \\ = 1 - 0 = 1 \\ ⟹ \forall x \in U : x is counted the same number of times on both sides \\ Proved \end{matrix}

\begin{matrix} If \forall k \in [n] : sizes of intersection of any k sets are equal to α_{k} \\ Then | ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} (- 1)^{k - 1} \sum_{\begin{matrix} B \subseteq [n] \\ | B | = k \end{matrix}} α_{k} = \sum_{k = 1}^{n} (- 1)^{k - 1} α_{k} (\binom{n}{k}) \end{matrix}

\begin{matrix} How many numbers from [1000] can be divided by at least one of numbers: 2, 3, 5 ? \\ Solution: \\ Let A_{2} = {n \in [1000] | 2 ∣ n} \\ Let A_{3} = {n \in [1000] | 3 ∣ n} \\ Let A_{5} = {n \in [1000] | 5 ∣ n} \\ | A_{2} \cup A_{3} \cup A_{5} | = \underset{k = 1}{\underset{⏟}{| A_{2} | + | A_{3} | + | A_{5} |}} - \underset{k = 2}{\underset{⏟}{(| A_{2} \cap A_{3} | + | A_{2} \cap A_{5} | + | A_{3} \cap A_{5} |)}} + \\ + \underset{k = 3}{\underset{⏟}{| A_{2} \cap A_{3} \cap A_{5} |}} = \\ | A_{2} | = ⌊ \frac{1000}{2} ⌋ = 500 \\ | A_{3} | = ⌊ \frac{1000}{3} ⌋ = 333 \\ | A_{5} | = ⌊ \frac{1000}{5} ⌋ = 200 \\ | A_{2} \cap A_{3} | = ⌊ \frac{1000}{2 * 3} ⌋ = 166 \\ | A_{2} \cap A_{5} | = ⌊ \frac{1000}{2 * 5} ⌋ = 100 \\ | A_{3} \cap A_{5} | = ⌊ \frac{1000}{3 * 5} ⌋ = 66 \\ | A_{2} \cap A_{3} \cap A_{5} | = ⌊ \frac{1000}{2 * 3 * 5} ⌋ = 33 \\ ⟹ | A_{2} \cup A_{3} \cup A_{5} | = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734 \end{matrix}

\begin{matrix} Let n, m \in N \\ What is the number of surjective functions f : [n] \to [m] ? \\ Solution: \\ Let m > n \\ ⟹ | [n] | < | [m] | ⟹ Number of surjective functions is zero \\ Let m \leq n \\ | [m]^{[n]} | = m^{n} \\ Let’s count the number of functions that are not surjective \\ Let \forall i \in [m] : A_{i} = {f : [n] \to [m] | i \notin I m (f)} \\ f (1) \in [m] ∖ {i} \\ f (2) \in [m] ∖ {i} \\ \dots \\ f (n) \in [m] ∖ {i} \\ ⟹ \forall i \in [m] : | A_{i} | = (m - 1)^{n} \\ \forall 1 \leq i_{1} < i_{2} < \dots < i_{k} \leq m : | \underset{f : [n] \to [m] : i_{1}, i_{2}, \dots, i_{k} \notin I m (f) ⟹ | I m (f) | = m - k}{\underset{⏟}{A_{i_{1}} \cap A_{i_{2}} \cap \dots \cap A_{i_{k}}}} | = (m - k)^{n} \\ ⟹ | ⋃_{i \in [m]} A_{i} | = \sum_{k = 1}^{m} (- 1)^{k - 1} (m - k)^{n} (\binom{m}{k}) \\ Number of surjective functions is equal to: \\ m^{n} - | ⋃_{i \in [m]} A_{i} | = m^{n} - \sum_{k = 1}^{m} (- 1)^{k - 1} (m - k)^{n} (\binom{m}{k}) \end{matrix}

\begin{matrix} If there are n pigeons and n - 1 pigeon holes \\ then there are at least 2 pigeons in one of the holes \\ Proof: \\ \dots \end{matrix}