View source for Inclusion–exclusion principle

In [[combinatorics|combinatorial]] [[mathematics]], the '''inclusion–exclusion principle''' (also known as the '''sieve principle''') states that if ''A''<sub>1</sub>, ..., ''A<sub>n</sub>'' are finite sets, then

:<math>
\begin{align}
\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|
-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\
& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|
\end{align}</math>

where |''A''| denotes the [[cardinality]] of the set ''A''. For example, taking ''n''&nbsp;=&nbsp;2, we get a special case of [[double counting (proof technique)|double counting]]; in words: we can count the size of the [[union (set theory)|union]] of sets ''A'' and ''B'' by adding |''A''| and |''B''| and then subtracting the size of their [[intersection (set theory)|intersection]]. The name comes from the idea that the principle is based on over-generous ''inclusion'', followed by compensating ''exclusion''. When ''n''&nbsp;>&nbsp;2 the exclusion of the pairwise intersections is (possibly) too severe, and the correct formula is as shown with alternating signs.

This formula is attributed to [[Abraham de Moivre]]; it is sometimes also named for [[Daniel da Silva (mathematician)|Daniel da Silva]], [[Joseph Sylvester]] or [[Henri Poincaré]].{{fact|date=October 2007}}
[[Image:Inclusion-exclusion.svg|thumb|Inclusion–exclusion illustrated for three sets]]
[[Image:Inclusion exclusion diagram.JPG|thumb|Counts of each region with progressively more terms used for n&nbsp;=&nbsp;4]]

For the case of three sets ''A'', ''B'', ''C'' the inclusion–exclusion principle is illustrated in the graphic on the right. 

==Proof==
Let ''A'' denote the union <math>\scriptstyle \cup_{i=1}^n A_i</math> of the sets ''A''<sub>1</sub>, ..., ''A<sub>n</sub>''.  To prove the inclusion–exclusion principle in general, we first have to verify the identity

:<math>1_A  =\sum_{k=1}^n (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,n\}\atop\scriptstyle|I|=k} 1_{A_I}\qquad(*)</math>

for [[indicator function]]s, where
:<math>A_I = \bigcap_{i\in I} A_i.</math>
There are at least two ways to do this:

'''First possibility:''' It suffices to do this for every ''x'' in the union of ''A''<sub>1</sub>, ..., ''A<sub>n''</sub>. Suppose ''x'' belongs to exactly ''m'' sets with 1&nbsp;≤&nbsp;''m''&nbsp;≤&nbsp;''n'', for simplicity of notation say ''A''<sub>1</sub>, ..., ''A<sub>m''</sub>. Then the identity at ''x'' reduces to

:<math>1 =\sum_{k=1}^m (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,m\}\atop\scriptstyle|I|=k} 1.</math>

The number of subsets of cardinality ''k'' of an ''m''-element set is the combinatorical interpretation of the [[binomial coefficient]] <math>\textstyle\binom mk</math>&nbsp;. Since <math>\textstyle1=\binom m0</math>&nbsp;, we have

:<math>\binom m0 =\sum_{k=1}^m (-1)^{k-1}\binom mk.</math>

Putting all terms to the left-hand side of the equation, we obtain the expansion for (1&nbsp;–&nbsp;1)<sup>''m''</sup> given by the [[binomial theorem]], hence we see that (*) is true for ''x''.

'''Second possibility:'''  The following function is identically zero

:<math>(1_A-1_{A_1})(1_A-1_{A_2})\cdots(1_A-1_{A_n})\,=\,0\,,</math>

because: if ''x'' is not in ''A'', then all factors are 0 - 0 = 0; and otherwise, if ''x'' does belong to some  ''A<sub>m</sub>'', then the corresponding ''m''th factor is 1 - 1 = 0. By expanding the product on the right-hand side, equation (*) follows.

'''Use of (*):''' To prove the inclusion–exclusion principle for the cardinality of sets, sum the equation (*) over all ''x'' in the union of ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub>. To derive the version used in probability, take the [[expected value|expectation]] in (*). In general, [[Lebesgue integral|integrate]] the equation (*) with respect to ''μ''. Always use linearity.

==Example==
Suppose there is a deck of ''n'' cards, each card is numbered from 1&nbsp;to&nbsp;''n''.  Suppose a card numbered ''m'' is in the correct position if it is the ''m''th card in the deck. How many ways, ''W'', can the cards be shuffled with at least 1 card being in the correct position?

