Skip to content

3.26 Inclusive-Exclusive Principle

  1. 60% of students in a class read JoAM, 50% read Science, 50% read Nature, 30% read both JoAM and Science, 20% read both Science and Nature, 40% read both JoAM and Nature, 10% read all three journals.

    That is \(A_{0}=100\%,A_{1}=60\%,A_{2}=50\%,A_{3}=50\%,A_{1}\cap A_{2}=30\%,A_{2}\cap A_{3} =20\%,A_{1}\cap A_{3}=40\%,A_{1}\cap A_{2}\cap A_{3}=10\%\)​

    • What is the percentage of students who read no journals?

    Use formula \(\left|A\setminus(A_{1}\cup\dots\cup A_{n})\right|=\sum\limits_{J\subseteq\{1,\dots,n\}} (-1)^{\left|J\right|}\left|\bigcap_{j\in J}A_{j}\right|\)

    \(=100\%\left(J=\emptyset\right)-60\%\left(J=\left\lbrace1\right\rbrace\right)-50\% \left(J=\left\lbrace2\right\rbrace\right)-50\%\left(J=\left\lbrace3\right\rbrace\right )+30\%\left(J=\left\lbrace1,2\right\rbrace\right)+10\%\left(J=\left\lbrace2,3\right \rbrace\right)+40\%\left(J=\left\lbrace1,3\right\rbrace\right)-10\%\left(J=\left\lbrace 1,2,3\right\rbrace\right)\)​

    \(=20\%\)​ * What is the percentage of students who read at least two journals?

    Let \(B_1=A_1\cap A_2,B_2=A_2\cap A_3,B_3=A_1\cap A_3\)​

    Thus \(=B_{1}\cup B_{2}\cup B_{3}=30\%\left(J=\left\lbrace1\right\rbrace\right)+20\%\left (J=\left\lbrace2\right\rbrace\right)+40\%\left(J=\left\lbrace3\right\rbrace\right )-10\%\left(J=\left\lbrace1,2\right\rbrace\right)-10\%\left(J=\left\lbrace2,3\right \rbrace\right)-10\%\left(J=\left\lbrace1,3\right\rbrace\right)+10\%\left(J=\left\lbrace 1,2,3\right\rbrace\right)\)​

    \(=70\%\)​ * What is the percentage of students who read exactly two journals?

    \(=\) at least 2- at least 3 \(=70\%-10\%=60\%\)​

  2. Maria received \(n\) letters, each in an envelope. She extracted all of them, and randomly put each letter inside some envelope. What is the number of possible distributions in which no letter ends up in its own envelope?

    Let \(A=\left\lbrace\text{distributions of letters in envelopes}\right\rbrace\) and we know \(|A|=n!\)​

    But \(A\supset A_{i}=\left\lbrace\text{distributions in which letter i ends up in envelope i}\right\rbrace\) for \(i=1,...,n\)​

    Then \(A\setminus(A_{1}\cup...\cup A_{n})=\left\lbrace\text{distributions such that no letter in its own envelope}\right\rbrace\)

    Then use \(\left|A\setminus(A_{1}\cup\dots\cup A_{n})\right|=\sum\limits_{J\subseteq\{1,\dots,n\}} (-1)^{\left|J\right|}\left|\bigcap_{j\in J}A_{j}\right|\)

    Then the result is \(n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\ldots+\left(-1\right)^{n}\binom{n}{n}\left (n-n\right)!\)

    where----------\(|J|=0\), \(|J|=1\),-------\(|J|=2\)-----------------\(|J|=n\)​

    \(=\sum_{j=0}^{n}\left(-1\right)^{j}\binom{n}{j}\left(n-j\right)!=\sum_{j=0}^{n}\left (-1\right)^{j}\frac{n!}{j!}=n!\left(\sum_{j=0}^{n}\frac{\left(-1\right)^{j}}{j!}\right )\)​

    Here in the parenthesis(let's call its \(P\)) it is the probability that no letter ends up in its own envelop \(\lim_{n\to\infty}P=e^{-1}\)

  3. Find the number of integers less than 1000 which are not divisible by 5 nor by 7, but are divisible by 3.

    (divisible by 3) (not divisible by 5) (not divisible by 7)

    Let \(A=\{\text{divisible by 3}\}\) and \(|A|=333\), \(A_{1}=\{\text{divisible by 3 and 5}\}\) and \(|A_{1}|=\lfloor\frac{999}{15}\rfloor=66\)

    \(A_{2}=\{\text{divisible by 3 and 7}\}\) and \(|A_{2}|=\lfloor\frac{999}{27}\rfloor=47\)

    \(A_{1}\cap A_{2}=\{\text{divisible by 3, 5 and 7}\}=\lfloor\frac{999}{105}\rfloor =9\)​

    The result is \(333-66-47+9=229\)​

  4. The Euler totient function \(\phi\) : \(\mathbb{N} \to \mathbb{N}\) is defined as follows: for the number \(n\), its value \(\phi(n)\) is the number of elements of the set \(\{ k \in \mathbb{N} \mid k \leq n, \gcd(n, k) = 1 \}\)

    • Prove that if \(n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}\) with \(p_1, \dots, p_k\) are distinct prime numbers, and \(\alpha_1, \dots, \alpha_k \in \mathbb{N}\)​, we have \(\phi(n) = n \prod_{i=1}^{k}\left( 1 - \frac{1}{p_{i}}\right)\)

    For some \(a\), if \(\gcd(a,n)\neq 1\), then \(a\) is divisible by at least one \(p_i\) for some \(i=1,...,k\)

    Thus Let \(A=\{\text{divisible by exact zero factor}\}\), then \(|A|=n\)

    \(A_{1}=\{\text{divisible by exact one factor}\}\), then \(|A_{1}|=\sum_{1\leq p_{i}\leq m}\frac{n}{p_{i}}\)

    .....

    Thus the idea is \(n\) - divisible by exact one factor - divisible by exact two factors -...- divisible by exact m factors

    \(n - \sum_{j=1}^{m} \frac{n}{p_i} + \sum_{1 \leq i_1 < i_2 \leq m} \frac{n}{p_{i_1} p_{i_2}} - \sum_{1 \leq i_1 < i_2 < i_3 \leq m} \frac{n}{p_{i_1} p_{i_2} p_{i_3}} + \dots\)

    \(J = \emptyset, \quad \#J = 1\)

    \(n \left( 1 - \sum \frac{1}{p_{i_1}} - \sum \frac{1}{p_{i_1} p_{i_2}} + \sum \frac{1}{p_{i_1} p_{i_2} p_{i_3}} + \dots \right)\) \(= n \prod_{i=1}^{m} \left(1 - \frac{1}{p_i} \right)\) * Prove that if for \((m, n) \in \mathbb{N}\) we have \(\gcd(m, n) = 1\), then \(\phi(mn) = \phi(m) \phi(n)\)

    Since \(\gcd(m,n)=1\), then \(mn=m\times n\) is the only way

    Then \(\phi(mn)=mn\left(1-\frac{1}{m}\right)\left(1-\frac{1}{n}\right)=mn\left(1+\frac{1}{mn} -\frac{1}{m}-\frac{1}{n}\right)=mn+1-n-m\)

    \(\phi(m)\phi(n)=m\left(1-\frac{1}{m}\right)n\left(1-\frac{1}{n}\right)=\left(m-1\right )\left(n-1\right)=mn-m-n+1\)​

    Thus they are equal

  5. Show that for any \(n \geq 2\) we have \(\sum_{k=0}^{n}(-1)^{k} \binom{n}{k}(n-k)^{n} = n!\)

    \(\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k)^{n}= n!\iff \sum_{j=0}^{n}(-1)^{j}\binom {n}{j}(n-j)^{n}= n!\)

    Thus for Stirling number \(S(k,n)=\frac{1}{n!}\cdot\sum_{j=0}^{n}\left(-1\right)^{j}\binom{n}{j}\left(n-j\right )^{k}\)

    Let \(k=n\), then \(S(n,n)=1=\frac{1}{n!}\cdot\sum_{j=0}^{n}\left(-1\right)^{j}\binom{n}{j}\left(n-j \right)^{n}\)​

    Thus \(\sum_{j=0}^{n}(-1)^{j}\binom{n}{j}(n-j)^{n}=n!\)

‍