14.3: The Generalized Product Rule

Last updated
Save as PDF

Page ID: 48395

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

In how many ways can, say, a Nobel prize, a Japan prize, and a Pulitzer prize be awarded to \(n\) people? This is easy to answer using our strategy of translating the problem about awards into a problem about sequences. Let \(P\) be the set of \(n\) people taking the course. Then there is a bijection from ways of awarding the three prizes to the set \(P^3 ::= P \times P \times P\). In particular, the assignment:

\[\nonumber \text{“Barak wins a Nobel, George wins a Japan, and Bill wins a Pulitzer prize”}\]

maps to the sequence (Barak, George, Bill). By the Product Rule, we have \(|P^3| = |P|^3 = n^3\), so there are \(n^3\) ways to award the prizes to a class of \(n\) people. Notice that \(P^3\) includes triples like (Barak, Bill, George) where one person wins more than one prize.

But what if the three prizes must be awarded to different students? As before, we could map the assignment to the triple (Bill, George, Barak) \(\in P^3\). But this function is no longer a bijection. For example, no valid assignment maps to the triple (Barak, Bill, Barak) because now we’re not allowing Barak to receive two prizes. However, there is a bijection from prize assignments to the set:

\[\nonumber S = \{(x, y, z) \in P^3 \mid x, y, \text{ and }z \text{ are different people}\}\]

This reduces the original problem to a problem of counting sequences. Unfortunately, the Product Rule does not apply directly to counting sequences of this type because the entries depend on one another; in particular, they must all be different. However, a slightly sharper tool does the trick.

Prizes for truly exceptional Coursework

Given everyone’s hard work on this material, the instructors considered awarding some prizes for truly exceptional coursework. Here are three possible prize categories:

Best Administrative Critique We asserted that the quiz was closed-book. On the cover page, one strong candidate for this award wrote, “There is no book.”

Awkward Question Award “Okay, the left sock, right sock, and pants are in an antichain, but how—even with assistance—could I put on all three at once?”

Best Collaboration Statement Inspired by a student who wrote “I worked alone” on Quiz 1.

Rule 14.3.1 (Generalized Product Rule). Let \(S\) be a set of length-\(k\) sequences. If there are:

\(n_1\) possible first entries,
\(n_2\) possible second entries for each first entry,

\(\quad \vdots\)

\(n_k\) possible \(k\)th entries for each sequence of first \(k - 1\) entries,

then

\[\nonumber |S| = n_1 \cdot n_2 \cdot n_3 \cdots n_k\]

In the awards example, \(S\) consists of sequences \((x, y, z)\). There are \(n\) ways to choose \(x\), the recipient of prize #1. For each of these, there are \(n - 1\) ways to choose \(y\), the recipient of prize #2, since everyone except for person \(x\) is eligible. For each combination of \(x\) and \(y\), there are \(n - 2\) ways to choose \(z\), the recipient of prize #3, because everyone except for \(x\) and \(y\) is eligible. Thus, according to the Generalized Product Rule, there are

\[\nonumber |S| = n \cdot (n-1) \cdot (n-2)\]

ways to award the 3 prizes to different people.

Defective Dollar Bills

A dollar bill is defective if some digit appears more than once in the 8-digit serial number. If you check your wallet, you’ll be sad to discover that defective bills are all-too-common. In fact, how common are nondefective bills? Assuming that the digit portions of serial numbers all occur equally often, we could answer this question by computing

\[\label{14.3.1} \text{fraction of nondefective bills} = \dfrac{\{\text{serial #’s with all digits different}\}}{\{\text{serial numbers}\}}.\]

Let’s first consider the denominator. Here there are no restrictions; there are 10 possible first digits, 10 possible second digits, 10 third digits, and so on. Thus, the total number of 8-digit serial numbers is 10⁸ by the Product Rule.

Next, let’s turn to the numerator. Now we’re not permitted to use any digit twice. So there are still 10 possible first digits, but only 9 possible second digits, 8 possible third digits, and so forth. Thus, by the Generalized Product Rule, there are

\[\nonumber 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 = \dfrac{10!}{2} = \text{1,814,400}\]

serial numbers with all digits different. Plugging these results into Equation \ref{14.3.1}, we find:

\[\nonumber \text{fraction of nondefective bills} = \dfrac{\text{1,814,400}}{\text{100,000,000}} = 1.8144%\]

Chess Problem

In how many different ways can we place a pawn (\(P\)), a knight (\(N\)), and a bishop (\(B\)) on a chessboard so that no two pieces share a row or a column? A valid configuration is shown in Figure 14.1(a), and an invalid configuration is shown in Figure 14.1(b).

Figure 14.1 Two ways of placing a pawn, a knight, and a bishop on a chessboard. The configuration shown in (b) is invalid because the bishop and the knight are in the same row.

First, we map this problem about chess pieces to a question about sequences. There is a bijection from configurations to sequences

\[\nonumber (r_P, c_P, r_N, c_N, r_B, c_B)\]

where \(r_P , r_N\), and \(r_B\) are distinct rows and \(c_P , c_N\), and \(c_B\) are distinct columns. In particular, \(r_P\) is the pawn’s row, \(c_P\) is the pawn’s column, \(r_N\) is the knight’s row, etc. Now we can count the number of such sequences using the Generalized Product Rule:

\(r_P\) is one of 8 rows
\(c_P\) is one of 8 columns
\(r_N\) is one of 7 rows (any one but \(r_P\))
\(c_N\) is one of 7 columns (any one but \(c_P\))
\(r_B\) is one of 6 rows (any one but \(r_P\) or \(r_N\))
\(c_B\) is one of 6 columns (any one but \(c_P\) or \(c_N\))

Thus, the total number of configurations is \((8 \cdot 7 \cdot 6)^2\).

Permutations

A permutation of a set \(S\) is a sequence that contains every element of \(S\) exactly once. For example, here are all the permutations of the set \(\{a, b, c\}\):

\[\begin{aligned} (a, b, c) \quad (a, c, b) \quad (b, a, c) \\ (b, c, a) \quad (c, a, b) \quad (c, b, a) \end{aligned}\]

How many permutations of an \(n\)-element set are there? Well, there are \(n\) choices for the first element. For each of these, there are \(n - 1\) remaining choices for the second element. For every combination of the first two elements, there are \(n - 2\) ways to choose the third element, and so forth. Thus, there are a total of

\[\nonumber n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1 = n!\]

permutations of an \(n\)-element set. In particular, this formula says that there are \(3! = 6\) permutations of the 3-element set \(\{a, b, c\}\), which is the number we found above.

Permutations will come up again in this course approximately 1.6 bazillion times. In fact, permutations are the reason why factorial comes up so often and why we taught you Stirling’s approximation:

\[\nonumber n! \sim \sqrt{2 \pi n}\left(\dfrac{n}{e}\right)^n\]