Suma alternada para n conjuntos.
El Principio de Inclusión-Exclusión (PIE) es una técnica de conteo fundamental en combinatoria que usas para determinar el tamaño de la unión de conjuntos finitos. Cuando quieres encontrar el número total de elementos en la unión de varios conjuntos, si solo sumas los tamaños de los conjuntos individuales vas a contar de más, porque los elementos que pertenecen a varios conjuntos los cuentas más de una vez. PIE te da un método sistemático para corregir este error: restas los tamaños de las intersecciones de dos en dos, sumas las de tres en tres, restas las de cuatro en cuatro, y así te sigues.
Esta técnica es súper potente cuando es difícil contar un conjunto de objetos directamente, pero es fácil contar los objetos que cumplen con subconjuntos específicos de propiedades. Por ejemplo, PIE es clave para resolver problemas de desarreglos (permutaciones sin puntos fijos), para contar funciones sobreyectivas entre conjuntos y para calcular la función totiente de Euler en teoría de números. Transforma una condición complicada de "al menos una" propiedad en una suma alternada de restricciones de intersección más simples.
La intuición detrás de la fórmula parte de un proceso de corrección alternado. Al sumar los conjuntos individuales, cuentas un elemento que está en $k$ conjuntos exactamente $k$ veces. Al restar las intersecciones de dos en dos quitas los conteos extra, pero podrías estar quitando demasiado para los elementos que están en tres o más conjuntos. Sumar las intersecciones de tres en tres corrige esto, y el proceso sigue hasta que la contribución de cada elemento en la unión queda balanceada en exactamente 1.
Sean $A_1, A_2, \dots, A_n$ subconjuntos finitos de un universo finito $U$.
La Fórmula General para la Unión: La cardinalidad de la unión de estos conjuntos es: $$ \left| \bigcup_{i=1}^n A_i \right| = \sum_{1 \le i \le n} |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j| + \sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} |A_1 \cap