Discrete-math 15

Discrete-math 15

Basic counting problems

Addition rule #lemma

\begin{matrix} Let A, B be finite sets such that A \cap B = \emptyset \\ Then | A \cup B | = | A | + | B | \\ \forall C, D \subseteq U : | C \cup D | = | C ∖ D | + | D | \end{matrix}

Multiplication rule #lemma

\begin{matrix} \forall A, B \subseteq U : | A \times B | = | A | \cdot | B | \end{matrix}

Extensions of the multiplication rule

\begin{matrix} For any n sets A_{1}, A_{2}, \dots, A_{n} \\ | A_{1} \times A_{2} \times A_{3} \times \dots \times A_{n} | = | A_{1} | \cdot | A_{2} | \cdot \dots \cdot | A_{n} | \end{matrix}

Example

\begin{matrix} Let A, B be finite sets \\ | A | = n, | B | = m \\ How many functions f : A \to B is there ? \\ Solution: \\ A = {a_{1}, \dots, a_{n}} \\ Let sequence S_{f} = (f (a_{1}), f (a_{2}), \dots, f (a_{n})) \\ f_{1} = f_{2} ⟹ S_{f_{1}} = S_{f_{2}} \\ f_{1} \neq f_{2} ⟹ S_{f_{1}} \neq S_{f_{2}} \\ ⟹ | B^{A} | = | {S_{f} | f : A \to B} | = | \underset{n times}{\underset{⏟}{B \times B \times B \times \dots \times B}} | = m^{n} \end{matrix}

Number of permutations/combinations #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}

With repetitions, order is important

\begin{matrix} Each chosen element can be one of n elements \\ ⟹ Number of ways to choose k elements : n^{k} \end{matrix}

Without repetitions, order is important (permutations)

\begin{matrix} First chosen element can be one of n elements \\ i -th chosen element can be one of n - i elements \\ i \in [0, k - 1] ⟹ P_{n}^{k} = (n - 0) (n - 1) (n - 2) \dots (n - k + 1) = \frac{n!}{(n - k)!} \end{matrix}

Without repetitions, order is not important (combinations)

\begin{matrix} Number of permutations of a binary string of length k is: k! \\ ⟹ Number of ways to choose k non-repeating elements with disregard to order is: \\ C_{n}^{k} = (\binom{n}{k}) = \frac{n!}{(n - k)! k!} \end{matrix}