20.3: Multiplication Rule

Example \(\PageIndex{1}\): Counting a small Cartesian product.

What is \(\vert A \times B \vert\) 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 \times B\) and counting them.

\begin{align*} A \times B & = \{ (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1),\\ & \quad (2,-1), (2,0), (2,1), (3,-1), (3,0), (3,1) \} \end{align*}
So \(\vert A \times B \vert = 12\text{.}\)

Example \(\PageIndex{2}\): Counting a large Cartesian product.

What is \(\vert C \times D \vert\) for \(C = \{ a,b,c,\ldots,z \}\) and \(D = \{0,1,2,\cdots,99 \}\text{?}\)

Solution

Writing out all the elements of \(C \times D\) and then counting them all seems like a lot of work. Instead, using our experience from Worked Example \(\PageIndex{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 \(\vert D \vert\) elements of \(C \times D\) with \(c\) as the first coordinate, and there are \(\vert C \vert\) such groupings of elements from \(C \times D\text{.}\) So we arrive at

\begin{equation*} \vert C \times D \vert = \vert C \vert \cdot \vert D \vert = 26 \cdot 100 = 2600 \text{.} \end{equation*}

Checkpoint \(\PageIndex{1}\)

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

Theorem \(\PageIndex{1}\): Multiplication Rule.

If there are \(m\) ways to perform task \(S\) and \(n\) ways to perform task \(T\text{,}\) then there are \(m n\) ways to perform task \(S\) followed by task \(T\text{.}\)

Warning \(\PageIndex{1}\)

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 \(\PageIndex{3}\): Counting Cartesian product elements by constructing an arbitrary element.

To create a specific example of an element from \(A \times 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 = \vert A \vert\) ways to perform task \(S\) and \(n = \vert B \vert\) ways to perform task \(T\text{.}\) Therefore, the Multiplication Rule says there are \(m n\) ways to construct an element of \(A \times B\text{,}\) which means \(\vert A\times B \vert = m n\text{.}\)

Example \(\PageIndex{4}\): 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 \(\PageIndex{1}\)

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

Example \(\PageIndex{5}\): Cardinality of Cartesian product of many sets.

If \(A_1,A_2,\ldots,A_m\) are finite sets with \(\vert A_j \vert= m_j\text{,}\) then

\begin{equation*} \vert A_1 \times A_2 \times \cdots \times A_\ell \vert = m_1 m_2 \cdots m_\ell \text{.} \end{equation*}

Example \(\PageIndex{6}\): Words of a given length.

Recall that, given alphabet \(\Sigma\) and number \(n \in \mathbb{N} \text{,}\) \(\Sigma^\ast_n\) is the set of words of length \(n\text{.}\) If \(\vert \Sigma \vert= m\text{,}\) what is \(\vert \Sigma^\ast_n \vert\text{?}\)

Solution

To construct a specific example word \(w \in \Sigma^\ast_n\text{,}\) there are:

• \(m\) ways to choose the first letter,
• \(m\) ways to choose the second letter,
• …,
• \(m\) ways to choose the \(n^{th}\) letter.

So there are

\begin{equation*} \underbrace{m \cdot m \cdot m \cdot \cdots \cdot m}_{n \text{ factors}} = m^n \end{equation*}
ways to construct \(w\text{.}\) We conclude \(\vert \Sigma^\ast_n \vert = m^n\text{.}\)

Example \(\PageIndex{7}\): Words with no repeated letters.

Suppose \(\vert \Sigma \vert = 5\text{.}\) How many words in \(\vert \Sigma^\ast_5 \vert\) have no repeated letters? (That is, in which no two letters are the same?)

Solution

To construct a specific example word \(w \in \Sigma^\ast_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 \(\PageIndex{4}\), 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.

Example \(\PageIndex{8}\): Palindromes.

Let \(\Sigma = \{a, b, c, \ldots, y, z \} \text{.}\) How many palindromes \(w\) with \(3 \le \vert w \vert \le 6\) are there in \(\Sigma^\ast\text{?}\)

Solution

Break into cases based on the length of \(w\text{.}\)

Case \(\vert w \vert = 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 \(\vert w \vert = 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 \(\vert w \vert = 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 \(\vert w \vert = 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 & = 26^2(1+1+26+26) \\ & = 54 \cdot 26^2 \\ & = 36,504 \end{align*}
as the number of palindromes length \(3\) to \(6\text{.}\)

Example \(\PageIndex{9}\)

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 \(f: A \rightarrow 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 \(\vert B \vert = 5\) ways. So the number of functions is \(5^3 = 125\text{.}\)

Number of injections.
An injection \(f: A \hookrightarrow 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 \(\vert B \vert = 5\) choices. Second step has \(\vert B \setminus \{f(a)\} \vert = 4\) choices. Third step has \(\vert B \setminus \{f(a),f(b)\} \vert = 3\) choices. So the number of injections is \(5 \cdot 4 \cdot 3 = 60\text{.}\)

A look ahead.

Notice that the number of injections has turned out to be

\begin{equation*} \dfrac{\vert B \vert!}{(\vert B \vert - \vert A \vert)!} \text{.} \end{equation*}
We will understand better how this formula arises in Section 21.4.

Number of surjections.
Suppose \(f: A \rightarrow B\text{.}\) Since \(\vert A \vert = 3\text{,}\) the largest that \(\vert f(A)\vert\) can be is \(3\text{,}\) which occurs when \(f\) is injective. However, even in such a largest case it is still smaller then \(\vert B \vert\text{,}\) so no surjections exist. That is, the number of surjections is \(0\text{.}\)