Discrete-math 10

\begin{matrix} Prove: (\binom{n}{k}) \cdot (\binom{k}{m}) = (\binom{n}{m}) \cdot (\binom{n - m}{k - m}) \\ Proof (algebraic): \\ (\binom{n}{k}) \cdot (\binom{k}{m}) = \frac{n!}{(n - k)! k!} \cdot \frac{k!}{(k - m)! m!} = \frac{n!}{(n - k)! (k - m)! m!} \\ (\binom{n}{m}) \cdot (\binom{n - m}{k - m}) = \frac{n!}{(n - m)! m!} \cdot \frac{(n - m)!}{(n - k)! (k - m)!} = \frac{n!}{(n - k)! (k - m)! m!} \\ Proof (combinatorial): \\ How many ways we can choose k workers out of n people such that \\ m of them are managers? \\ Let us first choose m managers out of n people \\ and then choose k - m people out of n - k people left, which is: \\ (\binom{n}{m}) \cdot (\binom{n - m}{k - m}) \\ Now let us first choose k people out of n people \\ and then choose m out of these k people to be managers, which is: \\ (\binom{n}{k}) \cdot (\binom{k}{m}) \end{matrix}

Fermat's identity

\begin{matrix} Let n, k \in N, k < n \\ \sum_{i = k}^{n} (\binom{i}{k}) = (\binom{n + 1}{k + 1}) \\ Proof: \\ How many ways there are to choose k + 1 people from the group of n + 1 people? \\ (\binom{n + 1}{k + 1}) \\ Now let’s pick the i ’th tallest person \\ Let’s then pick k people who are shorter than this person \\ Number of ways to pick them is: \sum_{i = k + 1}^{n + 1} (\binom{i - 1}{k}) \underset{j = k = i - 1}{\underset{⏟}{=}} \sum_{j = k}^{n} (\binom{j}{k}) \\ This way, we have chosen some k + 1 people \\ ⟹ \sum_{i = k}^{n} (\binom{i}{k}) = (\binom{n + 1}{k + 1}) \end{matrix}

\begin{matrix} \sum_{i = 0}^{n - 1} (\binom{n + i}{i}) = (\binom{2 n}{n - 1}) \\ Proof: \\ \sum_{i = 0}^{n - 1} (\binom{n + i}{n}) = (\binom{2 n}{n + 1}) \\ Let k = i + n \\ \sum_{k = n}^{2 n - 1} (\binom{k}{n}) = (\binom{2 n - 1 + 1}{n + 1}) = (\binom{2 n}{n + 1}) \end{matrix}

\begin{matrix} Let n \in N \cup {0} \\ S_{r} = {(x_{1}, x_{2}, \dots, x_{r}) | \sum_{i = 1}^{r} x_{i} = n} \\ \sum_{r = 1}^{n} | S_{r} | = \sum_{r = 1}^{n} (\binom{r + n - 1}{r - 1}) = \sum_{k = 0}^{n - 1} (\binom{k + n}{k}) = (\binom{2 n}{k - 1}) = (\binom{2 n}{n - 1}) \end{matrix}

\begin{matrix} How many strings can we write down with letters of word "mississippi"? \\ Solution: \\ 4 positions for "i", 4 positions for "s", 2 positions for "p", 1 position for "m" \\ (\binom{11}{4}) \cdot (\binom{7}{4}) \cdot (\binom{3}{2}) \cdot (\binom{1}{1}) \\ Multinomial is a "multiple choice" binomial: \\ (\binom{11}{4, 4, 2, 1}) = (\binom{11}{4}) \cdot (\binom{7}{4}) \cdot (\binom{3}{2}) \cdot (\binom{1}{1}) = \frac{11!}{7! 4!} \cdot \frac{7!}{3! 4!} \cdot \frac{3!}{2! 1!} = \frac{11!}{4! 4! 2! 1!} \\ (\binom{n}{n_{1}, \dots, n_{k}}) = \frac{n!}{n_{1}! n_{2}! \dots n_{k}!} = \frac{n!}{\prod_{i = 1}^{k} n_{i}!} \end{matrix}

\begin{matrix} 2 pizzas in size S, M, L or XL \\ 8 toppings \\ Solution: \\ Number of different pizzas: \\ 4 \cdot 2^{8} = 2^{10} \\ Number of ways to choose 2 pizzas out of all possible pizzas is: \\ (\binom{2^{10} + 2 - 1}{2}) = (\binom{2^{10} + 1}{2}) \end{matrix}

\begin{matrix} How many polinomials of degree 6 there are such that: \\ All coefficients are non-negative integers, p (1) = 30, p (- 1) = 12 \\ p (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + a_{4} x^{4} + a_{5} x^{5} + a_{6} x^{6} \\ p (1) = a_{0} + a_{1} + a_{2} + a_{3} + a_{4} + a_{5} + a_{6} = 30 \\ p (- 1) = a_{0} - a_{1} + a_{2} - a_{3} + a_{4} - a_{5} + a_{6} = 12 \\ ⟹ {\begin{matrix} a_{0} + a_{1} + a_{2} + a_{3} + a_{4} + a_{5} + a_{6} = 30 \\ a_{1} + a_{3} + a_{5} = 9 \end{matrix} ⟹ {\begin{matrix} a_{0} + a_{2} + a_{4} + a_{6} = 21 \\ a_{1} + a_{3} + a_{5} = 9 \end{matrix} \\ (\binom{4 + 21 - 1}{21}) \cdot (\binom{3 + 9 - 1}{9}) = (\binom{24}{21}) \cdot (\binom{11}{9}) \end{matrix}

\begin{matrix} Let n \geq 2 \\ S = {1, \dots, n + 1} \\ T = {(x, y, z) | {\begin{matrix} x < z \\ y < z \\ x, y, z \in S \end{matrix}} \\ | T | = \sum_{k = 1}^{n} k^{2} = (\binom{n + 1}{2}) + 2 \cdot (\binom{n + 1}{3}) \\ Proof: \\ Let z \in S \\ Number of ways to choose x, y < z is: \\ (z - 1) (z - 1) \\ ⟹ \sum_{z = 1}^{n + 1} (z - 1)^{2} = \sum_{k = 1}^{n} k^{2} \\ Let x = y \\ We need to choose two numbers - x, z \\ ⟹ (\binom{n + 1}{2}) \\ Let x \neq y \\ We need to choose three numbers - x, y, z \\ x < y and y < x are symmetrical and different \\ ⟹ 2 \cdot (\binom{n + 1}{3}) \\ ⟹ (\binom{n + 1}{2}) + 2 \cdot (\binom{n + 1}{3}) \end{matrix}

\begin{matrix} Let n, m, r \in N \\ r \leq m \leq n \\ \sum_{i = 0}^{r} (\binom{m}{i}) \cdot (\binom{n}{r - i}) = (\binom{m + n}{r}) \\ Proof: \\ Let us choose r people from m boys and n girls: \\ (\binom{m + n}{r}) \\ Let us now choose i boys first and then choose the girls left \\ A_{i} = {ways to choose i from m boys and r - i from n girls} \\ | A_{i} | = (\binom{m}{i}) \cdot (\binom{n}{r - i}) \\ i \neq j ⟹ A_{i} \cap A_{j} = \emptyset \\ | ⋃_{i = 0}^{r} A_{i} | = \sum_{i = 0}^{r} | A_{i} | = \sum_{i = 0}^{r} (\binom{m}{i}) \cdot (\binom{n}{r - i}) \end{matrix}