## 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:

- Ordered selection with repetition.
- Ordered selection without repetition.
- Unordered selection with repetition.
- Unordered selection without repetition.