Begin by defining set ''A''<sub>''m''</sub>, which is all of the orderings of cards with the ''m''th card correct.  Then the number of orders, ''W'', with ''at least'' one card being in the correct position, ''m'', is

: <math>W = \biggl|\bigcup_{m=1}^nA_m\biggr|.</math>

Apply the principle of inclusion-exclusion, 

: <math>
\begin{align}
W & = \sum_{m_1=1}^n \left| A_{m_1} \right|  \\
  & - \sum_{m_1,m_2\,:\,1 \le m_1 < m_2 \le n} \left|A_{m_1} \cap A_{m_2} \right|  \\
  & + \sum_{m_1,m_2,m_3\,:\,1 \le m_1 < m_2 < m_3 \le n} \left|A_{m_1} \cap A_{m_2} \cap A_{m_3} \right|  \\
  & - \cdots  \\
  & + (-1)^{p-1} \sum_{m_1,\ldots,m_p\,:\,1 \le m_1 < \cdots < m_p \le n} \left|A_{m_1} \cap \cdots \cap A_{m_p} \right|  \\
  & \cdots. \\
\end{align}
</math>

Each value <math>A_{m_1} \cap \cdots \cap A_{m_p}</math> represents the set of shuffles having ''p'' values ''m''<sub>1</sub>,&nbsp;...,&nbsp;''m''<sub>''p''</sub> in the correct position.  Note that the number of shuffles with ''p'' values correct only depends on ''p'', not on the particular values of <math>m</math>.  For example, the number of shuffles having the 1st, 3rd, and 17th cards in the correct position is the same as the number of shuffles having the 2nd, 5th, and 13th cards in the correct positions.  It only matter that of the n cards, 3 were chosen to be in the correct position.  Thus there are <math>{n \choose p}</math> terms in each summation (see [[combination]]).

: <math>
\begin{align}
W & = {n \choose 1} \left|A_1 \right|  \\
  & - {n \choose 2} \left|A_1 \cap A_2 \right|  \\
  & + {n \choose 3} \left|A_1 \cap A_2 \cap A_3 \right|  \\
  & - \cdots  \\
  & + (-1)^{p-1} {n \choose p} \left|A_1 \cap \cdots \cap A_p \right|  \\
  & \cdots. \\
\end{align}
</math>

<math>\left|A_1 \cap \cdots \cap A_p \right|</math> is the number of orderings having ''p'' elements in the correct position, which is equal to the number of ways of ordering the remaining ''n''&nbsp;&minus;&nbsp;''p'' elements, or (''n''&nbsp;&minus;&nbsp;''p'')<nowiki>!</nowiki>.  Thus we finally get:

: <math>
\begin{align}
W & = {n \choose 1} (n-1)!  \\
  & - {n \choose 2} (n-2)!  \\
  & + {n \choose 3} (n-3)!  \\
  & - \cdots   \\
  & + (-1)^{p-1} {n \choose p} (n-p)!  \\
  & \cdots \\
W & = \sum_{p=1}^n (-1)^{p-1} {n \choose p} (n-p)!. \\
\end{align}
</math>

Noting that <math>{n \choose p} = \frac{n!}{p!(n-p)!}</math>, this reduces to

: <math>
\begin{align}
W & = \sum_{p=1}^n (-1)^{p-1}\, \frac{n!}{p!}.
\end{align}
</math>

A permutation where ''no'' card is in the correct position is called a [[derangement]]. Taking ''n''<nowiki>!</nowiki> to be the total number of permutations, the probability ''Q'' that a random shuffle produces a derangement is given by

: <math>Q = 1 - \frac{W}{n!} = \sum_{p=0}^n \frac{(-1)^p}{p!}, </math>

the [[Taylor series|Taylor expansion]] of ''e''<sup>&minus;1</sup>.  Thus the probability of guessing an order for a shuffled deck of cards and being incorrect about every card is approximately 1/''e'' or 36%.

==In probability==

In [[probability]], for events ''A''<sub>1</sub>, ..., ''A''<sub>''n''</sub> in a [[probability space]] <math>\scriptstyle(\Omega,\mathcal{F},\mathbb{P})</math>, the inclusion–exclusion principle becomes for ''n''&nbsp;=&nbsp;2

