Counting · Definition

Multiplication principle

discrete mathematicscounting

It is the basic tool for counting without listing: it turns a large count into a product of small counts.

Definition

If a task is done in successive steps and step \(i\) admits \(n_i\) options regardless of how the earlier steps were done, the total number of ways \(N\) is the product of those numbers.

\[N=n_1\cdot n_2\cdots n_k\]

To use it, split the task into ordered steps and count the options of each one. Putting together an outfit from 4 shirts and 3 pairs of trousers is a two-step task: there are \(4\cdot 3=12\) outcomes, because each shirt pairs with each pair of trousers. A decision tree shows it: 4 initial branches, each splitting into 3.

The key condition is that the number of options at a step must not depend on what was chosen before. The available objects may change, but not how many there are. In three-digit numbers with distinct digits, the first digit has 9 options, the second 9 and the third 8 whatever digits were used, so there are \(9\cdot 9\cdot 8=648\).

If the options at a step do depend on earlier ones, reorder the steps and start with the most restrictive: to count even numbers, choose the last digit first. When every step has the same \(n\) options the product is \(n^k\); this gives the \(2^8\) binary strings of length 8 or the \(2^6\) subsets of a 6-element set.

The most common mistake is to add instead of multiply. The sum rule applies when choosing among mutually exclusive alternatives ("either this or that"); the product rule, when making several choices one after another ("and then"). This principle underlies factorials, permutations and binomial coefficients.

Think about it

Why are three-digit numbers with distinct digits counted as \(9\cdot 9\cdot 8\) and not \(9\cdot 10\cdot 10\)?

Because digits cannot repeat: after the first (9 options, no 0) the second excludes only that digit (9 options) and the third excludes two (8 options). The product \(9\cdot 10\cdot 10\) would allow repeats.

If a step has only one option, does the total change?

No: multiplying by 1 leaves the product unchanged; a forced step adds no possibilities.

Exercises 10

  1. A shop offers 4 different shirts and 3 different pairs of trousers. In how many ways can an outfit with one shirt and one pair of trousers be put together?
  2. A code has 2 letters (out of 26) followed by 3 digits (0 to 9). How many codes are there if repetitions are allowed?
  3. How many binary strings of length 8 are there?
  4. How many three-digit numbers (100 to 999) have three distinct digits?
  5. A plate has 3 different letters (out of 26) followed by any 2 digits. How many plates are there?
  6. How many functions are there from a 4-element set to a 3-element set?
  7. How many even three-digit integers (100 to 999) are there?
  8. Select the condition required to multiply the number of options of each step.
  9. Without repeating digits, how many odd 4-digit numbers (1000 to 9999) are there?
  10. How many positive divisors does 360 have? Use \(360=2^3\cdot 3^2\cdot 5\).

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §6.1
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §9.2
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §1.1