Editing Inclusion–exclusion principle (section)

==Formula generalization==

Given a [[family of sets|family (repeats allowed) of subsets]] ''A''<sub>1</sub>, ''A''<sub>2</sub>, ..., ''A''<sub>n</sub> of a universal set ''S'', the principle of inclusion–exclusion calculates the number of elements of ''S'' in none of these subsets. A generalization of this concept would calculate the number of elements of ''S'' which appear in exactly some fixed ''m'' of these sets.

Let ''N'' = <nowiki>[</nowiki>''n''<nowiki>]</nowiki> = {1,2,...,''n''}. If we define <math>A_{\emptyset} = S</math>, then the principle of inclusion–exclusion can be written as, using the notation of the previous section; the number of elements of ''S'' contained in none of the ''A''<sub>i</sub> is:
:<math> \sum_{J \subseteq [n]} (-1)^{|J|} |A_J|.</math>

If ''I'' is a fixed subset of the index set ''N'', then the number of elements which belong to ''A''<sub>i</sub> for all ''i'' in ''I'' and for no other values is:<ref>{{harvnb|Cameron|1994|loc=pg. 78}}</ref>
:<math> \sum_{I \subseteq J} (-1)^{|J| - |I|} |A_J|.</math>
Define the sets

:<math>B_k = A_{I \cup \{ k \}} \text{ for } k \in N \smallsetminus I.</math>

We seek the number of elements in none of the ''B''<sub>k</sub> which, by the principle of inclusion–exclusion (with <math>B_\emptyset = A_I</math>), is

:<math>\sum_{K \subseteq N \smallsetminus I} (-1)^{|K|}|B_K|.</math>

The correspondence ''K'' ↔ ''J'' = ''I'' ∪ ''K'' between subsets of ''N''&nbsp;\&nbsp;''I'' and subsets of ''N'' containing ''I'' is a bijection and if ''J'' and ''K'' correspond under this map then ''B''<sub>K</sub> = ''A''<sub>J</sub>, showing that the result is valid.