:<math>\mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),</math>

for ''n''&nbsp;=&nbsp;3

:<math>\begin{align}\mathbb{P}(A_1\cup A_2\cup A_3)&=\mathbb{P}(A_1)+\mathbb{P}(A_2)+\mathbb{P}(A_3)\\
&\qquad-\mathbb{P}(A_1\cap A_2)-\mathbb{P}(A_1\cap A_3)-\mathbb{P}(A_2\cap A_3)\\
&\qquad+\mathbb{P}(A_1\cap A_2\cap A_3)
\end{align}</math>

and in general

:<math>\begin{align}
\mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr) & {} =\sum_{i=1}^n \mathbb{P}(A_i)
-\sum_{i,j\,:\,i<j}\mathbb{P}(A_i\cap A_j) \\
&\qquad+\sum_{i,j,k\,:\,i<j<k}\mathbb{P}(A_i\cap A_j\cap A_k)-\ \cdots\ +(-1)^{n-1}\, \mathbb{P}\biggl(\bigcap_{i=1}^n A_i\biggr),
\end{align}</math>

which can be written in closed form as

:<math>\mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr)  =\sum_{k=1}^n (-1)^{k-1}\sum_{\scriptstyle I\subset\{1,\ldots,n\}\atop\scriptstyle|I|=k} \mathbb{P}(A_I),</math>

where the last sum runs over all subsets ''I'' of the indices 1, ..., ''n'' which contain exactly ''k'' elements, and

:<math>A_I:=\bigcap_{i\in I} A_i</math>

denotes the intersection of all those ''A<sub>i</sub>'' with index in ''I''.

