The Fundamental Counting Principle

Section 3.1 The Fundamental Counting Principle

Subsection 3.1.1 Possibility Trees

Suppose we want to count the number of possible outcomes that can occur. A systematic way of doing this is to use a tree diagram. Each “path” from “root” to “leaf” represents one possible outcome.

Subsection 3.1.2 Multiplication Principle (Fundamental Counting Principle)

Theorem 3.1.1. Fundamental counting principle (FCP).

If there are $n_1$ ways to make choice 1, and $n_2$ ways to make choice 2, then there are $n_1 \cdot n_2$ ways to make both choices together.

The fundamental counting principle is also called the multiplication principle, or the rule of product.

In the language of set theory, if there are $n_1$ distinct objects in one set and $n_1$ distinct objects in another set, then there are $n_1 n_2$ ways to choose one object from each set.

This can be generalized to $k$ choices.

Theorem 3.1.2. Fundamental counting principle.

Let there be $k$ choices, with $n_1$ ways to make choice 1, $n_1$ ways to make choice $2, \dots, n_k$ ways to make choice $k$ (in general for choice $i\text{,}$ there are $n_i$ ways). Then, the number of ways to make the entire sequence of choices is,

\begin{equation*} n_1 n_2 \cdots n_k \end{equation*}

In the language of set theory, if there are $n_1$ distinct objects in set 1, $n_1$ in set $2, \dots, n_k$ in set $k\text{,}$ then there are $n_1 n_2 \cdots n_k$ ways to choose one object from each set.

Corollary 3.1.3.

Let there be $k$ choices with $n$ ways to make each choice. Then, the number of ways to make the sequence of choices is,

\begin{equation*} \underbrace{n \cdot n \cdots n}_{\text{$k$ factors of $n$}} = n^k \end{equation*}

For the FCP to apply, the number of ways to perform each step must be constant, regardless of the choices on the previous steps.

The FCP can be thought of as an axiom, because it is so intuitively true. Any proof of the FCP would simply be an formal proof.

Subsection 3.1.3 Numbers and Letters (PIN codes)

Example 3.1.4.

Consider a pin code on a smartphone or for a bank login. Pin codes are typically made up of 4 digits from 0-9. Determine the number of possible pin codes.

There are 10 options 0-9 for each digit, so there are,

\begin{equation*} 10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10000 \end{equation*}

possible pin codes. With these many options, a criminal with no insight into the numbers chosen would have a difficult time trying to guess the code.

Example 3.1.5.

Customer account “numbers” for a certain company consists of 2 letters followed by 4 numbers. How many different account numbers are possible if repetitions of letters and digits are allowed?

There are 26 ways to choose each letter, and 10 ways to choose each number. Thus, there are,

\begin{equation*} 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 6760000 \end{equation*}

ways to choose all 6 characters.

Example 3.1.6. Postal codes.

A postal code (in Canada) is given by a string of characters of the form $A1A1A1\text{,}$ where each $A$ is any letter, and each 1 is any number. Determine the number of possible postal codes.

There are 26 options for each letter and 10 for each digit. Then, the number of possible postal codes is given by,

\begin{equation*} 26 \cdot 10 \cdot 26 \cdot 10 \cdot 26 \cdot 10 = 26^3 10^3 = 17576000 \end{equation*}

Subsection 3.1.4 Morse Code

Morse code is a method of representing letters and words using a sequence of dots and dashes. It uses up to 4 of these symbols to represent a single letter.

If using a sequence of only 1 symbol, there are 2 sequences (a dot or a dash). If using 2 symbols, there are 2 ways to choose each symbol, so there are $2 \cdot 2 = 2^2 = 4$ total sequences. Continuing, we have,

\begin{equation*} \begin{array}{c|c} \text{\# of symbols} \amp \text{\# of sequences} \\ \hline 1 \amp 2 \\ 2 \amp 2 \cdot 2 = 4 \\ 3 \amp 2 \cdot 2 \cdot 2 = 8 \\ 4 \amp 2 \cdot 2 \cdot 2 \cdot 2 = 16 \end{array} \end{equation*}

If we were limited to a maximum of 3 symbols, we would only have $2 + 4 + 8 = 14$ total sequences, when we need 26 to represent every letter of the alphabet. Using 4 symbols, we have 16 more sequences for a total of $32 > 26$ sequences.

Subsection 3.1.5 Teams and Committees

If a club consists of 10 members, how many different choices of president, vice-president, and secretary are possible?

There are $10 \cdot 9 \cdot 8 = 720$ total arrangements.

Subsection 3.1.6 Other Examples

Example 3.1.7.

Pizza House offers 4 different salads, 5 different kinds of pizza, and 6 different desserts. How many different three-course meals can be ordered?

There are $4 \cdot 5 \cdot 6 = 120$ different meals.

Example 3.1.8.

Determine the number of 5 digit integers such that no consecutive digits are the same.

There are 9 choices for the first digit, as it can be any integer except 0. The second digit can be anything except identical to the first digit, so there are also 9 choices. Similarly, the third digit can be any integer except the second, so there are 9 choices. And so on. Thus, the number of ways is,

\begin{equation*} 9 \cdot 9 \cdot 9 \cdot 9 \cdot 9 = 9^5 = 59049 \end{equation*}

Example 3.1.9. Rooks on a Chessboard.

Determine the number of ways to place $n$ identical rooks on an $n \times n$ chessboard such that no two rooks attack each other.

No two rooks can share a rook or column. There are $n$ rooks, and $n$ rows and columns, so each row and column must contain exactly one rook. For the first column, there are $n$ choices as to which row to place a rook. Once that row is taken, for the second column, there will be $n-1$ choices for the row, and so on. Thus, the number of ways is given by,

\begin{equation*} n(n - 1) \cdots 3 \cdot 2 \cdot 1 = n! \end{equation*}

For a standard $8 \times 8$ chessboard, this means there will be $8!$ ways.

Example 3.1.10.

Determine the number of even 4-digit positive integers.

There are 4 digits to determine. The first digit must be from 1-9 (cannot be zero, otherwise it is a 3-digit number) so there are 9 choices. There are no restrictions on the middle 2 digits, so they have 10 choices each. The last digit must be even for the entire number to be even, so it must be one of 0, 2, 4, 6, 8, and so there are 5 choices. Thus, in total, the number of numbers ig given by,

\begin{equation*} 9 \cdot 10 \cdot 10 \cdot 5 = 4500 \end{equation*}

Example 3.1.11.

Determine the number of four digit positive integers which contain the digit 3 and are divisible by 5.

Four digit numbers cannot start with 0, and numbers divisible by 3 must end in either 0 or 5. Then, there are $9 \cdot 10 \cdot 10 \cdot 2 = 1800$ four digit numbers which are divisible by 5. Also, there are $8 \cdot 9 \cdot 9 \cdot 2 = 1296$ four digit numbers that divisible by 5 but do not contain any 3s. Thus, there are $1800 - 1296 = 504$ four digit numbers that contain at least one 3 and are divisible by 5.