Combinatorics

Binomial Coefficient and Binomial Identity Pascal’s Triangle \begin{matrix} {0 \choose 0}\\ {1 \choose 0} & {1 \choose 1}\\ {2 \choose 0} & {2 \choose 1} & {2 \choose 2}\\ {3 \choose 0} & {3 \choose 1} & {3 \choose 2} & {3 \choose 3}\\ {4 \choose 0} & {4 \choose 1} & {4 \choose 2} & {4 \choose 3} & {4 \choose 4}\\ .\\ .\\ . \end{matrix} Pascal’s Formula For all integers $n$ and $k$ with $1 \leq k \leq n - 1$, we have: $$ {n \choose k} = {{n-1} \choose k} + {{n-1} \choose {k-1}} $$ ...

Definition A combination of a set $S$ is a term usually used to denote an unordered selection of the element of $S$. It is simply a selection of a subset of $S$. $r$-combination = $r$-subset. $n\choose r$ is the number of $r$-subset in the set of size $n$. Theorem For $0 \leq r \leq n$, we have: $$ P(n, r) = r! {n \choose r} \text{ and } {n \choose r} = \frac{n!}{r!(n-r)!} $$ Proof ...

Gomory’s Theorem If you move two cells of a $8 \times 8$ chessboard of opposite colors, the remaining cells can be fully domino tiled. Proof Draw a closed path that passes through every square exactly once. (Draw a big C and then draw back and forth horizontally) Choose the two cells to be removed, and the closed path we have will be sperated into two paths. If we lable the close path we chose in the beginning from 1 to 64 in the order we drew it, white cells have odd numbers, and black cells have even numbers (or reversed). ...

The four basic counting principle Suppose that a set $S$ is partitioned into pairwise disjoint parts $S_1, S_2, …, S_n$. Addition principle: $$ |S| = |S_1| + |S_2| + … + |S_m| $$ Ex: Path counting: In a $3 \times 3$ grid, if you can move 1 step upward or 1 step to the right. How many ways do we have to move from bottom-left to top-right corner? The idea is to break this problem into smaller problems. Addition principle guarrantees that we can add the numbers together. ...