Fórmula General del PIE

Teoría

El Principio de Inclusión-Exclusión (PIE) es un método combinatorio muy robusto que sirve para calcular la cardinalidad de la unión de conjuntos finitos. La intuición detrás del principio es la de una sobrecorrección sistemática. Si quieres contar cuántos elementos hay en la unión de $n$ conjuntos, sumar simplemente los tamaños de los conjuntos individuales hace que cuentes de más, ya que los elementos que pertenecen a varios conjuntos se cuentan más de una vez. Para corregir esto, restas los tamaños de todas las intersecciones de dos en dos. Sin embargo, esta resta quita demasiadas veces los elementos que pertenecen a tres conjuntos, así que tienes que volver a sumar los tamaños de todas las intersecciones de tres en tres. Sigues con este proceso alternado de sumar y restar tamaños de intersecciones hasta que llegas a la intersección de los $n$ conjuntos.

Esta técnica es especialmente poderosa porque transforma un problema sobre una "Unión" (un O lógico) —que a menudo es difícil de contar directamente por los traslapes— en un cálculo que involucra "Intersecciones" (un Y lógico). En las olimpiadas de matemáticas, el PIE es indispensable para resolver problemas de permutaciones con restricciones (como los desajustes o derangements), para contar funciones sobreyectivas y en problemas de teoría de números que involucran divisibilidad por varios primos. Lo más frecuente es aplicarlo en su forma complementaria: calcular el número de elementos de un conjunto universal $S$ que no tienen ninguna de las propiedades $A_1, \dots, A_n$.

Fórmulas Clave

La Fórmula General de Inclusión-Exclusión Para conjuntos finitos $A_1, A_2, \dots, A_n$, la cardinalidad de su unión es: $$ \left| \bigcup_{i=1}^n A_i \right| = \sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i < j < k} |A_i \cap A_j \cap A_k| - \dots + (-1)^{n-1} \left| \bigcap_{i=1}^n A_i \right| $$

Notación Compacta Si tomas un subconjunto no vacío de índices $J \subseteq {1, 2, \dots, n}$, la fórmula se puede escribir de forma concisa así: $$ \left| \bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq J \subseteq {1, \dots, n}} (-1)^{|J|-1} \left| \bigcap_{j \in J} A_j \right| $$

Forma Complementaria Muchas veces, lo que quieres es contar cuántos elementos de un conjunto universal $S$ no están en ninguno de los conjuntos $A_i$ (es decir, elementos que no cumplen ninguna de las propiedades). $$ \left| \bigcap_{i=1}^n \overline{A_i} \right| = |S| - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + \dots + (-1)^n \left| \bigcap_{i=1}^n A_i \right| $$

Demostración

Aquí tienes una demostración combinatoria contando cuánto aporta un elemento cualquiera $x$ a cada lado de la ecuación. La idea es mostrar que cada elemento que está en la unión se cuenta exactamente una vez en la expresión del lado derecho, y cada elemento que no está en la unión se cuenta cero veces.

Toma un elemento $x$ del conjunto universal. Supón que $x$ pertenece exactamente a $k$ de los conjuntos $A_1, A_2, \dots, A_n$.

Caso 1: $k = 0$ Si $x$ no pertenece a ninguno de los conjuntos, entonces no está en la unión $\bigcup A_i$, así que aporta 0 al lado izquierdo. En el lado derecho, $x$ no está en ningún $A_i$, ni en ninguna intersección de estos conjuntos. Por lo tanto, cada término del lado derecho es 0. La igualdad $0=0$ se cumple.

Caso 2: $k > 0$ Si $x$ pertenece a exactamente $k$ conjuntos, aporta 1 al lado izquierdo. Hay que mostrar que la suma alternada del lado derecho también da 1. Fíjate en los términos del lado derecho:

• En la primera suma $\sum |A_i|$, $x$ se cuenta exactamente $\binom{k}{1}$ veces (una vez por cada uno de los $k$ conjuntos a los que pertenece).
• En la segunda suma $\sum |A_i \cap A_j|$, $x$ se cuenta exactamente $\binom{k}{2}$ veces (una vez por cada pareja de conjuntos elegida de los $k$ conjuntos que contienen a $x$).
• En general, para la $m$-ésima suma que involucra intersecciones de $m$ conjuntos, $x$ se cuenta $\binom{k}{m}$ veces.
• Nota que si $m > k$, $x$ no puede estar en la intersección de $m$ conjuntos, así que la cuenta es $\binom{k}{m} = 0$.

Entonces, el aporte total de $x$ al lado derecho es: $$ C = \binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \dots + (-1)^{k-1}\binom{k}{k} $$ Recuerda la expansión binomial de $(1-1)^k$: $$ 0 = (1-1)^k = \sum_{i=0}^k \binom{k}{i}(-1)^i = \binom{k}{0} - \binom{k}{1} + \binom{k}{2} - \dots + (-1)^k\binom{k}{k} $$ Si despejas el primer término $\binom{k}{0}$: $$ \binom{k}{0} = \binom{k}{1} - \binom{k}{2} + \dots - (-1)^k\binom{k}{k} $$ Como $\binom{k}{0} = 1$ y $-(-1)^k = (-1)^{k-1}$, tienes que: $$ 1 = \binom{k}{1} - \binom{k}{2} + \dots + (-1)^{k-1}\binom{k}{k} $$ Esto coincide con la expresión para $C$. Por lo tanto, cualquier elemento que esté en al menos un conjunto se cuenta exactamente una vez.

$\square$