En combinatoria , el principio de inclusión-exclusión permite expresar el número de elementos (o cardinal ) de una unión finita de conjuntos finitos en función del número de elementos de estos conjuntos y de sus intersecciones. Generaliza en términos de probabilidades .
Se atribuye al matemático Abraham de Moivre , y también conocido (él o su versión probabilística) con el nombre de fórmula de tamiz de Poincaré , fórmula de Poincaré o fórmula de tamiz .
Entre 20 estudiantes, 10 estudian matemáticas, 11 estudian física y 4 estudian ambos. ¿Cuántos estudiantes hay que no estudian matemáticas o física?
La construcción de un diagrama de Venn permite visualizar fácilmente la distribución general de los estudiantes.
Un área coloreada representa un grupo. E representa a todo el grupo de estudiantes, M representa a aquellos que tienen la propiedad de "estudiar matemáticas", P representa a aquellos que tienen la propiedad de "estudiar física".
Luego se anota el número de estudiantes para cada zona. Dado que cuatro personas estudian matemáticas y física, la intersección de los dos círculos tiene 4 estudiantes. Así que hay 10 - 4 = 6 personas que estudian matemáticas pero no física y 11 - 4 = 7 personas que estudian física pero no matemáticas. Por tanto, todavía hay 20 - (6 + 4 + 7) = 3 personas que no estudian matemáticas ni física.
Este resultado se encuentra fácilmente utilizando el principio de inclusión-exclusión que da el número de estudiantes que no tienen estas dos propiedades: 20 - 10 - 11 + 4 = 3.
Sean A y B dos conjuntos finitos, la fórmula se escribe
donde | A | y | B | representar el cardinal respectivo de A y B .
En otras palabras, podemos contar los elementos de la unión de dos conjuntos A y B sumando los cardinales de estos dos conjuntos y restando el cardinal de su intersección.
Sea A 1 , ..., A n n conjuntos finitos. Nosotros tenemos
donde | A | denota el cardinal de un conjunto finito A .
Esta fórmula también se puede escribir de una manera más condensada:
Teorema - .
Puede probarse por inducción en n , o usando las funciones del indicador .
Sea E un conjunto finito, que contiene los conjuntos A i . Deducimos, pasando al complementario, la cardinalidad del conjunto de elementos de E que no pertenecen a ninguno de los A i :
.El principio de inclusión-exclusión puede verse como un caso especial de generalización de la fórmula de inversión de Möbius .
Sea un espacio probabilizado y elementos de la tribu . Nosotros tenemos
.Esta fórmula se puede demostrar por inducción sobre n , o usando funciones indicadoras, de la misma manera que la fórmula anterior. También se puede formular de la siguiente manera:
.Las sumas parciales de los primeros términos de la fórmula proporcionan alternativamente un límite superior e inferior de la suma completa, y pueden usarse como aproximaciones de la última: estos aumentos y disminuciones se denominan desigualdades de Bonferroni , por el nombre de su autor, Carlo. Emilio Bonferroni .
En combinatoria, la fórmula del tamiz permite determinar el número de perturbaciones de un conjunto finito y, por tanto, resolver el problema de los encuentros . Un desarreglo de un conjunto X es una biyección de X sobre sí mismo sin un punto fijo . Gracias al principio de inclusión-exclusión, y tomando para A i el conjunto de permutaciones de X dejando i invariante, podemos demostrar que si la cardinalidad de X es igual an , entonces el número de perturbaciones de X es igual a . Es el número entero más cercano a n ! / E (donde e denota la base de los logaritmos naturales ). De ello se deduce que la probabilidad de que una biyección tomada al azar sea una perturbación tiende rápidamente hacia 1 / e mientras n tiende hacia el infinito.
Podemos impulsar más el estudio estadístico de los puntos fijos de las permutaciones . Denote por N ( ω ) el número de puntos fijos de una permutación ω . Este número es cero si y solo si ω es una falla. En esto, la siguiente proposición especifica el resultado relativo a las perturbaciones (que no es otro que el cálculo de ):
Proposición : para cualquier número entero k entre 0 y n ,
.En particular, la ley de N está muy cerca de la ley de Poisson del parámetro 1, para n grande. Esto ilustra el paradigma de Poisson , según el cual una suma de un gran número de variables de Bernoulli de pequeños parámetros y pobremente correlacionadas sigue aproximadamente la distribución de Poisson: N puede verse como tal suma. Este script permite calcular la media y la varianza de N más rápido que usar la expresión anterior de la Ley n .
El principio de inclusión-exclusión también permite mostrar, tomando para A τ el conjunto de permutaciones de X admitiendo un ciclo τ de orden 2, que el número de permutaciones que no tienen ciclo de orden 2 es , donde m es la parte entera de n / 2. De manera más general, el número de permutaciones que no tienen ciclo de orden p es , donde m es la parte entera de n / p .
Sean X e Y dos conjuntos finitos. Considere el conjunto de mapas de X a Y y, para cualquier elemento y de Y , el subconjunto de mapas que nunca toman el valor y . El conjunto de sobreyecciones de X a Y es entonces igual a y, por tanto, su cardinalidad es:
o nuevamente, por cambio de índice:
Proposición - Let . El número de sobreyecciones de un conjunto de elementos en un conjunto de elementos viene dado por:
.Dejar que m y n ser dos enteros estrictamente positivos. El número de Wortpitzky es el número de formas de colorear m cuadrados dispuestos en una línea con n colores, cada color aparece al menos una vez, y cada cuadrado también puede permanecer incoloro. Podemos encontrar una expresión para usar la versión probabilística del principio de inclusión-exclusión. Para cada cuadrado, dibujamos un color al azar entre {1, ..., n +1} con una distribución uniforme. Si el color dibujado es n +1, significa que el cuadrado es incoloro. Para cada color i que varía de 1 an , denotamos el evento: el color i no se usa en ningún cuadrado. Entonces tenemos:
para todo i < j . para todo i < j < ketc. La fórmula de inclusión-exclusión da:
La probabilidad del evento contrario no es otra que , por tanto, finalmente: