The Garsia-Milne bijectionThe involution principleThe Involution PrincipleThe Principle of Inclusion and Exclusion

The Principle of Inclusion and Exclusion

A beautiful application is provided by

Example: Let A denote a finite set and let P1, ...,Pn 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 Pi(a) the fact that a ÎA has the property Pi, and for an index set I Í n we put
AI:= {a | " i ÎI :Pi(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 | AI | . The set on which we shall define an involution is
M:= {(a,I) | I Í n, a ÎAI }.
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 | Pi(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ÎSM provided that A* not =A. Furthermore t2=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 | AI | - å | I | odd | AI | = åI Í n(-1) | I | | AI | .
Thus we have proved
The Principle of Inclusion and Exclusion Let A be a finite set and P1, ...,Pn any properties, while AI denotes the set of elements of A having each of the properties Pi,i ÎI Í n. Then the order of the subset A* of elements having none of these properties is
| A* | = åI Í n(-1) | I | | AI | .
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 p1, ...,pm of n. In order to do this we put A:= n and we define Pi,i Îm, to be the property ''divisible by pi ``, 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/pi | i Îm}+ {n/pipj | i,j Îm}-+ ...,
which gives the desired expression for the value of the Euler function at n:
  f(n)=n ·Õi=1m (1-(1)/(pi) ).

harald.fripertinger "at" uni-graz.at http://www-ang.kfunigraz.ac.at/~fripert/
UNI-Graz Institut für Mathematik
UNI-Bayreuth Lehrstuhl II für Mathematik
last changed: January 19, 2005

The Garsia-Milne bijectionThe involution principleThe Involution PrincipleThe Principle of Inclusion and Exclusion