PIE: identidades y formulación general

Motivación: el error del conteo ingenuo

El conteo ingenuo suma $|A_1| + |A_2| + \cdots + |A_n|$ para obtener el tamaño de la unión, pero esto sobrecontea los elementos que pertenecen a más de un conjunto. El principio de inclusión-exclusión (PIE) es la corrección sistemática de este error.

El nombre describe el proceso: primero *incluimos* todos los conjuntos individuales (con signo $+$), luego *excluimos* todas las intersecciones de pares (con signo $-$), luego volvemos a incluir las intersecciones de triples (con signo $+$), y así alternando signos hasta llegar a la intersección de todos los conjuntos.

Históricamente, casos especiales del PIE aparecen en los trabajos de Nicolaus Bernoulli sobre derangements (1710) y en los cálculos de Euler sobre la función $\phi$ (1763). La formulación general moderna se atribuye a Sylvester (1883), aunque el principio subyacente era conocido antes.

En las olimpiadas iberoamericanas, el PIE es la herramienta central para problemas de conteo con condiciones de exclusión: "ninguno de los objetos satisface la propiedad P", "exactamente $k$ objetos satisfacen la propiedad P", o "¿cuántas funciones evitan ciertos valores?"

La fórmula general del PIE

Sean $A_1, A_2, \ldots, A_n$ subconjuntos finitos de un universo $U$. El principio de inclusión-exclusión establece:

Donde la suma recorre todos los subconjuntos no vacíos $S \subseteq \{1, 2, \ldots, n\}$ y $A_S = \bigcap_{i \in S} A_i$ (con la convención $A_\emptyset = U$). Expandida explícitamente:

$\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 A_2 \cap \cdots \cap A_n|$.

Demostración: Sea $x \in U$ un elemento que pertenece exactamente a $m$ de los $n$ conjuntos (digamos $A_{i_1}, \ldots, A_{i_m}$). Calculamos la contribución de $x$ al lado derecho. En el término $\sum_{|S|=k} |A_S|$, el elemento $x$ pertenece a $A_S$ si y solo si $S \subseteq \{i_1, \ldots, i_m\}$; hay $\binom{m}{k}$ tales subconjuntos $S$. Por tanto $x$ contribuye $\sum_{k=1}^{m} (-1)^{k-1} \binom{m}{k}$ al lado derecho.

Por el binomio: $\sum_{k=0}^{m} (-1)^k \binom{m}{k} = (1-1)^m = 0$ para $m \geq 1$, luego $\sum_{k=1}^{m} (-1)^{k-1} \binom{m}{k} = 1$. Así, todo elemento de $\bigcup_i A_i$ contribuye exactamente 1, y los elementos fuera de la unión (con $m = 0$) contribuyen 0. Esto prueba la fórmula. $\square$

La clave es la identidad telescópica $\sum_{k=1}^{m} (-1)^{k-1} \binom{m}{k} = 1$, que se puede recordar como "cada elemento que pertenece a la unión es contado exactamente una vez con el PIE".

El complemento: contar lo que queda fuera

Una formulación equivalente y frecuentemente más útil cuenta los elementos que no pertenecen a ningún $A_i$, es decir, los elementos del complemento de la unión:

$\left|\overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n}\right| = |U| - \sum_{i}|A_i| + \sum_{i<j}|A_i \cap A_j| - \cdots + (-1)^n |A_1 \cap \cdots \cap A_n|$.

En la práctica olímpica, esta forma es la más útil: el universo $U$ es todo el conjunto de objetos posibles, cada $A_i$ es el conjunto de objetos que "violan la condición $i$", y queremos contar los objetos que satisfacen todas las condiciones (es decir, los de $\overline{A_1} \cap \cdots \cap \overline{A_n}$).

Ejemplo prototípico: ¿Cuántos enteros entre 1 y 100 no son divisibles por 2, ni por 3, ni por 5? Tomamos $U = \{1, \ldots, 100\}$, $A_2$ = múltiplos de 2, $A_3$ = múltiplos de 3, $A_5$ = múltiplos de 5. Por PIE: $|\overline{A_2} \cap \overline{A_3} \cap \overline{A_5}| = 100 - \lfloor 100/2 \rfloor - \lfloor 100/3 \rfloor - \lfloor 100/5 \rfloor + \lfloor 100/6 \rfloor + \lfloor 100/10 \rfloor + \lfloor 100/15 \rfloor - \lfloor 100/30 \rfloor = 100 - 50 - 33 - 20 + 16 + 10 + 6 - 3 = 26$.

La conexión con la función de Euler: $\phi(30) = 30(1 - 1/2)(1 - 1/3)(1 - 1/5) = 8$, y $\lfloor 100/30 \rfloor = 3$ grupos completos más $100 - 3 \cdot 30 = 10$ elementos del último grupo parcial. El PIE generaliza esta idea a cualquier modular aritmética.

Contar elementos en exactamente $k$ conjuntos

El PIE generaliza a contar elementos que pertenecen a exactamente $k$ de los $n$ conjuntos. Sea $E_k$ ese número. Definamos $S_j = \sum_{|T|=j} |A_T|$ (la suma de tamaños de intersecciones de $j$ conjuntos). Entonces:

$E_k = \sum_{j=k}^{n} (-1)^{j-k} \binom{j}{k} S_j$.

En particular, $E_0 = \sum_{j=0}^{n} (-1)^j S_j = |\overline{A_1} \cap \cdots \cap \overline{A_n}|$ (el PIE estándar) y $E_1 = \sum_{j=1}^{n} (-1)^{j-1} (j) S_j / j = \ldots$ que simplifica a la fórmula conocida.

