Principio de Inclusión-Exclusión (PIE)

Teoría

El Principio de Inclusión-Exclusión (PIE) es una técnica de conteo fundamental que te permite calcular el tamaño de la unión de varios conjuntos sumando y restando alternadamente los tamaños de sus intersecciones.

La intuición básica es que cuando sumas los tamaños de los conjuntos individuales, cuentas de más los elementos que pertenecen a varios conjuntos. Para corregir esto, restas las intersecciones. Pero luego los elementos que están en tres o más conjuntos se cuentan de menos, así que vuelves a sumar las intersecciones triples, y así sucesivamente.

El PIE es esencial para:

• Contar elementos que cumplen "al menos una" condición
• Problemas de desajustes (derangements)
• Contar funciones sobreyectivas
• Problemas que involucran múltiples restricciones

Fórmulas Clave

Dos conjuntos: $$|A \cup B| = |A| + |B| - |A \cap B|$$

Tres conjuntos: $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

Fórmula general (n conjuntos): $$\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| - \cdots + (-1)^{n+1}|A_1 \cap \cdots \cap A_n|$$

O en notación compacta: $$\left|\bigcup_{i=1}^n A_i\right| = \sum_{\emptyset \neq S \subseteq {1,\ldots,n}} (-1)^{|S|+1} \left|\bigcap_{i \in S} A_i\right|$$

Forma complementaria: $$\left|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}\right| = |U| - \left|\bigcup_{i=1}^n A_i\right|$$

donde $U$ es el conjunto universal.

Demostración

Demostración para dos conjuntos:

Divide $A \cup B$ en tres partes ajenas:

• Elementos que solo están en $A$: $A \setminus B$
• Elementos que solo están en $B$: $B \setminus A$
• Elementos en ambos: $A \cap B$

Entonces: $$|A \cup B| = |A \setminus B| + |B \setminus A| + |A \cap B|$$

Como $|A| = |A \setminus B| + |A \cap B|$ y $|B| = |B \setminus A| + |A \cap B|$:

$$|A| + |B| = |A \setminus B| + |A \cap B| + |B \setminus A| + |A \cap B| = |A \cup B| + |A \cap B|$$

Por lo tanto: $|A \cup B| = |A| + |B| - |A \cap B|$ $\square$

Demostración de la fórmula general (contando la contribución):

Toma un elemento $x$ que esté en exactamente $k$ de los conjuntos $A_1, \ldots, A_n$ con $k \geq 1$.

La idea es mostrar que el lado derecho de la ecuación cuenta a $x$ exactamente una vez.

$x$ contribuye con:

• $\binom{k}{1}$ a la suma $\sum |A_i|$
• $\binom{k}{2}$ a la suma $\sum |A_i \cap A_j|$
• $\binom{k}{m}$ a la suma de las intersecciones de $m$ conjuntos

Contribución total de $x$: $$\binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots + (-1)^{k+1}\binom{k}{k}$$

Por el teorema del binomio con $x = 1$: $$\sum_{m=0}^{k} (-1)^m \binom{k}{m} = (1-1)^k = 0$$

Por lo tanto: $$\sum_{m=1}^{k} (-1)^{m+1} \binom{k}{m} = -\sum_{m=1}^{k} (-1)^m \binom{k}{m} = -\left(-\binom{k}{0}\right) = 1$$

Así que cada elemento en la unión se cuenta exactamente una vez. $\square$