Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 4.1.2 Product Rule

Example 4.1.2.2. Chairs.

Suppose auditorium chairs are labeled with an uppercase letter followed by a positive integer not exceeding \(100\text{.}\) How many different labels are possible?
🔗
Solution.
We can view this problem as counting they ways to assign a label to a chair. We proceed by constructing tasks.
Assign a letter
🔗
There are \(26\) ways to assign the letter.
🔗
Assign an integer
🔗
For each choice of letter, there are \(100\) ways to assign the integer.
🔗
By the Product Rule, there are \(26 \cdot 100 = 2600\) different ways to assign a label. Hence there are \(2600\) different labels.
🔗
🔗
🔗
The Product Rule generalizes to \(m\) tasks. Suppose a procedure can be carried out by performing tasks \(T_1, T_2, \dots, T_k\) tasks in sequence. If each task \(T_i\) can be done in \(n_i\) ways regardless of how the previous tasks were done, then there are \(n_1n_2 \cdots n_m\) ways to carry out the procedure.
🔗

Example 4.1.2.3. Bit strings of length \(8\).

How many bit strings of length \(8\) are there?
🔗
Solution.
We just have to choose each bit, so there are \(8\) tasks. Each bit can be \(0\) or \(1\text{,}\) so there are \(2\) ways to choose each bit. The Product Rule says there are \(2^8 = 256\) such bit strings.
🔗
🔗
🔗

Example 4.1.2.4. Bit strings with start \(1\).

How many bit strings of length \(8\) that start with \(1\) are there?
🔗
Solution.
The first bit must be \(1\text{.}\) We are left with choosing the remaining bits, so there are 7 tasks. There are \(2\) ways to choose each of the remaining \(7\) bits. The Product Rule says there are \(2^7 = 128\) such bit strings.
🔗
🔗
🔗

Example 4.1.2.5. Bit strings with end \(00\).

How many bit strings of length \(8\) that end with \(00\) are there?
🔗
Solution.
The last two bits must be \(00\text{.}\) We are left with choosing the remaining bits, so there are 6 tasks. There are \(2\) ways to choose each of the remaining \(6\) bits. The Product Rule says there are \(2^6 = 64\) such bit strings.
🔗
🔗
🔗

Example 4.1.2.6. Bit strings with start \(1\) and end \(00\).

How many bit strings of length \(8\) that start with \(1\) and end with \(00\) are there?
🔗
Solution.
The first bit must be \(1\) and the last two must be \(00\text{.}\) We are left with choosing the remaining bits, so there are 5 tasks. There are \(2\) ways to choose each of the remaining \(5\) bits. The Product Rule says there are \(2^5 = 32\) such bit strings.
🔗
🔗
🔗

Example 4.1.2.7. Birthdays.

Suppose there are 22 people in the class. How likely is it that two share a birthday?
🔗
Solution.
First, let’s count the number of ways the birthdays could be arranged, assuming no one was born on February 29. We order the 22 people, and break this own into 22 tasks. The \(i\) th task is choosing a birthday for the \(i\) th person. There are 365 ways to complete each task, regardless of how previous tasks were done. By the Product Rule, the number of birthday arrangements is
\begin{equation*} 365^{22} \approx 2.346621351 \times 10^{56}. \end{equation*}
🔗
Next, let’s compute the number of ways the birthdays could be arranged, assuming no one was born on February 29 and no two people share a birthday. Again, we break this into 22 tasks, where the \(i\) th task is choosing the birthday for the \(i\) th person. The difference is in the number of ways to complete each task. There are 365 was to complete the first task. There are only 364 ways to complete the second task, since we cannot choose the same birthday as the first person. Notice that the number of ways does not depend on what day was chosen for the first person. Similarly, there are 363 ways to complete the second task, and so on. In general, there are \(365 - (i - 1)\) ways to complete the \(i\) th task. By the Product Rule, the number of birthday arrangements so that no two share a birthday is
\begin{equation*} \underbrace{365 \cdot 364 \cdot 363 \dots 344}_{22\text{ terms }} \approx 1.230344586 \times 10^{56}. \end{equation*}
🔗
The likelihood of an event happening (assuming all possible events are equally likely) is the ratio of the number of ways the particular event can occur divided by the total number of events. We can compute that
\begin{equation*} \frac{1.230344586 \times 10^{56}}{2.346621351 \times 10^{56}} \approx 0.5243. \end{equation*}
That means if birthdays are arranged randomly, there is a 52% chance that no two people in the class share a birthday. This is the largest gathering where that is greater than 50%. If we do the same computation with twice as many people, there is only a 6.7% chance that no one shares a birthday.
🔗
🔗
🔗

Proof.

Label the elements of \(A\text{,}\)
\begin{equation*} A = \{a_1, a_2, \dots, a_n\}. \end{equation*}
Note that we uniquely determine a subset of \(A\) by specifying the elements that are in the subset.
🔗
We specify a subset of \(A\) by completing \(n\) tasks, where the \(i\) th task is deciding whether or not \(a_i\) is in the subset. There are two ways to complete each task, regardless of how previous tasks are completed. By the Product Rule, there are \(2^n\) different subsets of \(A\text{.}\)
🔗
🔗

Example 4.1.2.9. License plates.

How many license plates can be made, if the license plate consists of \(3\) upper case letters followed by \(4\) one digit numbers.
🔗
Solution.
We view this as a sequence of 7 tasks: choose a letter, choose a letter, choose a letter, choose a digit, choose a digit, choose a digit, and choose a digit. There are \(26\) letters and \(10\) digits, so there are \(26\) ways to choose a letter and 10 ways to choose a digit. The number of ways to complete each task does not depend on how the previous tasks were completed. Thus by the Product Rule, there are
\begin{equation*} 26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10 \cdot 10 = 175760000 \end{equation*}
different license plates.
🔗
🔗
🔗

Example 4.1.2.10. Number of functions.

Let \(A = \{a, b, c\}\text{,}\) and let \(B = \{1, 2, 3, 4, 5\}\text{.}\)
  1. How many functions \(f \colon A \to B\) are there?
    🔗
    🔗
  2. How many injective functions \(f \colon A \to B\) are there?
    🔗
    🔗
  3. How many surjective functions \(f \colon A \to B\) are there?
    🔗
    🔗
🔗
Solution.
  1. We need to choose a value for \(f(x)\) for each \(x\) in \(A\text{.}\) There are \(5\) choices for \(f(a)\text{,}\) \(5\) choices for \(f(b)\text{,}\) and \(5\) choices for \(f(c)\text{.}\) By the Product Rule, there are \(5\cdot 5 \cdot 5 = 125\) functions from \(A\) to \(B\text{.}\)
    🔗
    🔗
  2. We need to choose a value for \(f(x)\) for each \(x\) in \(A\text{,}\) but we need to do so in a way that produces an injective function. There are \(5\) choices for \(f(a)\text{.}\) There are \(4\) choices for \(f(b)\text{,}\) since we cannot choose the same value as was chosen for \(f(a)\text{.}\) Similarly, there are \(3\) choices for \(f(c)\text{,}\) since we must avoid \(f(a)\) and \(f(b)\text{.}\) By the Product Rule, there are \(5\cdot 4 \cdot 3 = 60\) injective functions from \(A\) to \(B\text{.}\)
    🔗
    🔗
  3. Since \(\size{B} \gt \size{A}\text{,}\) there are no surjective functions from \(A\) to \(B\text{.}\)
    🔗
    🔗
🔗
🔗
🔗
PrevTopNext