# Inclusion-Exclusion Principle Implementation

I would like to know how I can write a Mathematica code for the Inclusion–exclusion principle.

The formulas governing it are:

$P(\bigcup_{i=1}^n A_i)=\sum_{k=1}^n (-1)^{k-1} \sum_{\substack{I\subset\{1,2,...,n\}\\|I|=k} }P(\bigcap_{i\in I} A_i)$

where $P(A_i)$ denotes the probability of the event $A_i$. Similarly for cardinality of union we have:

$|\bigcup_{i=1}^n A_i|=\sum_{k=1}^n |A_k|- \sum_{1\leq i_1<i_2\leq n} |A_{i_1}\cap A_{i_2}|+\sum_{1\leq i_1<i_2<i_3\leq n} |A_{i_1}\cap A_{i_2}\cap A_{i_3}|-\cdots+(-1)^{n-1}|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_n}|$

or in closed form

$|\bigcup_{i=1}^n A_i|=\sum_{\substack{\emptyset\neq I\subset\{1,2,...,n\}\\|I|=k} }(-1)^{|I|-1} |\bigcap_{i\in I} A_i|$

-
Hi ! Please format your code accordingly (see help centre) and add any relevant details/code. As it is currently written (without any effort) the question will probably generate 0 answers. – Sektor Jul 28 '14 at 7:48
@Sektor, thanks! – asad Jul 28 '14 at 8:11
Would be great if you could come up with a minimal working example. – Öskå Jul 28 '14 at 9:03

## 1 Answer

Symbolically:

Clear[s,a,b,c,d];
s={a,b,c,d};
uni@@s==Total[Map[-(-1)^Length[#]int@@#&,Rest[Subsets[s]],1]]/.int[q_]->q;

uni[a,b,c,d] == a + b + c + d - int[a, b] - int[a, c] - int[a, d] - int[b, c] -
int[b, d]-int[c,d] + int[a, b, c] + int[a, b, d] + int[a, c, d] +
int[b, c, d] - int[a, b, c, d]

Now, fill in some values as integers:

{a,b,c,d} = RandomInteger[{0,9},{4,5}]

Finally, a workable example with Length as cardinality :

{car[uni @@ s], Total@ Map[-(-1)^Length[#]car[int @@ #]&, Rest[Subsets[s]], 1]} /.
uni->Union /. int->Intersection/. car->Length
-