Principle of Inclusion-Exclusion

Skip to main content

\(\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.4 Principle of Inclusion-Exclusion

Definition 4.1.4.1. Principle of Inclusion-Exclusion.

If a task can be done in \(n_1\) ways or \(n_2\) ways, then the number of ways to do the task is \(n_1 + n_2 - k\text{,}\) where \(k\) is the number of ways to do the task that is common to the \(n_1\) and \(n_2\) ways.

The Principle of Inclusion-Exclusion s sometimes called the Subtraction Rule .

Example 4.1.4.2. Bit strings with start \(1\) or end \(00\).

How many bit strings of length \(8\) are there that start with \(1\) or end with \(00\text{?}\)

Solution.

From Example 4.1.2.3, there are \(2^7\) bit strings of length \(8\) that start with \(1\text{.}\) From Example 4.1.2.5, there are \(2^6\) bit strings of length \(8\) that end with \(00\text{.}\) From Example 4.1.2.6, there are \(2^5\) bit strings that start with \(1\) and end with \(00\text{.}\) By the Principle of Inclusion-Exclusion, there are \(2^7 + 2^6 - 2^5= 160\) bit strings that start with \(1\) or end with \(00\text{.}\)

Example 4.1.4.3. Students in an auditorium.

Suppose there are \(350\) undergraduates in an auditorium. Of these, \(220\) are computer science majors, \(147\) are math majors, and \(51\) are double majoring in computer science and math. How many are neither computer science nor math majors?

Solution.

First count the number of computer science or math majors. By the Principle Inclusion-Exclusion, there are \(220 + 147 - 51 = 316\) computer science or math majors. Then there are \(350 - 316 = 34\) students that are neither computer science nor math majors.