Principi d'inclusió-exclusió

Exemple d'inclusió-exclusió a partir de tres conjunts.

En combinatòria, el principi d'inclusió-exclusió permet expressar el nombre d'elements (o cardinal) d'una unió finita de conjunts finits en funció del nombre d'elements d'aquests conjunts i de les seves interseccions. Es tradueix directament en termes de probabilitats.

S'atribueix al matemàtic Abraham De Moivre, tot i que va ser formulat per primera vegada pel matemàtic portuguès Daniel Augusto da Silva (1814-1878) i va ser generalitzat per Camille Jordan,[1] i es coneix també (ell o la seva versió probabilista) sota el nom de fórmula del garbell de Poincaré, fórmula de Poincaré, o fórmula del garbell.

El cas dos conjuntsModifica

ExempleModifica

Entre 20 estudiants, 10 estudien les matemàtiques, 11 estudien la física, i 4 estudien les dues assignatures al mateix temps. Quants n'hi ha d'estudiants que no estudien ni matemàtiques ni física?

Per visualitzar-ho es pot construir un diagrama de Venn.

 

S'encerclen els elements que verifiquen la mateixa propietat. E representa el grup de tots els estudiants, M representa els que tenen la propietat d'«estudiar matemàtiques», P representa aquells que posseeix la propietat: d'«estudiar física».

Es col·loca a cada part el nombre d'estudiants. Atès que quatre persones estudien a la vegada matemàtiques i física, se'n posen 4 en la intersecció dels dos cercles. Hi ha d'haver per tant 10-4=6 persones que estudien matemàtiques però no física i 11-4=7 persones que estudien física però no matemàtiques. Queden per tant 20-(6+4+7)=3 persones que no estudien ni matemàtiques ni física.

Aquest resultat es troba fàcilment emprant el principi d'inclusió-exclusió que dóna el nombre d'estudiants que no posseeixen aquestes dues propietats 20-10-11+4=3.

Fórmula per a n = 2Modifica

Siguin A i B dos conjunts finits, la fórmula s'escriu

 

on|A| i|B | representen els cardinals respectius de A i B.

En Altres Paraules, es poden comptar els elements de la unió de dos conjunts A i B sumant els cardinals d'aquests dos conjunts i sostraient el cardinal de la seva intersecció.

Cas generalModifica

Siguin A 1..., A n n conjunts finits. Es té

  

on|A| designa el cardinal d'un conjunt finit A.

Aquesta fórmula es també pot escriure de manera més condensada

 .

Es pot demostrar per inducció sobre n, o fent servir les funcions característiques.

Sigui E un conjunt finit, que conté els conjunts A i. Es dedueix per pas al complementari que el cardinal del conjunt dels elements de E que no pertanyen a cap dels Ai és:

 .

El principi d'inclusió-exclusió es pot deduir de la fórmula d'inversió de Möbius.

Versió probabilistaModifica

Siguin un espai de probabilitat   i   elements   de la tribu   es té

 .

Aquesta fórmula es pot demostrar per inducció sobre n, o fent servir funcions característiques, de la mateixa manera que la fórmula precedent. També es pot formular de la manera següent:

 .

AplicacionsModifica

Desigualtats de BonferroniModifica

El terme d'ordre k de la suma decreix (en valor absolut) en funció de k. Les sumes parcials dels primers termes de la fórmula subministren per tant alternativament a un augmentant i a un minorant la suma completa, i es poden fer servir com aproximacions d'aquesta: aquests augmentants i minorants s'anomenen les desigualtats de Bonferroni.

Desarranjaments i nombre de punts fixos d'una permutacióModifica

En combinatòria, la fórmula del garbell permet determinar el nombre de desarranjaments d'un conjunt finit. Un desarranjament d'un conjunt A és una bijection de A en si mateix sense punt fix. Gràcies al principi d'inclusió-exclusió de Moivre, es pot demostrar que si el cardinal de A és igual a n, llavors el nombre de desarranjaments de A és el nombre sencer més proper a n!/e (on e designa la base dels logaritmes neperians). En resulta que si totes les bijeccions tenen la mateixa probabilitat de ser escollides, llavors la probabilitat perquè una bijecció presa a l'atzar sigui un desarranjament tendeix ràpidament cap a 1/e quan n tendeix cap a l'infinit.

Es pot portar més lluny l'estudi estadístic dels punts fixos de les permutacions. notant N(ω) el nombre de punts fixos d'una permutació ω. S'observa que N(ω)=0 si i només si ω és un desarranjament. En això la proposició següent precisa el resultat en relació amb els desarranjaments (que no és altre que el càlcul de  ):

Proposició


Per a tot enter k comprès entre 0 i n
 

En particular, la llei de N és molt propera a la llei de Poisson de paràmetre 1, per a n gran. Això il·lustra el paradigma de Poisson,[2] segons el qual una suma d'un gran nombre de variables de Bernouilli de petit paràmetre, poc correlacionades, segueix aproximadament la Llei de Poisson: N pot ser vista com tal suma. L'escriptura de N com a suma de variables de Bernoulli permet un càlcul ràpid de l'esperança i de la variància de N, el que l'expressió explicita de la llei de N, donada damunt, no permet.

Vegeu tambéModifica

NotesModifica

  1. De Castro Korgi, Rodrigo. El universo LATEX. Univ. Nacional de Colombia, 2003, p. 305. ISBN 9789587010602. 
  2. A. D., Barbour; L., Holst; S., Janson. The Clarendon Press Oxford University Press. Poisson approximation (en en), 1992 (Oxford Studies in Probability). ISBN 0198522355. 

Pàgines relacionadesModifica