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 putAI:= {a | " i ÎI :Pi(a) }, in particular AÆ =A.Furthermore we putA*:= {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 isM:= {(a,I) | I Í n, a ÎAI }.A disjoint decomposition of this set is M=M+ ÈM-, whereM+:= {(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 ÎIt(a,I):= (a,I \{s(a) }) if a not ÎA*, s(a) ÎIt(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 provedThe 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 isA nice application is the following derivation of a formula for the values of the Euler function f: We would like to express| A* | = åI Í n(-1) | I | | AI | .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 |
The Principle of Inclusion and Exclusion |