Principio de inclusión-exclusión
El principio de inclusión-exclusión calcula el tamaño de una unión de conjuntos sumando y restando alternativamente los tamaños de sus intersecciones.
Definition
Una identidad de conteo que establece que la cardinalidad de una unión de conjuntos finitos es igual a la suma alternada de las cardinalidades de todas sus intersecciones, tomadas sobre cada subcolección no vacía.
Scope
Este tema presenta la fórmula de inclusión-exclusión y sus aplicaciones para contar objetos que evitan una lista de propiedades prohibidas: desórdenes, sobreyecciones, la función totient de Euler y el número de enteros coprimos a un número dado. Introduce el punto de vista de la criba y la generalización de la función de Möbius sobre conjuntos parcialmente ordenados, lo que sitúa el principio en un contexto algebraico más amplio.
Core questions
- ¿Cuántos elementos satisfacen al menos una de varias condiciones superpuestas?
- ¿Cómo se pueden contar objetos que evitan todas las propiedades de un conjunto de propiedades prohibidas?
- ¿Cómo se derivan del principio los recuentos de desórdenes y sobreyecciones?
- ¿Cómo generaliza la función de Möbius en un poset la inclusión-exclusión?
Key concepts
- Unión de conjuntos superpuestos
- Método de la criba
- Desórdenes mediante inclusión-exclusión
- Conteo de sobreyecciones
- Función totient de Euler
- Función de Möbius en posets
Key theories
- Fórmula de inclusión-exclusión
- La cardinalidad de una unión de conjuntos A_1 a A_n es igual a la suma de los tamaños de los conjuntos individuales menos las intersecciones por pares más las intersecciones triples, y así sucesivamente, corrigiendo sistemáticamente el recuento excesivo de elementos compartidos.
- Inversión de Möbius en posets
- La generalización de Stanley basada en la teoría de posets reemplaza los signos alternos de la inclusión-exclusión con la función de Möbius de un conjunto parcialmente ordenado, unificando el principio con las fórmulas de inversión de la teoría de números y de la teoría de retículos.
Clinical relevance
La idea de la criba se generaliza a la teoría de números (la criba de Eratóstenes y las cribas analíticas), la probabilidad (las desigualdades de Bonferroni que acotan las probabilidades de unión) y el análisis de fiabilidad de sistemas con modos de fallo superpuestos.
History
En esencia, enunciado por de Moivre y Sylvester, el principio fue situado dentro de una teoría general de las funciones de Möbius en conjuntos parcialmente ordenados por Rota en 1964, un hito de la combinatoria moderna.
Key figures
- Abraham de Moivre
- Gian-Carlo Rota
Related topics
Seminal works
- stanley2011
Frequently asked questions
- ¿Por qué los signos son alternos?
- Los elementos que se encuentran en varios de los conjuntos se suman demasiadas veces; la resta de las intersecciones por pares corrige en exceso, por lo que las intersecciones triples se vuelven a sumar, produciendo el patrón alterno que cuenta cada elemento exactamente una vez.
- ¿Cuál es la conexión con la función de Möbius?
- La inclusión-exclusión es el caso especial de la inversión de Möbius en el retículo booleano de subconjuntos, donde la función de Möbius toma valores de más o menos uno.