Combinatorics and computing

9.3 The Multiplication principle


Suppose a document is printed using five different fonts: Arial, Gothic, Courier, Times Roman and Sans Serif. Suppose also that each font can appear in one of three styles: normal, bold and italic. How many combinations of a font and a style are there altogether? The question can be answered very simply. Since there are five fonts, each of which can be paired with one of three styles, the total number of combinations is 5 × 3 = 15. The possible combinations are illustrated in the tree diagram in Figure 9.1.
Figure 9.1

The problem can also be expressed in the notation of sets. Let F be the set of fonts, and let S be the set of styles. A combination such as Courier Italic can be thought of as an ordered pair – (Courier, Italic). The set of all such ordered pairs is the Cartesian product F × S, and the problem asks for the cardinality of F × S. We obtained the answer by multiplying the cardinality of F by the cardinality of S.
This example illustrates a basic principle in combinatorics known as the Multiplication principle. The Multiplication principle states that the cardinality of the Cartesian product of two finite sets X and Y equals the cardinality of X multiplied by the cardinality of Y. We can write this result in symbols as follows:

More generally, we can obtain the cardinality of a Cartesian product X 1 × X 2 × ... × X n of a number of finite sets by multiplying together the cardinalities of the sets X 1 , X 2 , ..., X n . The Multiplication principle is usually stated in this more general form:

For many applications, a more intuitive (though somewhat wordier) version of the Multiplication principle is useful:
If a selection process consists of n steps, where the selection in the
first step can be done in k1 ways, the selection in the second step can
be done in k 2 ways, and so on, then the total number of possible
selections is k 1 k 2 ...k n .
We have actually met the Multiplication principle already. In Chapter 3, we used it to calculate the number of distinct integers that can be stored in 16 bits, by arguing that there were two possibilities for the first bit, two possibilities for the second bit, and so on, giving an answer of 2 n integers altogether. We also used the Multiplication principle in Chapter 5, when we showed that any set with n elements has 2 n subsets.


Example 9.3.1 The usercodes on a certain computer consist of 3 letters, followed by 3 digits, followed by a letter, for example, XYZ123A. (Assume that no distinction is made b etween upper-case and lower-case letters.)


(a) How many different usercodes can be constructed altogether?
(b) In how many of these usercodes does the digit 0 occur at least once?


Solution (a) The first character may be chosen to be any one of the 26 letters of the alphabet, and so may the second and third characters. The fourth, fifth and sixth characters are each chosen from the 10 digits, and the seventh character is chosen from the 26 letters. By the Multiplication principle, the total number of different usercodes is:
26 × 26 × 26 × 10 ×10 × 10 × 26 = 456 976 000
(b) Rather than try to count directly the number of usercodes containing at least one zero, it is simpler to count the number of usercodes that contain no zeros, and to subtract the answer from the result of part (a). If no zeros are allowed, then there are only nine choices available for each digit rather than ten, so the number of usercodes with no zeros is:
26 × 26 × 26 × 9 × 9 × 9 × 26 = 333 135 504
Therefore, the number of usercodes containing at least one zero is:
456 976 000 – 333 135 504 = 123 840 496