Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Section 20.3 Multiplication rule

Worked Example 20.3.1. Counting a small Cartesian product.

What is \(\card{A \cartprod B}\) for \(A = \{ 0, 1, 2, 3 \}\) and \(B = \{ -1, 0, 1 \}\text{?}\)
Solution.
We can solve this by just writing out the elements of \(A \cartprod B\) and counting them.
\begin{align*} A \cartprod B \amp = \{ (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1),\\ \amp \phantom{ = \{ } \quad (2,-1), (2,0), (2,1), (3,-1), (3,0), (3,1) \} \end{align*}
So \(\card{A \cartprod B} = 12\text{.}\)

Worked Example 20.3.2. Counting a large Cartesian product.

What is \(\card{C \cartprod D}\) for \(C = \{ a,b,c,\dotsc,z \}\) and \(D = \{0,1,2,\cdots,99 \}\text{?}\)
Solution.
Writing out all the elements of \(C \cartprod D\) and then counting them all seems like a lot of work. Instead, using our experience from Worked Example 20.3.1, notice that we usually perform the task of writing the elements of a Cartesian product in a pattern to make sure we get them all. One-by-one we pick a single element of the first set \(C\text{,}\) and pair it up with every element of the second set \(D\text{.}\) From this pattern we see that for each \(c \in C\text{,}\) there are \(\card{D}\) elements of \(C \cartprod D\) with \(c\) as the first coordinate, and there are \(\card{C}\) such groupings of elements from \(C \cartprod D\text{.}\) So we arrive at
\begin{equation*} \card{C \cartprod D} = \card{C} \cdot \card{D} = 26 \cdot 100 = 2600 \text{.} \end{equation*}

Checkpoint 20.3.3.

For sets \(X\) and \(Y\text{,}\) define an equivalence relation on \(X \cartprod Y\) whose equivalence classes partition \(X \cartprod Y\) in the manner described in the provided solution to Worked Example 20.3.2. Then describe how the number of classes and the number of objects in each class correspond to \(\card{X}\) and \(\card{Y}\text{.}\)

Warning 20.3.5.

The Multiplication Rule only applies to consecutive tasks \(S,T\) such that the number of ways of performing task \(T\) is independent of the choice made in performing task \(S\text{.}\)

Example 20.3.6. Counting Cartesian product elements by constructing an arbitrary element.

To create a specific example of an element from \(A \cartprod B\text{,}\) we must first choose an element of \(A\) to be the first coordinate (task \(S\)), then choose an element of \(B\) to be the second coordinate (task \(T\)). There are \(m = \card{A}\) ways to perform task \(S\) and \(n = \card{B}\) ways to perform task \(T\text{.}\) Therefore, the Multiplication Rule says there are \(m n\) ways to construct an element of \(A \cartprod B\text{,}\) which means \(\card{A\cartprod B} = m n\text{.}\)

Example 20.3.7. Choosing candidates.

Suppose you are a casting director and need to select both a primary actor and an understudy for the lead role in a play. If \(n\) actors audition for the role, then there are \(n\) different ways to select the primary actor. Once this choice is made, there remain \(n-1\) different ways to the select the understudy. Hence there are \(n (n - 1)\) ways to cast the role.
Now, the actual pool of candidates for understudy will differ based on which actor is offered the lead role. However, no matter who is chosen for the lead, the number of remaining candidates for understudy is the same.

Note 20.3.8.

We may extend the Multiplication Rule to any (finite) number of consecutive tasks.

Example 20.3.9. Cardinality of Cartesian product of many sets.

If \(A_1,A_2,\dotsc,A_m\) are finite sets with \(\card{A_j} = m_j\text{,}\) then
\begin{equation*} \card{A_1 \cartprod A_2 \cartprod \dotsb \cartprod A_\ell} = m_1 m_2 \dotsm m_\ell \text{.} \end{equation*}

Worked Example 20.3.10. Words of a given length.

Recall that, given alphabet \(\Sigma\) and number \(n \in \N\text{,}\) \(\words{\Sigma}_n\) is the set of words of length \(n\text{.}\) If \(\card{\Sigma} = m\text{,}\) what is \(\card{\words{\Sigma}_n}\text{?}\)
Solution.
To construct a specific example word \(w \in \words{\Sigma}_n\text{,}\) there are:
  • \(m\) ways to choose the first letter,
  • \(m\) ways to choose the second letter,
  • …,
  • \(m\) ways to choose the \(\nth\) letter.
So there are
\begin{equation*} \underbrace{m \cdot m \cdot m \cdot \dotsb \cdot m}_{n \text{ factors}} = m^n \end{equation*}
ways to construct \(w\text{.}\) We conclude \(\card{\words{\Sigma}_n} = m^n\text{.}\)

Worked Example 20.3.11. Words with no repeated letters.

Suppose \(\card{\Sigma} = 5\text{.}\) How many words in \(\card{\words{\Sigma}_5}\) have no repeated letters? (That is, in which no two letters are the same?)
Solution.
To construct a specific example word \(w \in \words{\Sigma}_5\) in which no two letters are the same, there are
  • \(5\) ways to choose the first letter,
  • \(4\) remaining ways to choose the second letter,
  • \(3\) remaining ways to choose the third letter,
  • \(2\) remaining ways to choose the fourth letter, and
  • only \(1\) remaining way to choose the last letter.
So there are
\begin{equation*} 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120 \end{equation*}
ways to construct \(w\text{.}\)
Similar to Example 20.3.7, while the actual pool of candidates for the next letter at each step will differ based on which letters have been chosen already, the number of remaining letters is always independent of which letters have actually been chosen so far. So the Multiplication Rule can be applied to this problem exactly as we have applied it.

Worked Example 20.3.12. Palindromes.

Let \(\Sigma = \EngAlphabet\text{.}\) How many palindromes \(w\) with \(3 \le \length{w} \le 6\) are there in \(\words{\Sigma}\text{?}\)
Solution.
Break into cases based on the length of \(w\text{.}\)

Case \(\length{w} = 3\).

Once we choose the first letter, the last is chosen for us, but we are still free to choose the middle letter. So there are \(26^2\) palindromes of length \(3\text{.}\)

Case \(\length{w} = 4\).

Once we choose the first two letters, the last two are chosen for us. So there are also \(26^2\) palindromes of length \(4\text{.}\)

Case \(\length{w} = 5\).

Once we choose the first two letters, the last two are chosen for us, but we are still free to choose the middle letter. So there are \(26^3\) palindromes of length \(5\text{.}\)

Case \(\length{w} = 6\).

Once we choose the first three letters, the last three are chosen for us. So there are also \(26^3\) palindromes of length \(6\text{.}\)

Total.

Applying the Addition Rule to these non-overlapping cases, we obtain
\begin{align*} 26^2 + 26^2 + 26^3 + 26^3 \amp = 26^2(1+1+26+26) \\ \amp = 54 \cdot 26^2 \\ \amp = 36,504 \end{align*}
as the number of palindromes length \(3\) to \(6\text{.}\)

Worked Example 20.3.13.

Set \(A = \{a,b,c\}\) and \(B = \{0,1,2,3,4\}\text{.}\) How many functions \(A \to B\) exist? How many of these are injections? How many are surjections?
Solution.

Number of functions.

A function \(\funcdef{f}{A}{B}\) can be constructed in three steps: choose \(f(a)\text{,}\) then choose \(f(b)\text{,}\) then choose \(f(c)\text{.}\) Each of the steps can be carried out in \(\card{B} = 5\) ways. So the number of functions is \(5^3 = 125\text{.}\)

Number of injections.

An injection \(\ifuncdef{f}{A}{B}\) can be constructed in three steps: choose \(f(a)\text{,}\) then choose \(f(b)\) to be different from \(f(a)\text{,}\) then choose \(f(c)\) to be different from both \(f(a)\) and \(f(b)\text{.}\) First step has \(\card{B} = 5\) choices. Second step has \(\card{ B \relcmplmnt \{f(a)\} } = 4\) choices. Third step has \(\card{ B \relcmplmnt \{f(a),f(b)\} } = 3\) choices. So the number of injections is \(5 \cdot 4 \cdot 3 = 60\text{.}\)

Number of surjections.

Suppose \(\funcdef{f}{A}{B}\text{.}\) Since \(\card{A} = 3\text{,}\) the largest that \(\card{f(A)}\) can be is \(3\text{,}\) which occurs when \(f\) is injective. However, even in such a largest case it is still smaller then \(\card{B}\text{,}\) so no surjections exist. That is, the number of surjections is \(0\text{.}\)
<Prev^TopNext>