6.4 Inclusion-Exclusion Principle

Inclusion-Exclusion Principle

The Inclusion-Exclusion Principle is a counting technique used to determine the size of a union of overlapping sets by correcting for overcounts. Instead of simply adding the sizes of each set, the method subtracts the sizes of their pairwise intersections, adds back the size of their triple-wise intersections, and so on, alternating signs:

\begin{document}
\begin{tikzpicture}[scale=0.95]
 %
 % First panel: shade A
 %
 \begin{scope}[shift={(-7.5,0)}]
   % Shade all of circle A (including its intersection region)
   \fill[gray, fill opacity=0.25] (0,0) circle (1cm);
   % Draw the two circles and label them
   \draw (0,0) circle (1cm)       node[above left  = 22pt] {$A$};
   \draw (1.5,0) circle (1cm)     node[above right = 22pt] {$B$};
   % Underneath: label |A|
   \node at (0.75,-1.5) {$|A|$};
 \end{scope}
 
 % “+” sign between panel 1 and panel 2
 \node at (-4.5, -1.5) [font=\Large] {+};
 
 \begin{scope}[shift={(-3,0)}]
   % Shade all of circle B
   \fill[gray, fill opacity=0.25] (1.5,0) circle (1cm);
   % Draw the two circles and label them
   \draw (0,0) circle (1cm)       node[above left  = 22pt] {$A$};
   \draw (1.5,0) circle (1cm)     node[above right = 22pt] {$B$};
   % Underneath: label |B|
   \node at (0.75,-1.5) {$|B|$};
 \end{scope}
 
 % “–” sign between panel 2 and panel 3
 \node at (0,-1.5) [font=\Large] {–};
 
 %
 % Third panel: shade A ∩ B only
 %
 \begin{scope}[shift={(1.5,0)}]
   % Clip to circle A first, then fill circle B → shades exactly the overlap
   \begin{scope}
     \clip (0,0) circle (1cm);
     \fill[gray, fill opacity = 0.25] (1.5,0) circle (1cm);
   \end{scope}
   % Draw the two circles and label them
   \draw (0,0) circle (1cm)       node[above left  = 22pt] {$A$};
   \draw (1.5,0) circle (1cm)     node[above right = 22pt] {$B$};
   % Underneath: label |A ∩ B|
   \node at (0.75,-1.5) {$|A \cap B|$};
 \end{scope}
 
 % “=” sign between panel 3 and panel 4
 \node at (4.5,-1.5) [font=\Large] {=};
 
 %
 % Fourth panel: shade A ∪ B
 %
 \begin{scope}[shift={(6,0)}]
   % Shade all of circle A
   \begin{scope}[gray, fill opacity = 0.25]
      \fill (0,0) circle (1cm) (1.5,0) circle (1cm);
  \end{scope}
   % Draw the two circles and label them
   \draw (0,0) circle (1cm)       node[above left  = 22pt] {$A$};
   \draw (1.5,0) circle (1cm)     node[above right = 22pt] {$B$};
   % Underneath: label |A ∪ B|
   \node at (0.75,-1.5) {$|A \cup B|$};
 \end{scope}
\end{tikzpicture}
\end{document}

Formally, given $n$ sets, their union is calculated by alternately adding and subtracting the cardinalities of their intersections, such that
$|A_1\cup A_2\cup \dots \cup A_n|={\sum }_{k=1}^n(-1{)}^{k-1}{\sum }_{S\subseteq \{1,\dots ,n\}:|S|=k}^{}|\bigcap _{i\in S}{A}_i|$

Examples

Coprimes

What is the total number of positive integers strictly less than 100 that are also coprime to 100?

Solution

If a number is not coprime, then it must be a multiple of 2 or 5:

• There are exactly $100/2-1=49$ multiples of 2.
• There are $100/5-1=19$ multiples of 5.
• There are also $100/10-1=9$ multiples of 2 and 5.

Therefore, there are exactly $49+19-9=59$ numbers less than 100 that are NOT coprime to 100. This means that there are $\boxed{99-59=40}$ numbers that are coprime to 100.