Sum Rule

\(\newcommand{\im}{{\mathrm{im}}} \newcommand{\given}{{\, :\,}} \newcommand{\hanoi}{\mathrm{hanoi}} \newcommand{\lcm}{{\mathrm{lcm}}} \newcommand{\ID}{{\mathrm{ID}}} \newcommand{\chr}{{\mathtt{chr}}} \newcommand{\ord}{{\mathtt{ord}}} \newcommand{\set}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\seq}[2]{( #1 )_{#2}} \newcommand{\gr}[1]{\left( #1 \right)} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\size}[1]{\# #1} \newcommand{\id}[1]{\mathrm{id}_{#1}} \newcommand{\ip}[1]{\left\langle #1 \right\rangle} \newcommand{\floor}[1]{\left\lfloor #1\right\rfloor} \newcommand{\ceiling}[1]{\left\lceil #1\right\rceil} \newcommand{\indemph}[1]{{\textbf{\emph{#1}}\index{#1}}} \renewcommand{\implies}{\to} \renewcommand{\iff}{\leftrightarrow} \newcommand{\lxor}{\oplus} \newcommand{\cP}{\wp} \newcommand{\pset}{\cP} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\NN}{\mathbb{N}} \newcommand{\CC}{\mathbb{C}} \newcommand{\RR}{\mathbb{R}} \newcommand{\barr}[1]{\overline{#1}} \newcommand{\sage}{\textsc{Sage}} \newcommand{\magma}{\textsc{Magma}} \newcommand{\bob}{\text{Bob}} \newcommand{\true}{\text{T}} \newcommand{\false}{\text{F}} \newcommand{\ahat}{\hat{a}} \newcommand{\ah}{\ahat} \newcommand{\bhat}{\hat{b}} \newcommand{\abar}{\bar{a}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cF}{\mathcal{F}} \newcommand{\cW}{\mathcal{W}} \newcommand{\todo}[1]{{\color{red} TODO: #1}} \renewcommand{\div}{\operatorname{div}} \newcommand{\gexp}[3]{#1^{#2 #3}} \newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}} \newcommand{\glog}[3]{\log_{#1}^{#3}#2} \def\dbend{{!!!}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Subsection 4.1.3 Sum Rule

Theorem 4.1.3.1. Sum Rule.

If a task can be done in either one of $n_1$ ways or $n_2$ ways, where none of the set of $n_1$ ways is the same as any of the set of $n_2$ ways. Then there are $n_1 + n_2$ ways to do the task.

🔗

The Sum Rule can be generalized. If a task can be done in one of $n_1$ ways, or in one of $n_2$ ways, \dots, or in one of $n_m$ ways, where none of the set of $n_i$ ways is the same as any of the set of $n_j$ ways, for all $i \neq j\text{,}$ then there are $n_1 + n_2 + \dots + n_m$ ways to complete the task.

🔗

Example 4.1.3.2. Goats and Sheep.

Suppose there are 10 goats and 15 sheep in a certain village.

Suppose a gift of one animal (goat or sheep) is to be given to a visiting dignitary. How many ways are there to select a gift?
🔗

🔗
Suppose it is decided instead that the gift should consist of one goat and one sheep. How many ways are there to select a gift?
🔗

🔗

🔗

Solution.

There are 10 ways to select a goat and 15 ways to select a sheep, and none of the ways that select a goat is the same as any of the ways that select a sheep. By the Sum Rule, there are $10 + 15 = 25$ ways to select the gift.
🔗

🔗
The procedure of selecting a gift can be broken down into two tasks: select the goat and select the sheep. The number of ways to select the sheep does not depend on which goat was selected. By the Product rule, there are $10 \cdot 15 = 150$ ways to select a gift.
🔗

🔗

🔗

Prev Top Next