Discrete-math 16

Number of permutations/combinations (continued) #definition

\begin{matrix} How many ways there is to choose k elements from the set \\ {1, 2, \dots, n} = [n] \\ Solution: \\ (\begin{array}{ccc} Order is important & Order is not important \\ With repetitions & A_{n}^{k} = n^{k} & C_{n + k - 1}^{k} = \frac{(n + k - 1)!}{(n - 1)! k!} \\ Without repetitions & P_{n}^{k} = \frac{n!}{(n - k)!} & C_{n}^{k} = \frac{n!}{(n - k)! k!} \end{array}) \end{matrix}

\begin{matrix} Multiset is a set of elements that can repeat \\ It can be denoted as: M = a_{1}^{α_{1}} a_{2}^{α_{2}} \dots a_{n}^{α n} \\ Number of ways to choose k elements from the set A of size n is equal to the number of \\ multisets of size k contatining elements of set A \\ Which is equal to number of solutions of equation α_{1} + α_{2} + \dots + α_{n} = k \\ Let us denote this equation as: \\ \underset{α_{1}}{\underset{⏟}{00 \dots 0}} 1 \underset{α_{2}}{\underset{⏟}{00 \dots 0}} 1 \dots \underset{α_{n}}{\underset{⏟}{00 \dots 0}} 1 \\ Length of this binary string is n + k - 1 \\ Number of ways to choose k places in the string of length n + k - 1 is: \\ \frac{(n + k - 1)!}{(n - 1)! k!} = (\binom{n + k - 1}{k}) = (\binom{n + k - 1}{n - 1}) \end{matrix}

\begin{matrix} How many solutions is there: \\ x_{1} + x_{2} + \dots + x_{n} \leq k & (1) \\ \forall i \in [1, n] : x_{i} \geq 0 \\ Let x_{n + 1} = k - \sum_{i = 1}^{n} x_{i} \\ Each solution for (1) is equivalent to solution of \\ x_{1} + \dots + x_{n} + x_{n + 1} = k \\ ⟹ Number of such solutions is: (\binom{n + k}{k}) \end{matrix}

\begin{matrix} \forall n \geq k \in N : (\binom{n}{k}) \in N \\ Proof (combinatorial): \\ (\binom{n}{k}) is equal to the number of subsets of size k of element from set [n] \\ Number of subsets is a natural number ⟹ (\binom{n}{k}) \in N \end{matrix}

\begin{matrix} (\binom{n}{k}) = (\binom{n}{n - k}) \\ Proof: \\ (\binom{n}{k}) = \frac{n!}{(n - k)! k!} = \frac{n!}{k! (n - k)!} = (\binom{n}{n - k}) \end{matrix}

\begin{matrix} \forall n \geq k \in N : (\binom{n}{k}) = (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) \\ Proof: \\ (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) = \frac{(n - 1)!}{(n - k - 1)! k!} + \frac{(n - 1)!}{(n - k)! (k - 1)!} = \\ = \frac{(n - 1)! (n - k)}{(n - k)! k!} + \frac{(n - 1)! k}{(n - k)! (k)!} = \frac{(n - 1)! n}{(n - k)! (k)!} = (\binom{n}{k}) \end{matrix}