Principi d'inclusió-exclusió

De Viquipèdia
Dreceres ràpides: navegació, cerca
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, 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[modifica | modifica el codi]

Exemple[modifica | modifica el codi]

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.

Exemple

S'encerclen els elements que verifiquen la mateixa propietat. E representa el grup de tots els estudiants, M representa els que tenen la propietat de «estudiar matemàtiques», P representa aquells que posseeix la propietat: de «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 = 2[modifica | modifica el codi]

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

|A\cup B|=|A|+|B|-|A\cap B|

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[modifica | modifica el codi]

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

\left|\,\bigcup_{i=1}^n A_i\,\right|=\sum_{i=1}^n\left|A_i\right|
-\sum_{(i,j)\,/\,1\leq i<j\leq n}\left|A_i\cap A_j\right|+\sum_{(i,j,k)\,/\,1\leq i<j<k\leq n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\cdots\ +(-1)^{n+1}|A_1\cap\ldots\cap A_n|

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

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

\left|\,\bigcup_{i=1}^n A_i\,\right|=\sum_{k=1}^n \left((-1)^{k-1} \sum_{1\leq i_1<i_2<\ldots<i_k\leq n} \left|A_{i_1}\cap A_{i_2}\cap \ldots \cap A_{i_k}\right|\right).

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:

\left|E\setminus\bigcup_{i=1}^n A_i\,\right|=|E|+\sum_{k=1}^n \left((-1)^{k} \sum_{1\leq i_1<i_2<\ldots<i_k\leq n} \left|A_{i_1}\cap A_{i_2}\cap \ldots \cap A_{i_k}\right|\right).

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

Versió probabilista[modifica | modifica el codi]

Siguin un espai de probabilitat \scriptstyle\ (\Omega,\mathcal{A},\mathbb{P})\ i \scriptstyle\ n\ elements \scriptstyle\ A_1, A_2, \dots,A_n\ de la tribu \scriptstyle\ \mathcal{A}.\ es té

\mathbb{P}\left(\,\bigcup_{i=1}^n A_i\,\right)=\sum_{k=1}^n \left((-1)^{k-1} \sum_{1\leq i_1<i_2<\ldots<i_k\leq n} \mathbb{P}\left(A_{i_1}\cap A_{i_2}\cap \ldots \cap A_{i_k}\right)\right).

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:

\mathbb{P}\left(\,\bigcup_{i=1}^n A_i\,\right)=\sum_{S\subset[\![1,n]\!],\,S\neq\varnothing} (-1)^{-1+|S|}\ \mathbb{P}\left(\bigcap_{i\in S}\,A_{i}\right).

Aplicacions[modifica | modifica el codi]

Desigualtats de Bonferroni[modifica | modifica el codi]

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 | modifica el codi]

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 \scriptstyle\ \mathbb{P}\left(\,N=0\right)\ ):

Proposició


Per a tot enter k comprès entre 0 i n
\mathbb{P}\left(\,N=k\right)\ =\ \frac{1}{k!}\quad\sum_{\ell=0}^{n-k}\ \frac{(-1)^{\ell}}{\ell!}.

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,[1] 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 | modifica el codi]

Notes[modifica | modifica el codi]

  1. 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 relacionades[modifica | modifica el codi]