Many finite problems ask how many outcomes are possible without requiring us to list them one by one. Counting principles turn the structure of a choice process into arithmetic.

Addition principle

If a result can occur in one of several mutually exclusive ways, the numbers of possibilities add.

For example, if a shelf contains $4$ novels and $3$ biographies and one book is chosen, there are

$$4+3=7$$

possible choices.

Multiplication principle

If a process consists of successive choices, the numbers of possibilities multiply. If there are $3$ possible shirts and $2$ possible pairs of trousers, then there are

$$3\cdot2=6$$

possible outfits.

More generally, if successive stages have $n_1,n_2,\ldots,n_k$ possibilities, the total number of outcomes is

$$n_1n_2\cdots n_k.$$

With and without replacement

The number of choices available at a later stage may depend on earlier choices. Choosing two cards with replacement restores the first card before the second draw, while choosing without replacement reduces the number of available cards.

Factorials

Repeated descending products occur frequently in counting. For a natural number $n$,

$$n!=n(n-1)(n-2)\cdots2\cdot1,$$

with

$$0!=1.$$

Factorials provide compact notation for the ordered arrangements developed next.