The Basics of Counting

The Product Rule

Suppose that a procedure can be broken down into a sequence of two tasks. If there are $n_1$ ways to do the first task and for each of these ways of doing the first task, there are $n_2$ ways to do the second task, then there are $n_1{n}_2$ ways to do the procedure

The Sum Rule

If a task can be done either in one of $n_1$ ways or in one of $n_2$ ways, where none of the set of $n_1$ ways is the same as the set of $n_2$ ways, then there are $n_1+n_2$ ways to do the task.

The Subtraction Rule (Inclusion-Exclusion for Two Sets)

If a task can be done either $n_1$ ways or $n_2$ ways, then the number of ways to do the task is $n_1+n_2$ minus the number of ways to do the task that are common to the two different ways.

The Division Rule

There are $\frac{n}{d}$ ways to do a task if it can be done using a procedure that can be carried out in $n$ ways, and for every way $w$, exactly $d$ of the $n$ ways correspond to way $w$

We can restate the division rule in terms of sets: "If the finite set $A$ is the union of $n$ pairwise disjoint subsets each with $d$ elements, then $n=\left|A\right|/d$"