The Multiplication Rule

Theorem 6.1.1 The Number of Elements in a List

If m and n are integers and m £ n, then there are n – m + 1 integers from m to n inclusive.

Proof : Let m be any integer. We prove the theorem by mathematical induction on n.

Basis Step: The formula is true for n = m: There is just one integer, m, from m to m inclusive. 1 = m – m + 1.

Inductive Step: If the formula is true for n = k, then it is true for n = k + 1: Suppose that the number of integers from m to k inclusive is k – m + 1. [This is the inductive hypothesis.] We must show that the number of integers from m to k + 1 inclusive is equal to ((k + 1) – m + 1). We have,

m, m + 1, m + 2, …, k, (k + 1) = (k + 1) – m + 1.

To count the LHS we utilize the inductive hypothesis for terms m to k inclusive,

(k – m + 1) + 1 = (k + 1) – m + 1.

By the commutative and associative properties,

(k + 1) – m + 1 =(k + 1) – m + 1,

As was to be shown.

Theorem 6.2.1 The Multiplication Rule

If an operation consists of k steps and

the first step can be performed in n1 ways,

the second step can be performed in n2 ways, …,

the kth step can be performed in nk ways, (regardless of how the preceding steps were performed),

then the entire operation can be performed in n1 × n2 × , …× nk ways.

Count
What is the value of count after the following code has been executed?

int count = 0;

 

 

for (int i1 = 1; i1 £ j; i1++)

 

 

 

for (int i2 = 1; i2 £ k; i2++)

 

 

 

for (int i3 = 1; i3 £ l; i3++)

 

 

 

count++;

 

Solution
Each time the nested loop is traversed, count is incremented. The number of ways to perform traversal of the outer loop is j, the number of ways to perform traversal of the middle loop is k, and the number of ways to perform traversal of the inner loop is l. So by the product rule the value of count after executing this code would be j× k× l.

Consider the above code with the following changes: int i1 = 3; int i2 = 4; int i3 = 5; j = 20; k = 30; and l = 40. What would the value of count be after executing the code?

Solution
The outer loop runs 20 - 3 + 1 = 18 times, the middle loop runs 30 - 4 + 1 = 27 times, and the inner loop runs 40 - 5 + 1 = 36 times. So we have count = 18× 27× 36 = 17496. (Contrast this code with the nested loops in Example 9.3.2 noting the dependence of steps and why in one case we use the multiplication rule but not in the other case.)

Example 6.2.2 Number of Personal Identification Numbers (PINS)

A typical PIN is a sequence of 4 symbols chosen from the 26 letters of the alphabet and the 10 digits. With repetition allowed how many different PINS are there?

Solution: Consider the multistep process

  1. Choose the first symbol.
  2. Choose the second symbol.
  3. Choose the third symbol.
  4. Choose the fourth symbol.

There is a fixed number of ways to perform each step, regardless of how preceding steps were performed, so there are 36 × 36 × 36 × 36 = 364 = 1,679,616 PINS.

Example 6.2.4 Number of PINS without Repetition

Solution: Again consider the multistep process

  1. Choose the first symbol. (36 choices)
  2. Choose the second symbol. (35 choices)
  3. Choose the third symbol. (34 choices)
  4. Choose the fourth symbol. (33 choices)

There is a fixed number of ways to perform each step, regardless of how preceding steps were performed, so there are 36 × 35 × 34 × 33 = 36!/(36 – 4)! = 1,413,720 PINS.

The probability that a PIN chosen at random contains no repeated symbol is 1,413,720/1,679,616 » .8417.

Counting Subsets of a Finite Set
Use the product rule to show that the number of different subsets of a finite set S is 2|s|.

Solution: We have previously proven that there are 2n elements in the power set of a set with cardinality n. For a different approach, consider the one-to-one correspondence between subsets of S and bit strings (each element takes on a value of 0 or 1) of length |S|. A susbset of S is associated with the bit string with a 1 in the ith position if the ith element in the list is in the subset. By the multiplication rule, there are 2|s| bit strings of length |S|. Therefore, |P(S)| = 2|s|.

Example Number of reflexive relations on a set with n elements.

Solution: There are n times n ordered pairs in A X A. For a relation R to be reflexive each of the n ordered pairs (a, a) must be in R. Each of the other n(n-1) ordered pairs of the form (a, b) where a does not equal b may or may not be in R. By the multiplication rule there are 2n(n-1) reflexive relations.

Counting problems can be solved using trees. We use a branch to represent each possible choice and represent the possible outcomes by the leaves (or terminal vertices).

Example How many bit strings of length four do not have two consecutive 0s?

Clearly, there are eight bit strings of length four that do not have consecutive 0s.

Example Each digit in a base B takes on a value from 0 to B-1, so there are B digit symbols in a given base. Bases other than 10 can be considered codes. A base-B number is expressed as a string of digits

an…a2a1a0.a -1a -2…a -k

The numeric value of this number is

There are B choices for each symbol, so how many codes are there of length N, where N = -k…n inclusive? (Note: you will have to be careful deducing the value for N, try it with abc.def).

Solution
BN.

How many 3 digit binary codes are there?
How many 4 digit binary codes are there?
How many 4 digit octal codes are there?
How many 4 digit hexadecimal codes are there?
How many 4 letter words AAAA to ZZZZ are there?