Demostración: Un elemento $x$ que pertenece a exactamente $m$ de los conjuntos contribuye $\binom{m}{j}$ al término $S_j$. Su contribución a $E_k$ según la fórmula es $\sum_{j=k}^{m} (-1)^{j-k} \binom{j}{k} \binom{m}{j}$. Usando la identidad $\binom{j}{k}\binom{m}{j} = \binom{m}{k}\binom{m-k}{j-k}$, la suma es $\binom{m}{k} \sum_{i=0}^{m-k} (-1)^i \binom{m-k}{i} = \binom{m}{k} \cdot [m = k]$. Luego $x$ contribuye 1 a $E_k$ si $m = k$ y 0 en otro caso. $\square$

**Forma especial — al menos $k$:** El número $A_k^{\geq}$ de elementos en al menos $k$ conjuntos satisface $A_k^{\geq} = \sum_{j=k}^{n} (-1)^{j-k} \binom{j-1}{k-1} S_j$. Para $k=1$ se recupera el PIE estándar.

Aplicación: En un grupo de 30 estudiantes, 18 hablan inglés, 15 hablan francés, 10 hablan alemán, 8 hablan inglés y francés, 5 hablan inglés y alemán, 4 hablan francés y alemán, 2 hablan los tres. ¿Cuántos hablan exactamente dos idiomas? $E_2 = \sum_{|T|=2} |A_T| - 3 \cdot |A_1 \cap A_2 \cap A_3| = (8 + 5 + 4) - 3 \cdot 2 = 17 - 6 = 11$.

Funciones sobreyectivas y el número de Stirling

Una aplicación fundamental del PIE es contar las funciones sobreyectivas de un conjunto de $n$ elementos a uno de $k$ elementos. El número de tales funciones es:

$\text{Sur}(n, k) = \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n$.

Demostración: Sea $U$ el conjunto de todas las $k^n$ funciones $f: \{1,\ldots,n\} \to \{1,\ldots,k\}$. Para cada $i \in \{1,\ldots,k\}$, sea $A_i$ el conjunto de funciones que no toman el valor $i$ (es decir, $i \notin \text{Im}(f)$). Entonces $|A_S| = (k - |S|)^n$ para todo $S \subseteq \{1,\ldots,k\}$ (las funciones que evitan todos los valores en $S$). Las funciones sobreyectivas son las que no están en ningún $A_i$: $|\overline{A_1} \cap \cdots \cap \overline{A_k}| = \sum_{j=0}^{k} (-1)^j \binom{k}{j}(k-j)^n$.

Conexión con Stirling: $\text{Sur}(n,k) = k! \cdot S(n,k)$ donde $S(n,k)$ es el número de Stirling de segunda clase (particiones de $\{1,\ldots,n\}$ en $k$ bloques no vacíos). Esto es porque cada función sobreyectiva corresponde a $k!$ funciones si etiquetamos los bloques, y a una partición si no etiquetamos.

Ejemplo: Las funciones sobreyectivas de $\{1,2,3,4\}$ a $\{1,2,3\}$ son: $\text{Sur}(4,3) = \binom{3}{0}3^4 - \binom{3}{1}2^4 + \binom{3}{2}1^4 - \binom{3}{3}0^4 = 81 - 48 + 3 - 0 = 36 = 3! \cdot S(4,3) = 6 \cdot 6$. ✓

Uso en distribución: El número de maneras de colocar $n$ objetos distinguibles en $k$ cajas distinguibles sin dejar ninguna vacía es $\text{Sur}(n,k)$. En problemas de olimpiadas: "¿de cuántas maneras se pueden distribuir $n$ regalos entre $k$ niños de modo que cada niño reciba al menos uno?"

Estrategia olímpica para problemas con PIE

El PIE tiene un procedimiento estándar en olimpiadas: (1) definir el universo $U$ y los conjuntos "malos" $A_i$; (2) calcular las intersecciones $|A_S|$ para cada subconjunto $S$; (3) aplicar la fórmula.

Paso 1 — Identificar la estructura: El PIE es apropiado cuando el problema pide contar objetos que evitan ciertas propiedades, o que cumplen todas las condiciones en una lista. Las palabras clave son "ninguno", "todos", "al menos uno de los cuales", "exactamente $k$".

Paso 2 — Simetría: En muchos problemas, todas las intersecciones del mismo tamaño son iguales: $|A_S| = f(|S|)$ para alguna función $f$ (porque los $A_i$ son "intercambiables"). Esto simplifica el PIE a $|\overline{\bigcup A_i}| = \sum_{j=0}^{n} (-1)^j \binom{n}{j} f(j)$, que es una suma de solo $n+1$ términos.

**Paso 3 — Computar $f(j)$:** Con la simetría, el trabajo se reduce a calcular el tamaño de $A_S$ para un solo $S$ de cada tamaño. Frecuentemente, $|A_S|$ tiene una fórmula simple en $|S|$.

Ejemplo estándar — Problemas de arreglos: ¿Cuántas permutaciones de $\{1,\ldots,n\}$ evitan que cualquier primo $p_1, \ldots, p_k$ (donde $p_i \leq n$) aparezca en la posición $p_i$? Sea $A_i$ el conjunto de permutaciones con $p_i$ en la posición $p_i$. Entonces $|A_S| = (n - |S|)!$ (las $n - |S|$ posiciones restantes son libres), y la simetría aplica si todos los $p_i$ son distintos. El resultado es $\sum_{j=0}^{k} (-1)^j \binom{k}{j} (n-j)!$.

Trampa frecuente: Asegurarse de que los $A_i$ sean disjuntos en su definición o de que el conteo de intersecciones sea correcto. Un error común es calcular $|A_i \cap A_j|$ ignorando que un objeto puede violar ambas condiciones de formas distintas.