2. The product rule

The product rule

The product rule

If there is a sequence of $k$ tasks such that:

• there are $n_1$ ways to do the first task
• $n_2$ to do the second
• $n_k$ to do the $k$th task ? Then, there are $n_1\cdot n_2\cdot ...\cdot n_k$ ways to do the whole sequence of $k$ tasks

$$|A_1\times A_2\times ...\times A_k|=|A_1|\cdot |A_2|\cdot ...\cdot |A_k|$$

title: Example 1
If each number plate contains a sequence of three letters followed by three digits (and no such sequence is prohibited), then the number of available different number plates is:
 
$$
	26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 = 17, 576, 000
$$

Usage with functions

If $|A|=n$ and $|B|=m$ then the number of different $f:A\to B$ functions is: ?

$$\stackrel{n}{\overbrace{m\cdot m\cdot ...\cdot m}}=m^n$$

title: Example 2 (with functions)
Let $A = \{ a,b,c \}, B = \{ d,e \} \rightsquigarrow n = 3, m = 2$.
- There are $2$ ways to choose a value for $a$.
Then there are $2$ ways to choose a value for $b$ and then $c$.
 
Hence $2^3 = 8$.

Link to original

Counting the subsets of a finite set

Let $S$ be a finite set having $n$ elements. How many subsets does $S$ have? Or otherwise, what is the cardinality of $P(S)$?

We list the elements of $S:s_1,s_2,...,s_n$. We can choose a subset $A$ of $S$ by going through this list and decide for each element whether it is in $A$ or not.

• We have one ‘task’ for each element: $n$ tasks total
• Each task can be done in two ways: IN or OUT We choose whether to leave it in or leave it out.

Hence, by product rule:

$$|P(S)|=\stackrel{n}{\overbrace{2\cdot 2\cdot ...\cdot 2}}=2^n$$

Combining sum and product rules

Take for example, how many four-digit numbers can begin with either $7$ or $42$?

• The set can be broken down into two disjoint sets:
  1. four-digit numbers beginning with $7$
  2. four-digit numbers beginning with $42$
• In case (1), if we begin with $7$, there are $3$ digits to be filled in with $10$ choices each. Hence by product rule: $10\cdot 10\cdot 10=1000$
• In case (2), there are $2$ digits to be filled with $10$ choices each. So $10\cdot 10=100$.
• Hence by sum rule, we combine these to be $1000+100=1100$.