home

# Counting

## Product rule

If a procedure can be split into two tasks with $$m$$ ways to complete the first an $$n$$ the second, then there are $$m \times n$$ possible approaches

More generally if there are $$k$$ tasks, with $$n_i$$ ways for completing task $$i$$ then there are $$n_1 \times n_2 \ldots \times n_k$$ ways of completing the procedure. $\prod_{i=1}^k n_i$ In terms of Sets, if each task is disjoint then the number of approaches can be considered as $|A \times B| = |A| \cdot |B|$

## Sum rule

If a procedure can either be completed in $$m$$ or $$n$$ ways, then it can be completed in $$m + n$$ ways.

Generalising to a total $$k$$ independent tasks this provides $\sum_{i=1}^{k}n_i$ Alternatively, considering each task as belonging to a disjoin set we may also find the cardinality of their union. $|A \cup B| = |A| + |B|$

## Subtraction rule

Also: Inclusion-exclusion principle If a choice can be made between two options, each with $$m$$ or $$n$$ items. The combined possibility are $$m + n -k$$ where $$k$$ is the number of items in common.

In set form, we may consider this as a case of intersecting sets. $|A \cup B| = |A| + |B| - |A \cap B|$

## Division rule

If a procedure can be completed in $$n$$ ways, and for each way, exactly $$d$$ of the $$n$$ ways correspond to that way. The total number of ways to complete the procedure is then $$\frac n d$$.

This further generalises to $$\frac {n} {d_1 \cdot d_2 \cdot ... d_n}$$ where $$d_n$$ is the number of repeats of each common element.

Within the set context, if the set $$A$$ is the union of $$n$$ pair-wise disjoint subsets each with $$d$$ elements, then $$n = \frac {|A|} d$$.