Principi d'inclusió-exclusió
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/42/Inclusion-exclusion.svg/220px-Inclusion-exclusion.svg.png)
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 conjunts
Exemple
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 dona el nombre d'estudiants que no posseeixen aquestes dues propietats 20-10-11+4=3.
Fórmula per a n = 2
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 general
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ó probabilista
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:
- .
Aplicacions
Desigualtats de Bonferroni
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ó
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 ):
|
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.
Via l'aplicació que, a una permutació ω de associa la seva restricció a la subclasse AS és en bijection amb el conjunt de les permutacions de per tant el cardinal de AS és (n-#S)!. Per tant, la probabilitat de AS és (n-#S)!/(n!). La fórmula d'inclusió-exclusió, sota la seva forma probabilista, s'escriu llavors
Reagrupant les parts S d'igual cardinal k, ja que la probabilitat de AS no depèn més que del cardinal de S, s'obté
després
Es nota dn aquesta última probabilitat, que és la probabilitat que una permutació de sigui un desarranjament: dn s'obté truncant el desenvolupament en sèrie de 1/e just després del terme d'índex n (el que, entre parèntesis, és una manera, entre altres, de justificar la convenció d0 = 1). Per a una part S de es nota BS el conjunt de les permutacions de Ω el conjunt dels punts fixos del qual és exactament S: BS és en bijecció amb el conjunt dels desarranjaments de per tant el cardinal de BS és (n-#S)! dn-#S. Així
Ara bé, per definició, una variable aleatòria X segueix la llei de Poisson de paràmetre a, per a tot k enter positiu o nul,