R A M A   A Z U L   X X X V I I





                      PRINCIPIO DE INCLUSION-EXCLUSION





        En la rama anterior, dejamos para pensar algunos problemas, el primero

de los cuales decia:

        

        " ¿cuantos numeros hay del 50 al 12000 inclusive que no sean multiplos

de 3 ni de 5?"



Es facil equivocarse. Intentemos organizarnos:

Del 50 al 12000 hay 12000 - 49 = 11951 numeros.

Tendriamos que restar de esta cantidad, los que son multiplos de 3 o de 5.

Si llamamos N3 al conjunto de los multiplos de 3 entre el 50 y el 12000 y N5

al de los multiplos de 5, y si con |A| indicamos la cantidad de elementos que

tiene A, la solucion a nuestro problema es

        11951- |N3 U N5|

Ahora: |N3 U N5| = |N3| + |N5| - |N3 ï N5|

(cuando sumamos |N3| con |N5| estamos contando 2 veces a todos los numeros que

son multiplos de 3 y de 5, y por lo tanto, hay que descontarlos 1 vez.)

        Notemos que ser multiplo de 3 y de 5 es lo mismo que ser multiplo de

15; contemos, entonces:



Multiplos de 3: 50 ó 3k ó 12000  si y solo si   51 ó 3k ó 12000  y esto ultimo

si y solo si  17 ó k ó 4000. Entonces |N3| = 4000 - 16 = 3984.



Multiplos de 5: 50 ó 5k ó 12000  si y solo si   10 ó k ó 2400, entonces

|N5| = 2400 - 9 = 2391.



Multiplos de 15: 50 ó 15k ó 12000 si y solo si 60 ó 15k ó 12000 y esto ultimo

si y solo si 4 ó k ó 800. Entonces, |N3 ï N4| = 800 - 3 = 797.



Asi, |N3 U N5| = 3984 + 2391 - 797 = 5578, y la cantidad buscada es 

        11951 - 5578 = 6373.



En general

        Si A es un conjunto finito. Supongamos dadas ciertas propiedades que

satisfacen algunos elementos de A.

O sea, se tienen A1, A2, ... , An subconjuntos de A caracterizados por satis-

facer las propiedades p1, p2, ..., pn, respectivamente.

El principio de inclusion exclusion da una formula para el numero de elementos

del COMPLEMENTO de la union A1 U A2 U ... U An, o sea el numero de elementos 

que no satisflace NINGUNA de las propiedades p1, p2, ..., pn.

        Se sabe, del algebra de conjuntos, que

|A1 U A2| = |A1| + |A2| - |A1 ï A2|

|A1 U A2 U A3| = |A1| + |A2| + |A3| - (|A1 ï A2| + |A1 ï A3| + |A2 ï A3| ) +

+ |A1 ï A2 ï A3|  , y en general:



  n                                            n+1

| U  Ai| =  ä |Ai|  -  ä |Ai ï Aj| + ... + (-1)    | A1 ï A2 ï ... ï An|

 i=1       1óión    1ói