3.1: The Multiplication Rule for Counting
- Page ID
- 182262
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\(\newcommand{\longvect}{\overrightarrow}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Apply the Multiplication Rule for Counting to solve problems.
One of the first bits of mathematical knowledge children learn is how to count objects by pointing to them in turn and saying: “one, two, three, …” That’s a useful skill. Still, when the number of things that we need to count grows large, that method becomes onerous (or, for very large numbers, impossible for humans to accomplish in a typical human lifespan). So, mathematicians have developed shortcuts to counting big numbers. These techniques fall under the mathematical discipline of combinatorics, which is devoted to counting.
Multiplication as a Combinatorial Shortcut
One of the first combinatorial shortcuts to counting students learn in school has to do with areas of rectangles. If we have a set of objects to be counted that can be physically arranged into a rectangular shape, then we can use multiplication to do the counting for us. Consider this set of objects (Figure \(\PageIndex{2}\) ):
Indeed, we can count them by pointing and running through the numbers, but it’s more efficient to group them (Figure \(\PageIndex{3}.\))
Figure \(\PageIndex{3}\)
If we group the balls by \(4\)s, we see that we have \(6\) groups (or, we can see this arrangement as \(4\) groups of \(6\) balls). Since multiplication is repeated addition (i.e., \(6 \times 4=4+4+4+4+4+4\), we can use this grouping to quickly see that there are \(24\) balls.
Let’s generalize this idea a little bit. Let’s say that we’re visiting a bakery that offers customized cupcakes. For the cake, we have three choices: vanilla, chocolate, and strawberry. Each cupcake can be topped with one of four types of frosting: vanilla, chocolate, lemon, and strawberry. How many different cupcake combinations are possible? We can think of laying out all the possibilities in a grid, with cake choices defining the rows and frosting choices defining the columns (Figure \(\PageIndex{4}.\))
Since there are \(3\) rows (cakes) and \(4\) columns (frostings), we have possible combinations. This is the reasoning behind the Multiplication Rule for Counting, which is also known as the Fundamental Counting Principle. This rule says that if there are ways to accomplish one task and ways to accomplish a second task, then there are ways to accomplish both tasks. We can tackle additional tasks by multiplying the number of ways to accomplish those tasks using our previous product.
Let's ask to choose one item from each of two separate categories where there are \(m\) items in the first category and \(n\) items in the second category. The total number of available choices is \(m\times n\).
To use the Multiplication rule for counting, you need to look for two things
- How many groups are you choosing items from?
- How many ways can you choose each item from that group?
For example, in the above figure \(\PageIndex{4}\), there are two groups: "cake group" and "frosting group". In the cake group, we can choose any one item at a time out of \(3\) and in the frosting group, we can choose any one item at a time out of \(4\).
Example \(\PageIndex{1}\) Using the Multiplication Rule for Counting for 3 Groups
At I Love Food restaurant, you can choose from \(5\) appetizers, \(13\) entrees, and \(3\) desserts. How many three-course meals can you order?
- Answer
-
Since there are three groups "appetizers" (\(5\) items), "entrees" (\(13\)) items, and "desserts (\(3\)) items.
Appetizers can be chosen in \(5\) different ways.
Entrees can be chosen in \(13\) different ways.
Desserts can be chosen in \(3\) different ways.
So, you can order a three-course meal \(5\times 13\times3= 195\) in different ways.
Example \(\PageIndex{2}\) Using the Multiplication Rule for Counting for 4 Groups
The University Combinatorics Club has \(31\) members: \(8\) seniors, \(7\) juniors, \(5\) sophomores, and \(11\) first-years. How many possible \(4\)-person committees can be formed by selecting one member from each class?
- Answer
-
Since we have four groups: seniors, juniors, sophomores, and first-year students. And number of choices: \(8\) choices for the senior, \(7\) choices for the junior, \(8\) for the sophomore, and \(11\) for the first year, there are
\[8\times 7\times 5\times 11= 3,080\nonumber\]
There are \(3,080\) different ways to fill out the committee members.
Example \(\PageIndex{3}\): Using the Multiplication Rule for Counting for More Groups
- The standard license plates for vehicles in a certain state are six characters: \(3\) letters followed by \(3\) digits. There are \(26\) letters in the alphabet and \(10\) digits (\(0\) through \(9\)) to choose from. How many license plates can be made using this format?
- \(10\) people are to be seated in a row of \(10\) chairs. How many different seating arrangements are there?
- Answer
-
- Since we are choosing \(6\) characters (items): There are \(6\) group: First three group are all \(26\) alphabets and last \(3\) group are \(10\) number. Since there are \(26\) different letters and \(10\) different digits. Each of the first three characters can be selected in \(26\) different ways, and the last three can be chosen in \(10\) different ways. (Note that there is no restriction. Digits and letters can be repeated. The total number of possible license plates \[26\times26\times26\times10\times10\times10=17,576,000 \nonumber\]
- Here we have to choose \(10\) items (person) for each chair. So we consider there are ten groups. In the first chair, there are \(10\) choices. Since one person (the first person that is selected) can sit in that chair, there are now \(9\) persons left, and there are \(9\) choices for the second chair (in other words, we have \(9\) items in this group), and so on. The total number of setting arrangements will be \[10\times9\times8\times7\times5\times6\times4\times3\times2\times1=3,628,800 \nonumber\]
Example \(\PageIndex{4}\): Using the Multiplication Rule for Counting for More Groups
A quiz consists of \(3\) true-or-false questions. In how many ways can a student answer the quiz?
- Answer
-
There are \(3\) questions. Each question has \(2\) possible answers (true or false). There are two ways to answer each of the three questions. So, the quiz can be answered in \(2\times 2\times 2=8\) different ways.
Example \(\PageIndex{5}\)
How many license plates can one create using the DDLLLL format, in which D stands for any odd digit and L stands for any capital letter A-N?
- If the repetition of digits and letters is allowed.
- If the repetition of digits is allowed, but the repetition of letters is not allowed.
- If the repetition of digits is not allowed, but the repetition of letters is allowed.
- If the repetition of digits and letters is not allowed.
- Answer
-
There are a total of \(6\) symbols on the license plate. The first two are odd digits, and the last \(4\) are alphabet from A to N.
- Note that repetition is allowed. Since there are \(5\) odd digits, the number of choices for the first two D is \(5,\) and since there are \(14\) capital letters A-N, the number of choices for the last four L is \(14,\) thus:\begin{aligned}5\times5\times14\times14\times14\times14=960,400\end{aligned}
- If the repetition of digits is allowed, but the repetition of letters is not allowed.\begin{aligned}5\times5\times14\times13\times12\times11=600,600\end{aligned}
- If the repetition of digits is not allowed, but the repetition of letters is allowed.\begin{aligned}5\times4\times14\times14\times14\times14=768,320\end{aligned}
- If the repetition of digits and letters is not allowed.\begin{aligned}5\times4\times14\times13\times12\times11=480,480\end{aligned}