The Multiplication Principle

The Multiplication Principle for Counting Procedures

If a sequence can be described as a sequence of $n$ independent steps, with $i_{1}$ possible outcomes for the first step, $i_{2}$ possible outcomes for the second step, $\dots$ , and $i_{n}$ possible outcomes for the $n^{t h}$ step, then the total number of composite outcomes of the procedure is $i_{1} i_{2} \dots i_{n}$

A sequential counting procedure is one that satisfies the following three properties:

The steps are ordered, i.e. any two sequences of different outcomes represent distinguishable composite outcomes
The steps are independent, i.e. the number of outcomes of one step is not affected by the outcomes of the preceding steps
The steps are complete, i.e. each composite outcome consists of a complete sequence of individual outcomes, one for each step

Example

A binary sequence is a sequence whose elements come from the set ${0, 1}$ . For example, 100110 is a binary sequence of length 6

How many binary sequences of length 5 are there?
How many binary sequences of length 5 begin with 101?

Part 1:
Each step $i$ has 2 possible outcomes ${0, 1}$
$n = 5$
$∴$ The total number of composite outcomes, $\prod_{r = 1}^{n} i_{r}$ , is $2^{5}$
Part 2:
$i_{1}, i_{2}, i_{3}$ all have one option, making 101
The steps $i_{4}, i_{5}$ choose from ${0, 1}$
$n = 5$
$∴$ $\prod_{r = 1}^{n} i_{r} = \prod_{r = 4}^{5} i_{r} = 2^{2}$