View source for Inclusion-exclusion formula

''inclusion-exclusion principle, inclusion-exclusion method''

The inclusion-exclusion principle is used in many branches of pure and applied mathematics. In [[Probability theory|probability theory]] it means the following theorem: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i1300201.png" /> be events in a [[Probability space|probability space]] and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i1300202.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i1300203.png" /></td> </tr></table>

Then one has the relation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i1300204.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>

This theorem can easily be proved by induction on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i1300205.png" />. Another proof can be given by the use of indicator variables, as follows. In connection with an event <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i1300206.png" /> one defines <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i1300207.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i1300208.png" /> occurs, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i1300209.png" /> otherwise. Then the equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002010.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>

holds. Taking expectations on both sides, the theorem follows.

If one wants to find the probability of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002011.png" />, then first one observes that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002012.png" /> and then uses (a2) for the events <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002013.png" />.

The theorem is frequently attributed to H. Poincaré [[#References|[a8]]]. However, it was already known to A. De Moivre [[#References|[a2]]] and the even more general formula for the probability that at least <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002014.png" /> events occur has been found by r equation','../p/p072950.htm','Positive variation of a function','../p/p073970.htm','Rectifiable curve','../r/r080130.htm','Variation of a function','../v/v096110.htm')" style="background-color:yellow;">C. Jordan [[#References|[a4]]]. See also [[#References|[a5]]] for further references. All these formulas concern Boolean functions of random events.

An example for the application of formula (a2) is the solution of the classical problem of coincidences proposed by P.R. Montmort [[#References|[a7]]]: A box contains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002015.png" /> cards marked <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002016.png" /> and all cards are drawn, one by one, without replacement, where each sequence has the same probability; one says that a coincidence occurs at the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002017.png" />th drawing, or event <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002018.png" /> occurs, if the card drawn is marked <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002019.png" />; the problem is to find the probability that at least one coincidence occurs (cf. also [[Montmort matching problem|Montmort matching problem]]). One easily sees that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002020.png" /> one has

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002021.png" /></td> </tr></table>

hence

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002022.png" /></td> </tr></table>

and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002023.png" /></td> </tr></table>

The numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002024.png" /> have another probabilistic interpretation: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002025.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002026.png" />, i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002027.png" /> is the number of events which occur. One says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002028.png" /> is the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002029.png" />th binomial moment of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002030.png" />. For a proof of the above equation, see, e.g., [[#References|[a11]]].

There are many practical applications where one needs to compute the probability of a union, or other Boolean function of events. Prominent are those in reliability theory. For example, in a communication network, where the links randomly work or fail, one may want to find a two-terminal reliability or the all-terminal reliability. In the former case one has to find the probability that all links in at least one path connecting the two terminal nodes work, and in the latter case the probability that all links in at least one spanning tree work. In both cases the number of random events is too large to apply inclusion-exclusion. In fact, one may be able to compute only a few of the binomial moments involved. In such cases one looks for bounds. The simplest ones, for the probability of the union, are the Bonferroni bounds:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002031.png" /></td> </tr></table>

if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002032.png" /> is even, and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002033.png" /></td> </tr></table>

if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002034.png" /> is odd, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002035.png" /> (cf. also [[Bonferroni inequalities|Bonferroni inequalities]]). However, in many cases these bounds are not sufficiently tight.

A general, efficient method for bounding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002036.png" /> and other Boolean functions of events has been worked out by A. Prékopa (see [[#References|[a10]]] and the references therein). In the case of bounding the probability of the union one observes that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002037.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002038.png" /> is the probability that exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002039.png" /> events occur. Then, if one knows <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002040.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002041.png" />, but the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002042.png" /> are unknown, one solves the linear programs:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002043.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>

If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002044.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002045.png" /> are the optimum values corresponding to the min and max problems, respectively, then these are sharp bounds for the probability of the union, i.e.

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002046.png" /></td> </tr></table>

and no better bounds can be given based on the knowledge of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002047.png" />. There are simple and efficient algorithms to solve problems (a4) which are variants of the dual algorithm of linear programming. The sharp bounding formulas can also be written as

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002048.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002050.png" /> are optimal solutions of the duals of the min and max problems, respectively. It has been shown that the components of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002051.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002052.png" /> have alternating signs, starting with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002053.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002054.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002055.png" />. The optimum values can be expressed by formulas if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002056.png" /> (see the references in [[#References|[a10]]]).

Formula (a2) holds for any finitely additive set function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002057.png" /> defined on an algebra <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002058.png" /> of some subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002059.png" /> (if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002060.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002061.png" />, and if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002062.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002063.png" />). In particular, one may take <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002064.png" /> an arbitrary finite set, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002065.png" /> all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002066.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002067.png" />, the cardinality of the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002068.png" />. The latter case has many applications in combinatorics, especially in enumeration problems. A good sample of combinatorial problems, where inclusion-exclusion is used, is presented in [[#References|[a6]]].

Inclusion-exclusion plays also an important role in number theory. Here one calls it the sieve formula or sieve method. In this respect, V. Brun did pioneering work [[#References|[a1]]] (cf. also [[Sieve method|Sieve method]]; [[Brun sieve|Brun sieve]]). For a summary of the sieve methods, see [[#References|[a9]]] and [[#References|[a3]]]. A simple but revealing example is the formula for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002069.png" />, the number of those positive integers that are relative prime to, and smaller than, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002070.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002071.png" /> has prime divisors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002072.png" />, then the inclusion-exclusion principle gives:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002073.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i130/i130020/i13002074.png" /></td> </tr></table>

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  V. Brun,   "Le crible d'Eratosthène et le théorème de Goldbach"  ''Skrifter Norske Vid.-Akad. Kristiana I'' , '''3'''  (1920)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A. De Moivre,   "Doctrine of chances" , London  (1718)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Halberstam,   H.E. Richert,   "Sieve methods" , Acad. Press  (1974)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  C. Jordan,   "De quelques formules de probabilité"  ''C.R. Acad. Sci. Paris'' , '''65'''  (1867)  pp. 993–994</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  K. Jordan,   "Chapters on the classical calculus of probability" , Akad. Kiadó  (1972)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  L. Lovász,   "Combinatorial problems and exercises" , Akad. Kiadó  (1993)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  P.R. Montmort,   "Essai d'analyse sur les jeux de hazard" , Paris  (1708)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  H. Poincaré,   "Calcul des probabilités" , Gauthier-Villars  (1896)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  K. Prachar,   "Primzahlverteilung" , Springer  (1957)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  A. Prékopa,   "Stochastic programming" , Kluwer Acad. Publ.  (1995)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  L. Takács,   "On the method of inclusion and exclusion"  ''J. Amer. Statist. Assoc.'' , '''62'''  (1967)  pp. 102–113</TD></TR></table>