Discrete-math 10

1

\begin{matrix} A person wants to choose 6 cookies from a tray containing at least 6 cookies \\ of each of the following types: chocolate chip, wheat, and peanut butter. \\ How many ways are there to choose these cookies? \\ Solution: \\ How many ways to choose one cookie is there? 3 \\ There are at least 6 cookies of each type, so the number of ways \\ doesn’t change after choosing 1,2,3,4 or 5 cookies, so it is always 3 \\ Order is not important and repetitions are allowed \\ ⟹ (\binom{6 + 3 - 1}{3 - 1}) = (\binom{8}{2}) \end{matrix}

2

\begin{matrix} How many ways are there to arrange number {1, 2, \dots, 9} such that \\ no multiple of 3 is adjacent to another multiple of 3? \\ Solution: \\ Let us first arrange numbers that are not multiples of 3 - 1, 2, 4, 5, 7, 8 \\ There are six of them, which means there are \frac{6!}{(6 - 6)!} = 6! ways to arrange them \\ Now we have 6 numbers arranged and we need to choose 3 positions \\ among them for multiples of 3 \\ There are 7 positions: 5 between chosen numbers and 2 on the sides \\ Each two multiples of 3 will then be separated by at least 1 other number \\ Number of ways to choose 3 out of these 7 positions is \frac{7!}{(7 - 3)!} = \frac{7!}{4!} \\ The final answer is: \frac{7! 6!}{4!} = 151200 \end{matrix}

3

\begin{matrix} There are 6 identical balls and 3 distinct boxes \end{matrix}

3a

\begin{matrix} In how many ways can 6 balls be arranged in the 3 boxes? \\ Solution: \\ Each box can be represented as a variable in the equation: \\ x_{1} + x_{2} + x_{3} = 6, \forall i \in [1, 3] : x_{i} \geq 0 \\ Number of different solutions is: (\binom{6 + 3 - 1}{3 - 1}) = (\binom{8}{2}) \end{matrix}

3b

\begin{matrix} In how many ways can 6 balls be arranged in the 3 boxes \\ such that each box contains at least one ball? \\ Solution: \\ x_{1} + x_{2} + x_{3} = 6, \forall i \in [1, 3] : x_{i} \geq 1 \\ ⟹ (x_{1} - 1) + (x_{2} - 1) + (x_{3} - 1) = 3, \forall i \in [1, 3] : x_{i} - 1 \geq 0 \\ Number of different solutions is: (\binom{3 + 3 - 1}{3 - 1}) = (\binom{5}{2}) \end{matrix}

3c

\begin{matrix} Now there are 7 balls. In how many ways can they be arranged in the 3 boxes \\ such that no box contains more than 4 balls \\ Solution: \\ x_{1} + x_{2} + x_{3} = 7, \forall i \in [1, 3] : 0 \leq x_{i} \leq 4 \\ Let’s solve an "inverse" problem: \\ x_{1} + x_{2} + x_{3} = 7, x_{1} \geq 5 \lor x_{2} \geq 5 \lor x_{3} \geq 5 \\ Note that only one of the variables can be greater than 4 at the same time \\ ⟹ There are 3 different problems with the same number of solutions: \\ (x_{i} - 5) + x_{j} + x_{k} = 2, x_{i} - 5, x_{j}, x_{k} \geq 0 \\ ⟹ 3 \cdot (\binom{2 + 3 - 1}{3 - 1}) = 3 \cdot (\binom{4}{2}) \\ ⟹ Number of solutions to the initial problem is: \\ (\binom{3 + 7 - 1}{3 - 1}) - 3 \cdot (\binom{4}{2}) = (\binom{9}{2}) - 3 \cdot (\binom{4}{2}) \end{matrix}

3d

