Editing Inclusion–exclusion principle (section)

==Other formulas==

The principle is sometimes stated in the form<ref>{{harvnb|Graham| Grötschel|Lovász|1995|loc=pg. 1049}}</ref> that says that if

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

then
{{NumBlk|:|<math>f(A)=\sum_{S \subseteq A}(-1)^{|A|-|S|}g(S) </math>|{{EquationRef|2}}}}

The combinatorial and the probabilistic version of the inclusion–exclusion principle are instances of ({{EquationNote|2}}).
{{math proof|proof=
Take <math>\underline{m} = \{1,2,\ldots,m\}</math>, <math>f(\underline{m}) = 0</math>, and

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

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

:<math>g(A)=\left|\bigcap_{i \in \underline{m} \smallsetminus A} A_i\right|, \quad g(\underline{m}) = \left|\bigcup_{i \in \underline{m}} A_i \right| \text{ and } g(A) = \mathbb{P} \left( \bigcap_{i \in \underline{m} \smallsetminus A} A_i \right),~~ g(\underline{m}) = \mathbb{P} \left(\bigcup_{i \in \underline{m}} A_i\right)</math>

respectively for all 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} \smallsetminus A} A_i</math> can be [[element (mathematics)#notation|contained]] in other <math>A_i</math> (<math>A_i</math> with <math>i \in A</math>) as well, and the {{nowrap|<math>\cap \smallsetminus \cup</math>-formula}} runs exactly through all possible extensions of the sets <math>\{A_i \mid i \in \underline{m} \smallsetminus A\}</math> with other <math>A_i</math>, counting <math>a</math> only for the set that matches the membership behavior of  <math>a</math>, if <math>S</math> runs through all [[subset]]s of <math>A</math> (as in the definition of <math>g(A)</math>).

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

:<math>\sum_{\underline{m} \supseteq T \supsetneq \varnothing}(-1)^{|T|-1} g(\underline{m} \smallsetminus T) = \sum_{\varnothing \subseteq S \subsetneq \underline{m}}(-1)^{m-|S|-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 ({{EquationNote|2}}) is a generalization of [[Möbius inversion formula]] for [[square-free integer|square-free]] [[natural number]]s. Therefore, ({{EquationNote|2}}) is seen as the Möbius inversion formula for the [[incidence algebra]] of the [[partially ordered set]] of all subsets of ''A''.

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

{{NumBlk|:|<math>f(A) = \sum_{S\subseteq A}\mu(A - S) g(S) </math>|{{EquationRef|3}}}}

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

* ''μ''(''S'') =  1 if ''S'' is a set (i.e. a multiset without double elements) of [[even and odd numbers|even]] [[cardinality]].
* ''μ''(''S'') =  −1 if ''S'' is a set (i.e. a multiset without double elements) of odd cardinality.
* ''μ''(''S'') =  0 if ''S'' is a proper multiset (i.e. ''S'' has double elements).

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

{{proof|title=Proof of ({{EquationNote|3}})|proof=
Substitute
<math display="block">g(S)=\sum_{T\subseteq S}f(T)</math>
on the right hand side of ({{EquationNote|3}}). Notice that <math>f(A)</math> appears once on both sides of ({{EquationNote|3}}). 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 ({{EquationNote|3}}). 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 \notin T</math>.

Notice that <math>A - S</math> must be a set for each [[Positive number|positive]] or [[negative number|negative]] appearance of <math>f(T)</math> on the right hand side of ({{EquationNote|3}}) 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 ({{EquationNote|3}}) that is obtained by way of <math>S</math> such that <math>A - S</math> is a set that 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 that does not contain <math>a</math>. This gives the desired result.
}}