home

Counting

Product rule

If a job 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 generaly if there a \(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 job. \[ \prod_{i=1}^k n_i \]

Sum rule

If a job can either be completed in \(m\) or \(n\) ways, then it can be completed in \(m + n\) ways.

Subtraction rule

Also: Inclusiion-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.