Homework 3
-
A 10-store building is to be painted with some 4 different colors such that each store is painted with one color. How many ways are there to paint the building in the following four scenarios:
- there are no restrictions, not every color needs to be used;
For each store, we have 4 possibilities and we have 1- stores, thus the result is \(4^{10}=1048576\) - any two adjacent stores must be painted with different colors, not every color needs to be used
For the first store, we have \(4\) possibilities, for the second one, we have \(3\) possibilities since the color must be different from the first
Thus...... for the tenth one, we have \(3\) possibilities.
Finally, using multiplication principle, the result is \(4\cdot 3^{9}=78732\) - all the colors must be used at least once;
Using Inclusive-Exclusive Principle
Let \(A=\) {all possibilities }, thus \(|A|=4^{10}\)
\(A_1=\) {possibilities of not using color 1}, thus \(|A_{1}|=3^{10}\)
\(A_2=\) {possibilities of not using color 2}, thus \(|A_{2}|=3^{10}\)
\(A_3=\) {possibilities of not using color 3}, thus \(|A_{3}|=3^{10}\)
\(A_{4}=\) {possibilities of not using color 4}, thus \(|A_{4}|=3^{10}\)
\(A_{1}\cap A_{2}=\){possibilities of not using 1 and 2}, thus \(|A_{1}\cap A_{2}|=2^{10}\)
....
\(A_1\cap A_2\cap A_3=\){possibilities of not using 1 and 2 and 3}, thus \(|A_{1}\cap A_{2}\cap A_{3}|=1^{10}\)
.....
Then \(|A\setminus(A_{1}\cup A_{2}\cup A_{3}\cup A_{4})|\) is the possibilities that all the colors must be used at least once
And we know \(\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 \(|A\setminus(A_{1}\cup A_{2}\cup A_{3}\cup A_{4})|=\left|A\right|-4\left|A_{1}\right |+6\left|A_{1}\cap A_{2}\right|-4\left|A_{1}\cap A_{2}\cap A_{3}\right|\)
\(=4^{10}– 4\cdot 3^{10}+ 6\cdot2^{10}– 4=818520\) - there are exactly 4 stores painted with color 1, 3 stores painted with color 2, 2 stores painted with color 3, and 1 store painted with color 4. 4 stores with color 1 → \(\binom{10}{4}\) 3 stores with color 2 → \(\binom{6}{3}\) 2 stores with color 3 → \(\binom{3}{2}\) 1 stores with color 4 → \(\binom{1}{1}\)
Then we use multiplicative principle, the result is \(\binom{10}{4}\binom{6}{3}\binom{3}{2}\binom{1}{1}=12600\)
-
Find the number of integer solutions to the equation \(x_1 + x_2 + x_3 + x_4 = 30\) in each of the following cases:
- \(x_i \geq 0\) for each \(i = 1,2,3,4\);
By theorem: We have \(n\) boxes, \(k\) identical balls without restrictions, then the number of ways is \(\binom{n+k-1}{n-1}\)
Here \(n=4,k=30\), thus we have \(\binom{33}{3}\) ways - \(2 \leq x_1 \leq 7\) and \(x_i \geq 0\) for each \(i = 2,3,4\);
\(x_1 \geq 2 \Rightarrow (x_1 - 2) \geq 0\), then we have \(x_1 - 2 + x_2 + x_3 + x_4 = 28\)
Use theorem there are \(\binom{31}{3}\) ways
\(x_1 > 7 \Rightarrow x_1 \geq 8\), then \(x_1 - 8 \geq 0 \Rightarrow x_1 - 8 + x_2 + x_3 + x_4 = 22\)
Use theorem there are \(\binom{25}{3}\) ways
Thus, the result is \(\binom{31}{3} - \binom{25}{3}\) - \(x_1 \geq -5, x_2 \geq -1, x_3 \geq 1,\) and \(x_4 \geq 2\).
\(x_1 + 5 \geq 0, \quad x_2 + 1 \geq 0, \quad x_3 - 1 \geq 0, \quad x_4 - 2 \geq 0\)
\(\Rightarrow x_{1}+5+x_{2}+1+x_{3}-1+x_{4}-2=33\)Use theorem there are \(\binom{36}{3}\) ways
Thus the result is \(\binom{36}{3}\)
-
Show that for any \(n \in \mathbb{N}\), the number \(\frac{(n^{2})!}{(n!)^{n}}\) is an integer.
Consider multinomial coefficients: \(\frac{n^{\prime}!}{k_{1}!k_{2}!...k_{n}!}=\binom{n^{\prime}}{k_1,\ldots,k_{n}}\)
Let \(n'=n^{2}\) and \(k_1=k_2=...=k_n=n!\)
Thus we have \(\frac{(n^{2})!}{(n!)^{n}}=\binom{n^2}{n!,\ldots,n!}\) and we know multinomial coefficients is the number of ways to arrange balls into boxes where \(n\) boxes and \(n\) balls and \(m\) different types of Balls and all the balls of the same type are identical
Thus it must be a integer.