\begin{matrix} Now there are 8 balls, 4 boxes labeled A, B, C, D \\ How many ways to arrange the balls there are such that: \\ 1. Each box contains at least 1 ball \\ 2. Each box contains no more than 4 balls \\ 3. Boxes A and B together contain exactly 5 balls \\ Solution: \\ Let x_{1}, x_{2}, x_{3}, x_{4} correspond to boxes A, B, C, D accordingly \\ ⟹ {\begin{matrix} x_{1} + x_{2} + x_{3} + x_{4} = 8 \\ \forall i \in [1, 4] : 1 \leq x_{i} \leq 4 \\ x_{1} + x_{2} = 5 \end{matrix} ⟹ {\begin{matrix} x_{1} + x_{2} = 5 \\ x_{3} + x_{4} = 3 \\ \forall i \in [1, 4] : 1 \leq x_{i} \leq 4 \end{matrix} \\ x_{1} + x_{2} = 5, x_{1}, x_{2} \geq 1 \\ ⟹ There are no solutions where x_{1} or x_{2} are greater than 4 \\ ⟹ (x_{1} - 1) + (x_{2} - 1) = 3, (x_{1} - 1), (x_{2} - 1) \geq 0 ⟹ (\binom{3 + 2 - 1}{2 - 1}) = (\binom{4}{1}) \\ x_{3} + x_{4} = 3, x_{3}, x_{4} \geq 1 \\ ⟹ There are no solutions where x_{3} or x_{4} are greater than 4 \\ ⟹ (x_{3} - 1) + (x_{4} - 1) = 1, (x_{3} - 1), (x_{4} - 1) \geq 0 ⟹ (\binom{1 + 2 - 1}{2 - 1}) = (\binom{2}{1}) \\ ⟹ The final answer is (\binom{4}{1}) \cdot (\binom{2}{1}) \end{matrix}

4

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

5

\begin{matrix} Let n \in N \\ Prove algebraically and combinatorially: \sum_{k = 1}^{n} k \cdot k! = (n + 1)! - 1 \\ Proof (algebraic): \\ (n + 1)! - 1 = (n + 1) n! - 1 = n \cdot n! + n! - 1 \\ ⟹ \sum_{k = 1}^{n} k \cdot k! = \sum_{k = 1}^{n} (k \cdot k! + k! - 1) - \sum_{k = 1}^{n} (k! - 1) = \sum_{k = 1}^{n} ((k + 1)! - 1 - k! + 1) = \\ = \sum_{k = 1}^{n} (k + 1)! - k! = 2! - 1! + 3! - 2! + \dots + (n + 1)! - n! = (n + 1)! - 1! = (n + 1)! - 1 \\ ⟹ \sum_{k = 1}^{n} k \cdot k! = (n + 1)! - 1 \end{matrix}

\begin{matrix} Proof (combinatorial): \\ Let A = (1, 2, \dots, n + 1) \\ There are (n + 1)! permutations of this ordered list \\ Let us count all possible permutations except for the trivial (sorted) one \\ There are (n + 1)! - 1 of them \\ Let us now choose number k between 1 and n \\ 1. Let us choose one item from k first items and swap it with (k + 1) ’th item \\ There are k ways to do so \\ 2. Let us now count all possible permutations of first k items \\ There are k! such permutations \\ Let A_{k} = {permutations generated with steps 1 and 2} \\ Let i < j (symmetrical cases) \\ A_{i} \cap A_{j} = \emptyset because in any permutation of A_{i}, (j + 1) ’th element is equal to (j + 1) \\ And in any permutations of A_{j}, (j + 1) ’th element is not equal to (j + 1) \\ ⟹ | U_{k = 1}^{n} A_{k} | = \sum_{k = 1}^{n} | A_{k} | = \sum_{k = 1}^{n} k \cdot k! \\ Let P be a set of all non-trivial permutations \\ U_{k = 1}^{n} A_{k} \subseteq P is obvious \\ This is because \forall i \in [1, n] : \forall p \in A_{i} : p_{i + 1} \neq i + 1 \\ Let p \in P \\ There is a non-trivial part of p and there is a trivial part of p \\ Let the length of a non-trivial part of p be k + 1 \\ Then p \in A_{k} ⟹ P \subseteq U_{k = 1}^{n} A_{k} \\ ⟹ U_{k = 1}^{n} A_{k} is a set of all possible permutations of A except the trivial one \\ ⟹ | U_{k = 1}^{n} A_{k} | = (n + 1)! - 1 \\ ⟹ \sum_{k = 1}^{n} k \cdot k! = (n + 1)! - 1 \end{matrix}

6

\begin{matrix} Let A, B \subseteq R \\ | A | = n \leq k = | B | \end{matrix}

6a

\begin{matrix} How many functions f : A \to B exist such that: \\ \forall a_{1}, a_{2} \in A : a_{1} < a_{2} \to f (a_{1}) < f (a_{2}) \\ Solution: \\ Elements of A are strictly ordered by < on R \\ Elements of B are also strictly ordered by < on R \\ Thus to satisfy the condition we must simply choose n different images in B \\ ⟹ The answer is: (\binom{k}{n}) \end{matrix}

6b

\begin{matrix} How many functions f : A \to B exist such that: \\ \forall a_{1}, a_{2} \in A : a_{1} < a_{2} \to f (a_{1}) \leq f (a_{2}) \\ Solution: \\ Rhetoric is the same as in 6a, but this time repetitions are allowed \\ ⟹ The answer is: (\binom{n + k - 1}{k - 1}) \end{matrix}

7

\begin{matrix} Let n \in N \cup {0} \\ Prove algebraically and combinatorially: \sum_{k = 0}^{n} 3^{k} (\binom{n}{k}) = 4^{n} \\ Proof (algebraic): \\ By the binomial theorem: 4^{n} = (1 + 3)^{n} = \sum_{k = 0}^{n} 1^{n - k} 3^{k} (\binom{n}{k}) = \sum_{k = 0}^{n} 3^{k} (\binom{n}{k}) \\ ⟹ \sum_{k = 0}^{n} 3^{k} (\binom{n}{k}) = 4^{n} \\ Proof (combinatorial): \\ Let us construct a n -long string consisting of numbers 1, 2, 3, 4 \\ Number of ways to construct such a string is 4^{n} \\ Let us now first choose number 0 \leq k \leq n \\ 1. Let us choose n - k places for 1’s, there are (\binom{n}{k}) ways to do so \\ 2. For the left k places we need to choose either 2, 3 or 4 \\ There are 3^{k} ways to do this \\ Let A_{k} = {strings constructed using steps 1 and 2} \\ i \neq j ⟹ A_{i} \cap A_{j} = \emptyset because the amount of 1’s is different \\ ⟹ | U_{k = 0}^{n} A_{k} | = \sum_{k = 0}^{n} | A_{k} | = \sum_{k = 0}^{n} 3^{k} (\binom{n}{k}) \\ ⋃_{k = 0}^{n} A_{k} is a set of all possible n -long strings of numbers 1, 2, 3, 4 \\ ⟹ There are \sum_{k = 0}^{n} 3^{k} (\binom{n}{k}) ways to construct a n -long string of numbers 1, 2, 3, 4 \\ ⟹ \sum_{k = 0}^{n} 3^{k} (\binom{n}{k}) = 4^{n} \end{matrix}

8

\begin{matrix} Let n \in N \cup {0} \\ Prove combinatorially: \sum_{k = 0}^{2 n} k (\binom{2 n}{k}) = 2 n \cdot 2^{2 n - 1} \\ Proof (combinatorial): \\ If n = 0, then both sides are equal to 0 \\ If n \in N : \\ X ways how to choose a team: \\ 1. Choose a captain from 2 n players \\ 2. Choose a subset of left players to join the captain \\ X = 2 n \cdot 2^{2 n - 1} \\ Y ways to choose a team: \\ 1. Choose a subset of k players from 2 n players \\ 2. Choose one of the players in the team to be captain \\ k ranges from 0 to 2 n ⟹ Y = \sum_{k = 0}^{2 n} ((\binom{2 n}{k}) \cdot k) \\ X = Y ⟹ \sum_{k = 0}^{2 n} k (\binom{2 n}{k}) = 2 n \cdot 2^{2 n - 1} \\ P. S. This is also known as Captain’s identity \end{matrix}

9

\begin{matrix} Let n, m \in N \cup {0} \\ n \leq m \\ Prove combinatorially: \sum_{k = 0}^{n} (\binom{n}{k}) (\binom{m + k}{n}) = \sum_{k = 0}^{n} (\binom{n}{k}) (\binom{m}{k}) 2^{k} \end{matrix}

10a

\begin{matrix} Let n \in N \\ Prove combinatorially: \sum_{k = 0}^{n} k (\binom{n}{k}) = n \cdot 2^{n - 1} \\ Proof: \\ See task 8, it is identical \end{matrix}

10b

\begin{matrix} Let n \in N \\ Prove combinatorially: \sum_{k = 0}^{n} k (k - 1) (\binom{n}{k}) = n (n - 1) \cdot 2^{n - 2} \\ Proof: \\ Another variation of Captain’s identity \\ but now we choose a captain and his second-in-command, who must be a different person \end{matrix}

10c

\begin{matrix} Let n \in N \\ Prove algebraically or combinatorially: \sum_{k = 0}^{n} k^{2} (\binom{n}{k}) = n (n + 1) 2^{n - 2} \\ Proof: \\ k (\binom{n}{k}) = n (\binom{n - 1}{k - 1}) \\ ⟹ \sum_{k = 0}^{n} k^{2} (\binom{n}{k}) = n \sum_{k = 0}^{n} k (\binom{n - 1}{k - 1}) \\ k = 0 does not affect the sum \\ ⟹ \sum_{k = 0}^{n} k (\binom{n - 1}{k - 1}) = \sum_{k = 1}^{n} k (\binom{n - 1}{k - 1}) = \sum_{t = 0}^{n - 1} (t + 1) (\binom{n - 1}{t}) = \sum_{t = 0}^{n - 1} t (\binom{n - 1}{t}) + \sum_{t = 0}^{n - 1} (\binom{n - 1}{t}) \\ \sum_{t = 0}^{n - 1} t (\binom{n - 1}{t}) = (n - 1) \cdot 2^{n - 2} \\ \sum_{t = 0}^{n - 1} (\binom{n - 1}{t}) = 2^{n - 1} \\ ⟹ \sum_{k = 0}^{n} k (\binom{n - 1}{k - 1}) = (n - 1) \cdot 2^{n - 2} + 2^{n - 1} = (n - 1 + 2) \cdot 2^{n - 2} = (n + 1) 2^{n - 2} \\ \sum_{k = 0}^{n} k^{2} (\binom{n}{k}) = n \sum_{k = 0}^{n} k (\binom{n - 1}{k - 1}) ⟹ \sum_{k = 0}^{n} k^{2} (\binom{n}{k}) = n (n + 1) 2^{n - 2} \end{matrix}

11a

\begin{matrix} Let n \in N \\ How many ways there are to divide 2n tennis players into pairs for the tournament? \\ Solution: \\ We need to split 2 n players into n pairs \\ Order of pairs does not matter \\ Order inside the pairs also does not matter \\ So we simply need to calculate the number of ways to choose 2 different players from 2 n \\ and do so n times \\ Order of pairs doesn’t matter too, so we should divide by n! \\ Which is \frac{(\binom{2 n}{2, 2, \dots, 2})}{n!} = \frac{2 n!}{n! \cdot (2!)^{n}} = \frac{(2 n)!}{n! \cdot 2^{n}} \end{matrix}

11b

\begin{matrix} Let n \in N \\ Prove combinatorially: \frac{(2 n)!}{n! \cdot 2^{n}} = 1 \cdot 3 \cdot 5 \dots \cdot (2 n - 1) \\ Proof: \\ Let us think about left side in terms of task 11a: \\ Let us reorder 2 n players, there are (2 n)! ways to do so \\ Let us now treat each two players as a pair \\ Note that the order of pairs doesn’t matter, so we divide by n! \\ Note that in each pair order also doesn’t matter, so we divide n times by 2 \\ The final formula for the amount of pairs is: \\ \frac{(2 n)!}{n! \cdot 2^{n}} \\ Let us now think about the right side: \\ How many ways to choose a partner does the first person have? 2 n - 1 \\ There are now 2 n - 2 players without partners \\ How many way to choose a partner does the second person have? 2 n - 3 \\ This process will continue until the last two persons form a pair \\ The final formula for the amount of pairs is: \\ (2 n - 1) \cdot (2 n - 3) \cdot \dots \cdot 3 \cdot 1 \\ ⟹ \frac{(2 n)!}{n! \cdot 2^{n}} = 1 \cdot 3 \cdot 5 \dots \cdot (2 n - 1) \end{matrix}

12

\begin{matrix} Let n \in N \\ Prove combinatorially: \sum_{k = 1}^{n - 1} (n - k)^{2} (\binom{n - 1}{n - k}) = n (n - 1) \cdot 2^{n - 3} \\ Proof: \\ Let t = k - 1 \\ \sum_{k = 1}^{n - 1} (n - k)^{2} (\binom{n - 1}{n - k}) = \sum_{t = 0}^{n - 2} (n - 1 - t)^{2} (\binom{n - 1}{n - 1 - t}) = \sum_{t = 0}^{n - 2} (n - 1 - t)^{2} (\binom{n - 1}{t}) \\ Suppose there are n - 1 people \\ We would like to choose a team of at most n - 2 sailors, led by a captain and a navigator \\ The same person can be both captain and navigator \\ Let us first choose t people for the team, there are (\binom{n - 1}{t}) ways to do so \\ Let us then choose a captain and a navigator from n - 1 - t people left \\ They can be the same person, so the number of ways to do so is: (n - 1 - t)^{2} \\ The final formula would then be: \sum_{t = 0}^{n - 2} (n - 1 - t)^{2} (\binom{n - 1}{t}) \\ n (n - 1) \cdot 2^{n - 3} = (n - 2 + 2) (n - 1) \cdot 2^{n - 3} = (n - 2) (n - 1) \cdot 2^{n - 3} + (n - 1) \cdot 2^{n - 2} \\ Let us now first choose a captain and a navigator: \\ 1. Choose two different persons - (n - 1) (n - 2) \\ 2. Choose one person for both - (n - 1) \\ And then choose a team of sailors to join them: \\ 1. If captain and navigator are two persons \\ there are n - 3 people left to choose from: 2^{n - 3} \\ 2. If captain and navigator are the same person \\ there are n - 2 people left to choose from: 2^{n - 2} \\ The final formula would then be: (n - 2) (n - 1) \cdot 2^{n - 3} + (n - 1) \cdot 2^{n - 2} \\ ⟹ \sum_{k = 1}^{n - 1} (n - k)^{2} (\binom{n - 1}{n - k}) = \sum_{t = 0}^{n - 2} (n - 1 - t)^{2} (\binom{n - 1}{t}) = \\ = (n - 2) (n - 1) \cdot 2^{n - 3} + (n - 1) \cdot 2^{n - 2} = n (n - 1) \cdot 2^{n - 3} \\ ⟹ \sum_{k = 1}^{n - 1} (n - k)^{2} (\binom{n - 1}{n - k}) = n (n - 1) \cdot 2^{n - 3} \end{matrix}