Homework 4
-
Find the number of 7-digit numbers (no 0 in any position) such that they do not contain the sequence of adjacent digits 454 in this particular order.
Let's \(A_{1}=\{\text{the 1st, 2nd, 3rd digits are 454}\}\), \(A_{2}=\{\text{the 2nd, 3rd, 4th digits are 454}\}\)
\(A_{3}=\{\text{the 3rd, 4th, 5th digits are 454}\}\), \(A_{4}=\{\text{the 4th, 5th, 6th digits are 454}\}\)
\(A_{5}=\{\text{the 5th, 6th, 7th digits are 454}\}\)
Then we want \(\left|A\setminus(A_{1}\cup\ldots\cup A_{5})\right|=\sum\limits_{J\subseteq\{1,\ldots,5\}} (-1)^{\left|J\right|}\left|\bigcap_{j\in J}A_{j}\right|=\left|A\right|-\left|A_{1} \right|-\left|A_{2}\right|-\left|A_{3}\right|-\left|A_{4}\right|-\left|A_{5}\right |+\left|A_{1}\cap A_{2}\right|+\left|A_{1}\cap A_{3}\right|+\left|A_{1}\cap A_{4} \right|+\left|A_{1}\cap A_{5}\right|+\left|A_{2}\cap A_{3}\right|+\left|A_{2}\cap A_{4}\right|+\left|A_{2}\cap A_{5}\right|+\left|A_{3}\cap A_{4}\right|+\left|A_{3} \cap A_{5}\right|+\left|A_{4}\cap A_{5}\right|-\left|A_{1}\cap A_{2}\cap A_{3}\right |-\left|A_{1}\cap A_{2}\cap A_{4}\right|-\left|A_{1}\cap A_{2}\cap A_{5}\right|-\left |A_{1}\cap A_{3}\cap A_{4}\right|-\left|A_{1}\cap A_{3}\cap A_{5}\right|-\left|A_{1} \cap A_{4}\cap A_{5}\right|+\left|A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\right|+\left |A_{1}\cap A_{2}\cap A_{3}\cap A_{5}\right|+\left|A_{1}\cap A_{2}\cap A_{4}\cap A _{5}\right|+\left|A_{1}\cap A_{3}\cap A_{4}\cap A_{5}\right|+\left|A_{2}\cap A_{3} \cap A_{4}\cap A_{5}\right|-\left|A_{1}\cap A_{2}\cap A_{3}\cap A_{4}\cap A_{5}\right |\)
\(=9^{7}-5\cdot9^{4}+3\cdot9+3\cdot9^{2}-1=4750433\)
-
Let \(A_1, \dots, A_n\) be finite sets. Prove that the number of elements \(x \in A_{1}\cap \dots \cap A_{k}\) with the following property:
- \(x\) belongs to the intersection \(A_{i_1}\cap \dots \cap A_{i_{n-2}}\) of some \(n - 2\) of these sets,
- but not to an intersection of any \(n - 1\) of these sets,
is given by the following formula: \(\sum\limits_{J \subset \{1, \dots, n\}, |J| = n-2}\# \left( \bigcap\limits_{j \in J}A_{j}\right ) - (n-1) \sum\limits_{J \subset \{1, \dots, n\}, |J| = n-1}\# \left( \bigcap\limits_{j \in J}A_{j}\right) + \binom{n}{2}\# \left( \bigcap\limits _{j \in \{1, \dots, n\}}A_{j}\right)\)
Proof
First, we fixed the \(n - 2\) intersection set, consider one n-2 intersection set- \(A_{1}\cap\dots\cap A_{n-2}\)
Then since the property, we know we need to find how many elements do \(A_{1}\cap\dots\cap A_{n-2}\) exactly have without any other intersection
By inclusive-exclusive principle, we know \(|\text{the number of }A_{1}\cap\dots\cap A_{n-2}\text{ without any other intersection} |=\left|A_{1}\cap\dots\cap A_{n-2}\right|-\left|A_{1}\cap\dots\cap A_{n-1}\right| -\left|A_{1}\cap\dots\cap A_{n-2}\cap A_{n}\right|+\left|A_{1}\cap\dots\cap A_{n} \right|\)
Then we have \(\binom{n}{n-2}\) such n-2 intersection set. And for all n-2 intersection set, the number is \(\sum\limits_{J\subset\{1,\dots,n\},|J|=n-2}\#\left(\bigcap\limits_{j\in J}A_{j}\right )\)
By above argument, every n-2 intersection set need to be added \(\left|A_{1}\cap\dots\cap A_{n} \right|\)
Then for \(\sum\limits_{J\subset\{1,\dots,n\},|J|=n-2}\#\left(\bigcap\limits_{j\in J}A_{j}\right)\), we need to add \(\binom{n}{n-2}\#\left(\bigcap\limits_{j\in\{1,\dots,n\}}A_{j}\right)\) such set since we have \(\binom{n}{n-2}\) such n-2 intersection set
Then we only to determine how many times do a specific n-1 intersection set need to be subtracted. (Then the same situation for any other n-1 intersection set)
For a n-1 intersection set: \(A_{1}\cap\dots\cap A_{n-1}\). It will be subtracted iff it contains that n-2 intersection sets. If not, contradicts to property
Then the times for a n-1 intersection set: \(A_{1}\cap\dots\cap A_{n-1}\) to be subtracted is \(\binom{n-1}{n-2}\)
Then the same situation for any other \(n-1\) intersection set
Thus totally we need to subtract \(\binom{n-1}{n-2}\sum\limits_{J\subset\{1,\dots,n\},|J|=n-1}\#\left(\bigcap\limits _{j\in J}A_{j}\right)\) from \(\sum\limits_{J\subset\{1,\dots,n\},|J|=n-2}\#\left(\bigcap\limits_{j\in J}A_{j}\right)\)
Thus the final results is \(\sum\limits_{J\subset\{1,\dots,n\},|J|=n-2}\#\left(\bigcap\limits_{j\in J}A_{j}\right )-\binom{n-1}{n-2}\sum\limits_{J\subset\{1,\dots,n\},|J|=n-1}\#\left(\bigcap\limits _{j\in J}A_{j}\right)+\binom{n}{n-2}\#\left(\bigcap\limits_{j\in\{1,\dots,n\}}A_{j} \right)\)
This is equivalent to \(\sum\limits_{J \subset \{1, \dots, n\}, |J| = n-2}\# \left( \bigcap\limits_{j \in J}A_{j}\right ) - (n-1) \sum\limits_{J \subset \{1, \dots, n\}, |J| = n-1}\# \left( \bigcap\limits_{j \in J}A_{j}\right) + \binom{n}{2}\# \left( \bigcap\limits _{j \in \{1, \dots, n\}}A_{j}\right)\)
-
Prove that for any \(n \in \mathbb{N}\): \(\sum\limits_{d | n}\phi(d) = n,\)where the sum ranges over all the positive divisors of \(n\), and \(\phi: \mathbb{N} \to \mathbb{N}\) is Euler’s totient function.
Hint: Define the right-hand part by \(\psi(n)\). Prove that for \(\gcd(m, n) = 1\), we have \(\psi(nm) = \psi(n) \psi(m)\), and then prove that for any prime \(p\) and any natural number \(d\), we have \(\psi(p^d) = p^d\).
Proof
Define \(\psi(n)=\sum\limits_{d | n}\phi(d)\)
Assume \(\gcd(m, n) = 1\), then \(\psi(nm)=\sum\limits_{d|mn}\phi(d)=\sum\limits_{d|m\text{ or }d\mid n}\phi(d)=\sum \limits_{d|m}\phi(d)\sum\limits_{d|n}\phi(d)=\psi(m)\psi(n)\)
We know 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 any prime \(p\) and any natural number \(d\), \(\psi(p^{d})=\sum\limits_{d|p^{d}}\phi(d)=\phi(1)+\phi(p)+\phi(p^{2})+\cdots+\phi (p^{d})=1+p\left(1-\frac{1}{p}\right)+p^{2}\left(1-\frac{1}{p}\right)+\ldots+p^{d} \left(1-\frac{1}{p}\right)\)
\(=1+(1-\frac{1}{p})\frac{p\left(1-p^{d}\right)}{1-p}=1+\left(p-1\right)\frac{1-p^{d}}{1-p} =1+p^{d}-1=p^{d}\)
Then assume \(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}\)
Then \(\psi(n)=\psi\left(p_{1}^{\alpha_1}\cdots p_{k}^{\alpha_{k}}\right)=\psi(p_{1}^{\alpha_1} )\cdot\psi(p_{2}^{\alpha_2})\cdot\ldots\cdot\psi(p_{k}^{\alpha_{k}})=p_{1}^{\alpha_1} \cdots p_{k}^{\alpha_{k}}=n\)