According to the [[Boole's inequality|Bonferroni inequalities]], the sum of the first terms in the formula is alternately an upper bound and a lower bound for the [[Sides of an equation|LHS]]. This can be used in cases where the full formula is too cumbersome.

For a general [[measure space]] (''S'',''Σ'',''μ'') and [[measurable]] subsets ''A''<sub>1</sub>, ..., ''A<sub>n''</sub> of finite measure, the above identities also hold when the probability measure <math>\mathbb{P}</math> is replaced by the measure ''μ''.

===Special case===

If, in the probabilistic version of the inclusion–exclusion principle, the probability of the intersection ''A<sub>I</sub>'' only depends on the cardinality of ''I'', meaning that for every ''k'' in {1,&nbsp;...,&nbsp;''n''} there is an ''a<sub>k</sub>'' such that

:<math>a_k=\mathbb{P}(A_I)\quad\text{for every}\quad I\subset\{1,\ldots,n\}\quad\text{with}\quad |I|=k,</math>

then the above formula simplifies to

:<math>\mathbb{P}\biggl(\bigcup_{i=1}^n A_i\biggr)  =\sum_{k=1}^n (-1)^{k-1}\binom nk a_k</math>

due to the combinatorial interpretation of the [[binomial coefficient]] <math>\scriptstyle\binom nk</math>.

Similarly, when the cardinality of the union of finite sets ''A''<sub>1</sub>, ..., ''A<sub>n</sub>'' is of interest, and these sets are a family with regular intersections, meaning that for every ''k'' in {1, ..., ''n''} the intersection

:<math>A_I:=\bigcap_{i\in I} A_i</math>

has the same cardinality, say ''a<sub>k</sub>'' = |''A<sub>I</sub>''|, irrespective of the ''k''-element subset ''I'' of {1,&nbsp;...,&nbsp;''n''}, then

:<math>\biggl|\bigcup_{i=1}^n A_i\biggr|  =\sum_{k=1}^n (-1)^{k-1}\binom nk a_k\,.</math>

An analogous simplification is possible in the case of a general measure space (''S'',''Σ'',''μ'') and measurable subsets ''A''<sub>1</sub>, ..., ''A<sub>n''</sub> of finite measure.

==Other forms==

The principle is sometimes stated in the form that says that if

:<math>g(A)=\sum_{S\,:\,S\subseteq A}f(S)</math>

then

:<math>f(A)=\sum_{S\,:\,S\subseteq A}(-1)^{\left|A\right|-\left|S\right|}g(S)\qquad(**)</math>

::We show now that the combinatorial and the probabilistic version of the inclusion-exclusion principle are instances of (**). Take <math>\underline{m} = \{1,2,\ldots,m\}</math>, <math>f(\underline{m}) = 0</math>, and

:::<math>f(S)=\bigg|\bigcap_{i \in \underline{m} \backslash S} A_i \bigg\backslash \bigcup_{i \in S} A_i\bigg| \qquad\text{and}\qquad f(S)=\mathbb{P}\bigg(\bigcap_{i \in \underline{m} \backslash S} A_i \bigg\backslash \bigcup_{i \in S} A_i\bigg)</math>

::respectively for all [[set (mathematics)|sets]] <math>S</math> with <math>S \subsetneq \underline{m}</math>. Then we obtain 

:::<math>g(A)=\bigg|\bigcap_{i \in \underline{m} \backslash A} A_i\bigg|,~~ g(\underline{m}) = \bigg|\bigcup_{i \in \underline{m}} A_i \bigg| \qquad\text{and}\qquad g(A)=\mathbb{P}\bigg(\bigcap_{i \in \underline{m} \backslash A} A_i\bigg),~~ g(\underline{m}) = \mathbb{P}\bigg(\bigcup_{i \in \underline{m}} A_i\bigg)</math>

::respectively for all [[set (mathematics)|sets]] <math>A</math> with <math>A \subsetneq \underline{m}</math>. This is  because [[element (mathematics)|elements]] <math>a</math> of <math>\cap_{i \in \underline{m} \backslash A} A_i</math> can be [[element (mathematics)#notation|contained]] in other <math>A_i</math>'s (<math>A_i</math>'s with <math>i \in A</math>) as well, and the <math>\cap\backslash\!\!\cup\!\text{-}</math>formula runs exactly through all possible extensions of the [[set (mathematics)|sets]] <math>\{A_i \mid i \in \underline{m} \backslash A\}</math> with other <math>A_i</math>'s, counting <math>a</math> only for the [[set (mathematics)|set]] that matches the [[element (mathematics)#notation|membership]] behavior of  <math>a</math>, if <math>S</math> runs through all [[subset|subsets]] of <math>A</math> (as in the definition of <math>g(A)</math>).

::Since <math>f(\underline{m}) = 0</math>, we obtain from (**) with <math>A = \underline{m}</math> that

:::<math>\sum_{T\,:\,\underline{m} \supseteq T \supsetneq \varnothing}(-1)^{\left|T\right|-1} g(\underline{m} \backslash T) = \sum_{S\,:\,\varnothing \subseteq S \subsetneq \underline{m}}(-1)^{m-\left|S\right|-1}g(S) = g(\underline{m})</math>

::and by interchanging sides, the combinatorial and the probabilistic version of the inclusion-exclusion principle follow. 

If one sees a number <math>n</math> as a set of its prime factors, then (**) is a generalization of [[Möbius inversion formula]] for [[square-free integer|square-free]] [[natural number|natural numbers]]. Therefore, (**) is seen as the [[Möbius inversion formula]] for the [[incidence algebra]] of the [[partially ordered set]] of all [[subset|subsets]] of ''A''.

For a generalization of the full version of [[Möbius inversion formula]], (**) must be generalized to [[multiset]]s. For multisets instead of sets, (**) becomes

:<math>f(A)=\sum_{S\,:\,S\subseteq A}\mu(A - S)g(S)\qquad(***)</math>

where <math>A - S</math> is the [[multiset]] for which <math>(A - S) \uplus S = A</math>, and

* ''&mu;''(''S'') =  1 if ''S'' is a [[set (mathematics)|set]] (i.e. a [[multiset]] without double [[element (mathematics)|elements]]) of [[even and odd numbers|even]] [[cardinality]].
* ''&mu;''(''S'') =  -1 if ''S'' is a [[set (mathematics)|set]] (i.e. a [[multiset]] without double [[element (mathematics)|elements]]) of [[even and odd numbers|odd]] [[cardinality]].
* ''&mu;''(''S'') =  0 if ''S'' is a proper [[multiset]] (i.e. ''S'' has double [[element (mathematics)|elements]]).

Notice that ''<math>\mu</math>''<math>(A - S)</math> is just the <math>(-1)^{\left|A\right|-\left|S\right|}</math> of (**) in case <math>A - S</math> is a set. 

'''Proof of (***):''' Substitute 

:<math>g(S)=\sum_{T\,:\,T\subseteq S}f(T)</math>

on the right hand side of (***). Notice that <math>f(A)</math> appears once on both sides of (***). So we must show that for all <math>T</math> with <math>T\subsetneq A</math>, the terms <math>f(T)</math> cancel out on the right hand side of (***). For that purpose, take a fixed <math>T</math> such that <math>T\subsetneq A</math> and take an arbitrary fixed <math>a \in A</math> such that <math>a \not\in T</math>. 

Notice that <math>A - S</math> must be a [[set (mathematics)|set]] for each [[positive]] or [[negative]] appearance of <math>f(T)</math> on the right hand side of (***) that is obtained by way of the [[multiset]] <math>S</math> such that <math>T \subseteq S \subseteq A</math>. Now each appearance of <math>f(T)</math> on the right hand side of (***) that is obtained by way of <math>S</math> such that <math>A - S</math> is a [[set (mathematics)|set]] that [[element (mathematics)#notation|contains]] <math>a</math> cancels out with the one that is obtained by way of the corresponding <math>S</math> such that <math>A - S</math> is a [[set (mathematics)|set]] that does not [[element (mathematics)#notation|contain]] <math>a</math>. This gives the desired result.

==Applications==

In many cases where the principle could give an exact formula (in particular, counting [[prime number]]s using the [[sieve of Eratosthenes]]), the formula arising doesn't offer useful content because the number of terms in it is excessive. If each term individually can be estimated accurately, the accumulation of errors may imply that the inclusion–exclusion formula isn't directly applicable. In [[number theory]], this difficulty was addressed by [[Viggo Brun]]. After a slow start, his ideas were taken up by others, and a large variety of [[sieve method]]s developed. These for example may try to find upper bounds for the "sieved" sets, rather than an exact formula.

===Counting derangements===

{{main|Derangement}}

A well-known application of the inclusion–exclusion  principle is to the combinatorial problem of counting all [[derangement]]s of a finite set.  A ''derangement'' of a set ''A'' is a [[bijection]] from ''A'' into itself that has no fixed points. Via the inclusion–exclusion principle one can show that if the cardinality of ''A'' is ''n'', then the number of derangements is [''n''!&nbsp;/&nbsp;''e''] where [''x''] denotes the [[nearest integer function|nearest integer]] to ''x''; a detailed proof is available [[Random permutation statistics#Number of permutations that are derangements|here]].

This is also known as the [[subfactorial]] of ''n'', written !''n''. It follows that if all bijections are assigned the same probability then the probability that a random bijection is a derangement quickly approaches 1/''e'' as ''n'' grows.

===Counting intersections===
The principle of inclusion–exclusion, combined with [[de Morgan's theorem]], can be used to count the intersection of sets as well. Let <math>\scriptstyle\overline{A}_k</math> represent the complement of ''A''<sub>''k''</sub> with respect to some universal set ''A'' such that <math>\scriptstyle A_k\, \subseteq\, A</math> for each ''k''. Then we have

:<math> 
\bigcap_{i=1}^n A_i = \overline{\bigcup_{i=1}^n \overline{A}_i}
</math>

thereby turning the problem of finding an intersection into the problem of finding a union.

==See also==
* [[Combinatorial principles]]
* [[Boole's inequality]]
* [[Necklace problem]]
* [[Schuette–Nesbitt formula]]
* [[Maximum-minimums identity]]

==References==
{{planetmath|id=2803|title=principle of inclusion-exclusion}}

[[Category:Enumerative combinatorics]]
[[Category:Probability theory]]
[[Category:Articles containing proofs]]
[[Category:Mathematical principles]]

[[de:Prinzip von Inklusion und Exklusion]]
[[es:Principio de inclusión-exclusión]]
[[eo:Inkluziveco-ekskluda principo]]
[[eu:Bilketa (probabilitatea)]]
[[fr:Principe d'inclusion-exclusion]]
[[it:Principio di inclusione ed esclusione]]
[[he:עקרון ההכלה וההפרדה]]
[[ja:包除原理]]
[[ko:포함-배제의 원리]]
[[pl:Zasada włączeń i wyłączeń]]
[[ru:Формула включений-исключений]]
[[sk:Princíp zapojenia a vypojenia]]
[[sv:Principen om inklusion/exklusion]]
[[ur:اصول شمول استشنا]]
[[zh:排容原理]]