Sum and Product Rule

Counting problems ask how many valid choices or objects exist. Usually, we want to calculate this number without listing every possibility.

The Sum Rule

If a choice can be made in exactly one of several separate cases, add the numbers of possibilities.

For example, suppose we can choose one of 4 red pens or one of 3 blue pens. There are

\[ 4 + 3 = 7 \]

possible choices.

The cases must not overlap. Otherwise, an object that belongs to more than one case would be counted more than once.

The Product Rule

If constructing one result requires several successive choices, multiply the numbers of choices.

For example, suppose we choose one of 3 shirts and one of 2 pairs of trousers. There are

\[ 3 \cdot 2 = 6 \]

possible outfits.

The product rule also works with more than two choices. A code made of two letters followed by one digit has

\[ 26 \cdot 26 \cdot 10 = 6760 \]

possibilities when repetition is allowed.

Sum or Product?

Structure Rule
Choose from case A or case B Add
Choose from A and then from B Multiply

For example:

  • Choosing one of 4 pens or one of 3 notebooks gives \(4+3=7\) choices.
  • Choosing one of 4 pens and one of 3 notebooks gives \(4\cdot3=12\) choices.

Words such as or and and are useful hints, but it is more important to identify whether the possibilities are separate alternatives or successive choices.

Combining the Rules

Suppose we want to travel from \(A\) to \(E\) through the following network of one-directional roads.

flowchart LR
    A((A))
    B((B))
    C((C))
    D((D))
    E((E))

    A --> B
    A --> B
    A --> B
    B --> C
    B --> C
    A --> D
    A --> D
    D --> C
    D --> C
    D --> C
    D --> C
    C --> E
    C --> E
    C --> E
    C --> E
    C --> E

There are \(3\cdot2=6\) routes to \(C\) through \(B\) and \(2\cdot4=8\) routes to \(C\) through \(D\). These are separate cases, so there are

\[ 3\cdot2 + 2\cdot4 = 14. \]

From \(C\), there are 5 choices for the final road to \(E\). Therefore, the number of routes from \(A\) to \(E\) is

\[ (3\cdot2 + 2\cdot4)\cdot5 = 70. \]

In general, multiply choices within a case, then add the results of separate cases.