Combinatorics

Combinatorics is about counting. In this course, we look at the number of ways that an event can occur.

Addition

If, given a task $T$ with two subtasks $T_1$ and $T_2$, you can accomplish the task by performing either $T_1$ or $T_2$, then you can use the addition principle.

The addition principle states that the total number of ways to perform task $T$ is $T_1+T_2$.

$$\begin{array}{c} \text{How many ways can you choose either one of}\\\text{three pizzas or one of two pastas?}\\ \hline\\ T_1=\text{Pizzas}=3\\ T_2=\text{Pasta}=2\\ \\ \text{Total}=T_1+T_2=3+2=5 \end{array}$$

Multiplication

If, given a task $T$ with two subtasks $T_1$ and $T_2$, you can accomplish the task by performing both $T_1$ and $T_2$, then you can use the multiplication principle.

The multiplication principle states that the total number of ways to perform task $T$ is $T_1\cdot T_2$.

$$\begin{array}{c} \text{How many ways can you choose one of}\\\text{three pizzas and one of two pastas?}\\ \hline\\ T_1=\text{Pizzas}=3\\ T_2=\text{Pasta}=2\\ \\ \text{Total}=T_1\cdot T_2=3+2=6 \end{array}$$

Repetition & Order

The two main things you have to worry about are if the order matters, and if you allow repetitions.

$$\begin{array}{c|c|c} &\text{ordered}&\text{unordered} \\\hline\\ \text{repetition allowed} & n^k & \frac{(k+n-1)!}{k!(n-1)!}=\binom{k+n-1}{n} \\\\\hline\\ \text{no repetition allowed} & \dfrac{n!}{(n-k)!} & \frac{n!}{k!(n-k)!}=\binom{n}{k} \\\\\hline\end{array}$$

There are four scenarios: