Rule of Sum and Rule of Product

The Rule of Sum (Addition Principle) and Rule of Product (Multiplication Principle) are principles of counting that are used to build up the theory of enumerative combinatorics.

Rule of Sum / Addition principle: If there are $n$ ways of doings something, and $m$ ways of doing another thing, both of which cannot be done at the same time, then there are $n+m$ ways to choose one of these actions.

Rule of Product / Multiplication principle: If there are $n$ ways of doing something, and $m$ ways of doing another thing after that, then there are $n\times m$ ways to perform both of these actions.

Worked Examples

1. Calvin wants to go to Milwaukee. He can choose from $3$ bus services or $2$ train services to head from home to downtown Chicago. From there, he can choose from 2 bus services or 3 train services to head to Milwaukee. How many ways are there for him to get to Milwaukee?

Solution: Since Calvin can either take a bus or a train downtown , he has $3+2 =5$ ways to head downtown (Rule of Sum). After which, he can either take a bus or a train to Milwaukee, hence he has another $2+3=5$ ways to head to Milwaukee (Rule of Sum). Thus in total, he has $5 \times 5 = 25$ ways to head from home to Milwaukee (Rule of Product).

2. Calvin wants to go to Milwaukee (see previous question). This time, he has to purchase a bus concession (which will only allow him to take buses), or a train concession (which will only allow him to take trains). If he only has money for $1$ of these concessions, how many ways are there for him to get to Milwaukee?

Solution: If Calvin purchases a bus concession, he has $3 \times 2=6$ ways to get to Milwaukee (Rule of Product). If Calvin purchases a train concession, he has $2\times3=6$ ways to get to Milwaukee (Rule of Product). Hence, he has $6+6=12$ ways to get to Milwaukee in total (Rule of Sum).

3. Six friends Andy, Bandy, Candy, Dandy, Endy and Fandy want to sit in a row at the cinema. If there are only six seats available, how many ways can we seat these friends?

Solution: For the first seat, we have a choice of any of the 6 friends. After seating the first person, for the second seat, we have a choice of any of the remaining 5 friends. After seating the second person, for the third seat, we have a choice of any of the remaining 4 friends. After seating the third person, for the fourth seat, we have a choice of any of the remaining 3 friends. After seating the fourth person, for the fifth seat, we have a choice of any of the remaining 2 friends. After seating the fifth person, for the sixth seat, we have a choice of only 1 of the remaining friends. Hence, by the Rule of Product, there are $6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$ ways to seat these 6 people. More generally, this problem is known as a Permutation. There are $n! = n \times (n-1) \times (n-2) \times \ldots \times 1$ ways to seat $n$ people in a row.

4. How many positive divisors does $2000 = 2^4 5^3$ have?

Solution: Any positive divisor of 2000 must have the form $2^a 5^b$, where $a$ and $b$ are integers satisfying $0 \leq a \leq 4, 0 \leq b \leq 3$. There are 5 possibilities for $a$ and 4 possibilities for $b$, hence there are $5 \times 4 = 20$ (Rule of Product) positive divisors of 2000 in all.