Counting Theorems

Basic Counting Properties

$(\begin{matrix} n \\ 0 \end{matrix}) = 1; (\begin{matrix} n \\ n \end{matrix}) = 1$
$(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ n - k \end{matrix}) ⟶$ pairs
$(\binom{n}{k}) = \frac{n}{k} (\binom{n - 1}{k - 1})$

Number of subsets of a set with size n (power set)

(\begin{matrix} n \\ 0 \end{matrix}) + (\begin{matrix} n \\ 1 \end{matrix}) + (\begin{matrix} n \\ 2 \end{matrix}) + . . . + (\begin{matrix} n \\ n \end{matrix}) = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) = 2^{n}

Left side is equal to $2^{n}$ by Bijection

For any integer $n$ and $0 \leq k < n$

(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n - 1 \\ k - 1 \end{matrix}) + (\begin{matrix} n - 1 \\ k \end{matrix}) ⟺ (\begin{matrix} n \\ k \end{matrix}) - (\begin{matrix} n - 1 \\ k \end{matrix}) = (\begin{matrix} n - 1 \\ k - 1 \end{matrix})

$(\begin{matrix} n - 1 \\ k - 1 \end{matrix})$ counts the subsets with one element already selected

$(\begin{matrix} n - 1 \\ k \end{matrix})$ counts all subsets where that same element cannot be selected

As they are 2 separate scenarios, we add the possibilities (Sum Rule)

(x + y)^{n} = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) x^{k} y^{n - k} = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) x^{n - k} y^{k}

For example

(x + y)^{4} = x^{0} y^{4} + 4 x^{1} y^{3} + 6 x^{2} y^{2} + 4 x^{3} y^{1} + x^{4} y^{0}

Therefore the coefficient for $x^{k}$ is $(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n \\ n - k \end{matrix})$

(\begin{matrix} m + n \\ r \end{matrix}) = \sum_{k = 0}^{r} (\begin{matrix} m \\ k \end{matrix}) (\begin{matrix} n \\ r - k \end{matrix})

$(\begin{matrix} m + n \\ r \end{matrix})$ is the coefficient of $y^{r}$ when expanding $(1 + y)^{m + n}$

$(1 + y)^{m + n} = (1 + y)^{m} (1 + y)^{n} = ()$

Generalized for any number of $n$ s

\begin{pmatrix} n_1+...+n_p\\r \end{pmatrix}=\sum_{k_1+...+k_p=r}^r\begin{pmatrix} n_1\\k_1 \end{pmatrix}\begin{pmatrix} n_2\\k_2 \end{pmatrix}\begin{pmatrix} n_p\\k_p \end{pmatrix}$$= $\begin{pmatrix} r+p-1\\p-1 \end{pmatrix}$ = multiset with p groups of r # Inclusion/Exclusion Principle - sets = no repeated elements - $|A|+|B| =|A\cup B|-|A\cap B| = |A|+|B|-|AB|$ - $$|A_1\cup A_2\ \cup\ ...\ \cup\ A_n|= \sum_{S\neq 0,S\subseteq\{1,...,n\}}(-1)^{|S|-1}|A_S|

n^{2} (\binom{2 n - 2}{n - 2}) = \sum_{j = 1}^{n} j (n - j) {(\binom{n}{j})}^{2}