The Principle of Inclusion and Exclusion |

Example:LetAdenote a finite set and letPbe any given properties. We want to express the number of elements of_{1}, ...,P_{n}Awhich havenoneof these properties in terms of numbers of elements which havesomeof these properties. In order to do this we indicate byPthe fact that_{i}(a)a ÎAhas the propertyP, and for an index set_{i}I Íwe putnFurthermore we putA_{I}:= {a | " i ÎI :P_{i}(a) }, in particular A_{Æ}=A.and it is our aim to expressAi^{*}:= {a | there exists nosuch thatP_i(a)},| Ain terms of the^{*}|| A. The set on which we shall define an involution is_{I}|A disjoint decomposition of this set isM:= {(a,I) | I Ín, a ÎA_{I}}.M=M, where^{+}ÈM^{-}Now we introduce, forM^{+}:= {(a,I) | | I | even }, and M^{-}:=M \M^{+}.a not ÎA, the number^{*}s(a):= min{i | P, and define_{i}(a) } ÎntonMas follows:t(a,I):= (a,I È{s(a) }) if a not ÎA^{*},s(a) not ÎIt(a,I):= (a,I \{s(a) }) if a not ÎA^{*}, s(a) ÎIObviouslyt(a,I):= (a,I)=(a, Æ) if a ÎA^{*}.1 not = tÎSprovided that_{M}A. Furthermore^{*}not =Atand^{2}=1tis sign-reversing, so that from the involution principle we obtain| A^{*}| = | M_{ t}| = | M^{+}| - | M^{-}| = å_{(a,I) ÎM+}1- å_{(a,I) ÎM-}1Thus we have proved= å_{ | I | even}| A_{I}| - å_{ | I | odd}| A_{I}| = å_{I Í n}(-1)^{ | I | }| A_{I}| .The Principle of Inclusion and Exclusion LetAbe a finite set andPany properties, while_{1}, ...,P_{n}Adenotes the set of elements of_{I}Ahaving each of the propertiesP. Then the order of the subset_{i},i ÎI ÍnAof elements having none of these properties is^{*}| A^{*}| = å_{I Í n}(-1)^{ | I | }| A_{I}| .A nice application is the following derivation of a formula for the values of the Euler function

f:We would like to expressin terms of the different prime divisorsf(n):= | {i În| gcd (i,n)=1 } |pof_{1}, ...,p_{m}n.In order to do this we putA:=and we definenPto be the property ''divisible by_{i},i Îm,p``, obtaining from the Principle of Inclusion and Exclusion the following expression for_{i}Athe set of elements of^{*},which are relatively prime tonn:which gives the desired expression for the value of the Euler function atA^{*}=n- {n/p_{i}| i Îm}+ {n/p_{i}p_{j}| i,j Îm}-+ ...,n:f(n)=n ·Õ_{i=1}^{m}(1-(1)/(p_{i})).

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

The Principle of Inclusion and Exclusion |