1.5 Counting and Combinatorics

Basic Principles

Addition Principle

If a task can be done in either of two disjoint ways, then the total ways are summed: $|A\cup B|=\left|A\right|+\left|B\right|$ when $A\cap B=\varnothing$.

Multiplication Principle

If a task consists of two steps with $m$ ways for step $1$ and $n$ ways for step $2$, then $m\times n$ total ways.

Permutations and Combinations

Permutations

Distinct: Number of ways to arrange $n$ distinct items: $n!$.

Partial: Number of ways to choose and order $k$ from $n$: $P(n,k)=\frac{n!}{(n-k)}$.

With Repetition: $n^k$ sequences of length $k$ from $n$ types.

Combinations

Without Repetition: Number of ways to choose $k$ from $n$: $\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!(n-k)!}$.

With Repetition: Number of multisets of size $k$ from $n$ types: $\left(\begin{array}{c}n+k-1\\ k\end{array}\right)$.

Binomial Theorem

For any integer $n\geqq 0$:

${(x+y)}^n={\sum }_{k=0}^n(\left(\begin{array}{c}n\\ k\end{array}\right)x^{n-k}{y}^k)$

Pigeonhole Principle

If $n$ pigeons are placed into $m$ holes and $n>m$, then some hole contains at least two pigeons. More generally: at least one hole has at least $\lceil n/m\rceil$ pigeons.