The Multiplication Principle

Discrete Uniform Distributions

If a random vector X for an experiment is uniformly distributed on a finite subset S of Rⁿ, then the probability distribution of X is proportional to counting measure:

Such random vectors arise frequently in many different experiments, particularly those that can be interpreted as sampling from a finite set. The set S is typically very large, hence efficient counting methods are essential. For example, see the discussions of the Ball and Urn experiment.

One-to-One Correspondence

In many cases, a set of objects can be counted by establishing a one-to-one correspondence between the given set and some other set. Naturally, the two sets have the same number of elements, but for some reason, the second set may be easier to count.

The Multiplication Principle

The multiplication principle of combinatorics is based on the formulation of a procedure (or algorithm) that generates the objects to be counted. Specifically, suppose that the procedure consists of k steps, performed sequentially, and that for each j, step j can be performed in n_j ways regardless of the choices made on the previous steps. Then the number of ways to perform the entire procedure (and hence the number of objects) is

n₁n₂···n_k.

The key to a successful application of the multiplication principle to a counting problem is the clear formulation of a procedure that generates the objects being counted, so that each object is generated once and only once. That is, we must neither over-count nor undercount.

Equivalent Formulations

The first two Exercises below give equivalent formulations of the multiplication principle.

1. Suppose that A is a subset of R^k and and that we denote the elements of A by

(x₁, x₂, ..., x_k)

Suppose that for each j, x_j has n_j different values, regardless of the values of the previous coordinates. Show that the cardinality of A is

n₁n₂···n_k.

2. Suppose that T is an ordered tree with depth k and that each vertex at level i - 1 has n_i children for i = 1, 2, ..., k. Show that the number of vertices at level k is

n₁n₂···n_k.

Additonal Exercises

3. A license number consists of two letters followed by five digits. How many different license numbers are there?

4. Suppose that a Personal Identification Number (PIN) is a four-symbol code word in which each entry is either a letter or a digit. How many PINs are there?

5. Show that if S is a set with n elements, then the number of subsets of S is 2ⁿ.

In particular, by Exercise 5, an experiment with n outcomes has 2ⁿ events.

6. Show that if S is a set with m elements, then Sⁿ has mⁿ elements.

7. Show that the number of functions from a set A of n elements into a set B of m elements is mⁿ.

The most basic applications of the multiplication principle are to permutations and combinations. It is also interesting to note that the multiplication principle is the counting measure analogue of the multiplication rule for conditional probability.

Combinatorics