Discrete-math 18

Even and Odd numbers amount #lemma

\begin{matrix} Let n \in N \\ E = {X \subseteq [n] | | X | is even} \\ O = {X \subseteq [n] | | X | is odd} \\ Then | E | = | O | \\ Proof: \\ How to choose a subset of even size: \\ 1. Choose any subset of [n - 1] . Number of ways to do it is 2^{n - 1} \\ 2. If the size of the chosen subset is even, we are done. If it’s odd, we add n to the subset \\ ⟹ | E | = 2^{n - 1} \cdot 1 = 2^{n - 1} \\ O \cap E = \emptyset \\ O \cup E = P ([n]) \\ | O \cup E | = | O | + | E | - | O \cap E | \\ ⟹ | O | = | P ([n]) | - | E | = 2^{n} - 2^{n - 1} = 2^{n - 1} \\ ⟹ | E | = | O | \end{matrix}

\begin{matrix} \forall n \in N : \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = 0 \\ Proof (combinatorial): \\ \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = \underset{Number of subsets of even size}{\underset{⏟}{\sum_{k = 0}^{⌊ n / 2 ⌋} (\binom{n}{2 k})}} - \underset{Number of subsets of odd size}{\underset{⏟}{\sum_{k = 1}^{⌈ n / 2 ⌉} (\binom{n}{2 k - 1})}} = 0 \\ Proof (algebraic): \\ \forall x, y \in R : x \neq 0 \neq y : (x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k} \\ Let x = - 1, y = 1 \\ (- 1 + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) (- 1)^{k} 1^{n - k} = \sum_{k = 0}^{n} (\binom{n}{k}) (- 1)^{k} \\ ⟹ \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = 0 \end{matrix}

\begin{matrix} \forall n \in N : \sum_{k = 0}^{n} k (\binom{n}{k}) = n \cdot 2^{n - 1} \\ Proof (combinatorial): \\ X ways how to choose a team: \\ 1. Choose a captain from n players \\ 2. Choose a subset of left players to join the captain \\ X = n \cdot 2^{n - 1} \\ Y ways to choose a team: \\ 1. Choose a subset of k players from n players \\ 2. Choose one of the players in the team to be captain \\ ⟹ Y = \sum_{k = 0}^{n} (\binom{n}{k}) \cdot k \\ X = Y ⟹ \sum_{k = 0}^{n} k (\binom{n}{k}) = n \cdot 2^{n - 1} \\ Proof (algebraic): \\ k (\binom{n}{k}) = n (\binom{n - 1}{k - 1}) \\ \sum_{k = 0}^{n} k (\binom{n}{k}) = \sum_{k = 1}^{n} n (\binom{n - 1}{k - 1}) = n \sum_{k = 1}^{n} (\binom{n - 1}{k - 1}) \underset{t = k - 1}{\underset{⏟}{=}} n \sum_{t = 0}^{n - 1} (\binom{n - 1}{t}) = n \cdot 2^{n - 1} \\ Proof (calculus): \\ \forall x, y \in R : x \neq 0 \neq y : (x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} y^{n - k} \\ Let y = 1 \\ (x + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{k} \\ Let’s differentiate both sides: \\ n \cdot (x + 1)^{n - 1} = \sum_{k = 0}^{n} k (\binom{n}{k}) x^{k - 1} \\ Let x = 1 \\ n \cdot 2^{n - 1} = \sum_{k = 0}^{n} k (\binom{n}{k}) \end{matrix}

\begin{matrix} Moves right or up, how many ways there are to get from (0, 0) to (n, n) \\ n moves up \\ n moves right \\ Total of 2 n moves \\ ⟹ Number of paths is the number of ways to choose n steps up from 2 n steps total \\ ⟹ Number of paths is (\binom{2 n}{n}) \end{matrix}

\begin{matrix} Each step in path satisfies x \geq y \\ Any "bad" path goes through the line y = x + 1 \\ Every "bad" path can be represented as an "inversed" Lattice path from (- 1, 1) \\ ⟹ Number of "bad" paths is (\binom{2 n}{n - 1}) \\ ⟹ Number of "good" paths is (\binom{2 n}{n}) - (\binom{2 n}{n - 1}) = \\ \frac{(2 n)!}{n! n!} - \frac{(2 n)!}{(n + 1)! (n - 1)!} = \frac{(2 n)!}{n! n!} - \frac{(2 n)!}{n! n!} \cdot \frac{n}{n + 1} = \frac{n + 1 - n}{n + 1} (\binom{2 n}{n}) = \frac{1}{n + 1} (\binom{2 n}{n}) \end{matrix}

\begin{matrix} \forall n \in N : C_{n} = \frac{1}{n + 1} (\binom{2 n}{n}) \end{matrix}

\begin{matrix} How many balanced sequences of 2 n brackets are there? \\ Balanced sequence of brackets is: \\ 1. For any prefix #_{[} \geq #_{]} \\ 2. For the whole sequence #_{[} = #_{]} \\ Let [be a step to the right \\ Let] be a step up \\ ⟹ Number of balanced bracket sequences is a number of "good" Lattice paths \\ from (0, 0) to (n, n) \\ Which is equal to n -th Catalan number \\ C_{n} = \frac{1}{n + 1} (\binom{2 n}{n}) \end{matrix}