The Principle of Inclusion and Exclusion

The Principle of Inclusion and Exclusion

Example: Let A denote a finite set and let P₁, ...,P_n be any given properties. We want to express the number of elements of A which have none of these properties in terms of numbers of elements which have some of these properties. In order to do this we indicate by P_i(a) the fact that a ÎA has the property P_i, and for an index set I Í n we put

A_I:= {a | " i ÎI :P_i(a) }, in particular A_Æ =A.

Furthermore we put

A^*:= {a | there exists no i such that P_i(a) },

and it is our aim to express | A^* | in terms of the | A_I | . The set on which we shall define an involution is

M:= {(a,I) | I Í n, a ÎA_I }.

A disjoint decomposition of this set is M=M⁺ ÈM^-, where

M⁺:= {(a,I) | | I | even }, and M^-:=M \M⁺.

Now we introduce, for a not ÎA^*, the number s(a):= min{i | P_i(a) } Î n, and define t on M as follows:

t(a,I):= (a,I È{s(a) }) if a not ÎA^*,s(a) not ÎI

t(a,I):= (a,I \{s(a) }) if a not ÎA^*, s(a) ÎI

t(a,I):= (a,I)=(a, Æ) if a ÎA^*.

Obviously 1 not = tÎS_M provided that A^* not =A. Furthermore t²=1 and t is sign-reversing, so that from the involution principle we obtain

| A^* | = | M _t | = | M⁺ | - | M^- | = å_{(a,I) ÎM⁺}1- å_{(a,I) ÎM^-}1

= å _{| I | even} | A_I | - å _{| I | odd} | A_I | = å_{I Í n}(-1) ^{| I |} | A_I | .

Thus we have proved

The Principle of Inclusion and Exclusion Let A be a finite set and P₁, ...,P_n any properties, while A_I denotes the set of elements of A having each of the properties P_i,i ÎI Í n. Then the order of the subset A^* of 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 express

f(n):= | {i În | gcd (i,n)=1 } |

in terms of the different prime divisors p₁, ...,p_m of n. In order to do this we put A:= n and we define P_i,i Îm, to be the property ''divisible by p_i ``, obtaining from the Principle of Inclusion and Exclusion the following expression for A^*, the set of elements of n which are relatively prime to n:

A^*= n- {n/p_i | i Îm}+ {n/p_ip_j | i,j Îm}-+ ...,

which gives the desired expression for the value of the Euler function at n:

  f(n)=n ·Õ_i=1^m (1-(1)/(p_i) ).

The Principle of Inclusion and Exclusion