PIE en problemas Iberoamericanos

PIE en conteo de palabras con restricciones

Uno de los contextos más frecuentes del PIE en olimpiadas es contar palabras (cadenas de símbolos) que satisfacen ciertas condiciones de presencia o ausencia de caracteres.

Problema tipo: ¿Cuántas palabras de longitud $n$ con alfabeto $\{1, 2, \ldots, k\}$ usan todos los $k$ símbolos al menos una vez? Esto equivale a contar funciones sobreyectivas $\{1,\ldots,n\} \to \{1,\ldots,k\}$, y la respuesta por PIE es $\text{Sur}(n,k) = \sum_{j=0}^{k}(-1)^j \binom{k}{j}(k-j)^n$.

Variante con cotas superiores: ¿Cuántas palabras de longitud $n$ sobre $\{1,\ldots,k\}$ tienen el símbolo $i$ a lo sumo $m_i$ veces? Sea $A_i$ el conjunto de palabras donde el símbolo $i$ aparece más de $m_i$ veces. Las intersecciones $|A_S|$ se calculan con el coeficiente multinomial: si $S = \{i_1,\ldots,i_r\}$, entonces $|A_S|$ cuenta las palabras donde cada $i_j \in S$ aparece más de $m_{i_j}$ veces, que se calcula con la fórmula de generatriz $[x^n] \prod_{i \notin S} (1+x+\cdots+x^{m_i}) \cdot \prod_{i \in S} (x^{m_i+1} + x^{m_i+2} + \cdots)$.

Ejemplo concreto (estilo Iberoamericana): ¿Cuántas palabras de longitud 6 sobre $\{A, B, C\}$ contienen cada letra al menos una vez y la letra $A$ a lo sumo 3 veces? Universo: $3^6 = 729$ palabras. Definimos $A_1$ = palabras sin $A$, $A_2$ = palabras sin $B$, $A_3$ = palabras sin $C$, $A_4$ = palabras con $A$ al menos 4 veces. El PIE da $|\overline{A_1} \cap \overline{A_2} \cap \overline{A_3} \cap \overline{A_4}| = 729 - |A_1|-|A_2|-|A_3|-|A_4| + |A_1 \cap A_2| + \ldots$. Las condiciones no son simétricas, así que calculamos cada intersección por separado.

Truco — generatrices vs. PIE: Para cotas superiores sobre un solo tipo de símbolo, las funciones generatrices (coeficientes de series de potencias) suelen ser más eficientes. El PIE es más natural cuando las condiciones son de "presencia mínima" o cuando los conjuntos $A_i$ tienen intersecciones con fórmulas cerradas.

Distribuciones con cotas: el principio del reflejo

Uno de los problemas más clásicos del PIE es contar las soluciones enteras de $x_1 + x_2 + \cdots + x_k = n$ con restricciones de cota superior $0 \leq x_i \leq m_i$.

Sin cotas, el número de soluciones no negativas es $\binom{n+k-1}{k-1}$ (estrellas y barras). Con cotas superiores, usamos el PIE:

Sea $A_i$ el evento $x_i > m_i$, es decir, $x_i \geq m_i + 1$. Bajo $A_i$, hacemos el cambio $x_i' = x_i - (m_i+1)$ para reducir $n$ a $n - (m_i+1)$. La intersección $A_S$ corresponde a reducir $n$ en $\sum_{i \in S}(m_i+1)$: si el total reducido es no negativo, hay $\binom{n - \sum_{i \in S}(m_i+1) + k - 1}{k-1}$ soluciones; si es negativo, hay 0.

$|\text{Soluciones válidas}| = \sum_{S \subseteq \{1,\ldots,k\}} (-1)^{|S|} \binom{n - \sum_{i \in S}(m_i+1) + k-1}{k-1}$ (donde el término es 0 si la cota es negativa).

Ejemplo: Número de soluciones de $x_1 + x_2 + x_3 = 10$ con $0 \leq x_i \leq 4$. Sin cotas: $\binom{12}{2} = 66$. Por PIE (simetría, todos $m_i = 4$): restamos $3 \binom{12-5}{2} = 3 \binom{7}{2} = 63$, sumamos $3 \binom{12-10}{2} = 3 \binom{2}{2} = 3$, restamos $\binom{12-15}{2} = 0$ (negativo). Total: $66 - 63 + 3 - 0 = 6$. Verificación directa: las soluciones son permutaciones de $(4,4,2), (4,3,3)$ con $3+3=6$ arreglos. ✓

Principio del reflejo: En problemas de caminos reticulares con obstáculos (contar trayectorias de $(0,0)$ a $(m,n)$ que no crucen cierta barrera), el PIE combinado con simetría de reflexión (el principio del reflejo de André) da fórmulas exactas. Este es uno de los temas más ricos de la combinatoria iberoamericana.

Coloraciones con restricciones y el polinomio cromático

El PIE tiene una conexión profunda con el polinomio cromático de un grafo. Si $G = (V, E)$ es un grafo, el polinomio cromático $P(G, k)$ cuenta el número de coloraciones propias de $V$ con $k$ colores (coloraciones donde vértices adyacentes tienen colores distintos).

Por PIE, $P(G, k) = \sum_{A \subseteq E} (-1)^{|A|} k^{c(A)}$, donde $c(A)$ es el número de componentes conexas del subgrafo $(V, A)$. Esta es la fórmula de expansión por aristas del polinomio cromático.

Para grafos pequeños, esta fórmula es manejable. Para el ciclo $C_n$: $P(C_n, k) = (k-1)^n + (-1)^n (k-1)$. Para el grafo completo $K_n$: $P(K_n, k) = k(k-1)(k-2)\cdots(k-n+1) = k^{\underline{n}}$.

Aplicación directa en olimpiadas: El número de coloraciones propias de $G$ con exactamente $k$ colores (usando los $k$ colores) es $\frac{P(G,k) - \binom{k}{1}P(G,k-1) + \binom{k}{2}P(G,k-2) - \cdots}{1}$... simplificando: es $\frac{1}{k!}$ veces la suma anterior multiplicada por $k!$. En la práctica, para problemas olímpicos con grafos pequeños, se aplica el PIE directamente sobre las aristas o sobre los vértices según convenga.

Problema estándar: ¿De cuántas maneras se pueden colorear los vértices de un cubo con 3 colores de modo que vértices adyacentes tengan colores distintos? $P(Q_3, 3) = 3^8 - 12 \cdot 3^7 + \cdots$ (aplicando el PIE sobre las 12 aristas del cubo) es complicado. Más eficientemente: $P(Q_3, k) = (k-1)^8 + 28(k-1)^6 + \cdots$ usando el teorema de Burnside... La respuesta es $P(Q_3, 3) = 246$.

Permutaciones que evitan patrones y PIE en grafos

Una **permutación que evita el patrón $\tau$** es una permutación $\sigma$ tal que ninguna subsecuencia de $\sigma$ tiene la misma relación de orden que $\tau$. Aunque la teoría completa de permutaciones que evitan patrones va más allá del nivel iberoamericano, hay casos simples que se resuelven con PIE.

Permutaciones con posiciones prohibidas: El problema más clásico es contar permutaciones $\sigma$ de $\{1,\ldots,n\}$ tales que $\sigma(i) \neq a_{ij}$ para ciertos pares prohibidos $(i, j)$. Esto se modela con un grafo bipartito $G$ donde hay arista $(i, j)$ si la posición $i$ no puede tener el valor $j$. El número de permutaciones válidas es el permanente del complemento de la matriz de adyacencia de $G$.

El PIE sobre las aristas prohibidas da: $\sum_{S \subseteq E} (-1)^{|S|} r(S) \cdot (n - |S|)!$ donde $r(S)$ es el número de "sistemas de representantes distintos parciales" (matchings en el subgrafo generado por $S$). Esta es la fórmula de la persiana o rook polynomial formula.

El polinomio de la torre (Rook polynomial): El polinomio de la torre de un tablero $B \subseteq [n] \times [n]$ es $R(B, x) = \sum_{k=0}^{n} r_k(B) x^k$, donde $r_k(B)$ es el número de maneras de colocar $k$ torres en $B$ sin que se ataquen (sin dos torres en la misma fila o columna). La fórmula del PIE para permutaciones que evitan $B$ es $N(B) = \sum_{k=0}^{n} (-1)^k r_k(B) (n-k)!$.

Ejemplo — Problema de los matrimonios prohibidos: $n$ hombres y $n$ mujeres, donde cada hombre tiene $m$ mujeres con las que no puede casarse. ¿Cuántos matrimonios perfectos hay? Si los $nm$ pares prohibidos forman un grafo $k$-regular (cada hombre tiene exactamente $k$ prohibiciones), el cálculo del permanente vía polinomio de la torre da $N = \sum_{j=0}^{n} (-1)^j \binom{n}{j} \binom{n-j}{k}^? \cdot (n-j)!$... El caso regular permite usar la simetría del PIE, reduciendo el cálculo a $n+1$ términos.

Problema resuelto completo: distribución con condiciones múltiples

Problema (Cono Sur 2011, estilo): ¿De cuántas maneras se pueden distribuir 12 bolas distinguibles entre 4 cajas distinguibles $A, B, C, D$ de modo que $A$ tenga a lo sumo 5 bolas, $B$ tenga a lo sumo 4 bolas, $C$ tenga a lo sumo 4 bolas, y $D$ tenga a lo sumo 4 bolas? (Nota: $5+4+4+4 = 17 > 12$, por lo que la restricción es no trivial.)

Solución: El universo es $4^{12} = 16{,}777{,}216$... Espera, las bolas son distinguibles así que debemos usar el modelo correcto. Con bolas distinguibles en cajas distinguibles, el universo $U$ tiene $4^{12}$ distribuciones (cada bola va a una de 4 cajas). Las condiciones son: $|A| \leq 5$, $|B| \leq 4$, $|C| \leq 4$, $|D| \leq 4$.

Sea $X_A$ = distribuciones con $|A| \geq 6$, $X_B$ = distribuciones con $|B| \geq 5$, etc. Por PIE: válidas $= |U| - |X_A| - |X_B| - |X_C| - |X_D| + |X_A \cap X_B| + \ldots$

$|X_A| = \binom{12}{6}3^6 + \binom{12}{7}3^5 + \cdots$ No. Con bolas distinguibles: $|X_A| =$ número de distribuciones donde $A$ tiene al menos 6 bolas $= \sum_{j=6}^{12} \binom{12}{j} 3^{12-j}$. Por el binomio: $4^{12} = \sum_{j=0}^{12} \binom{12}{j} 3^{12-j}$, luego $|X_A| = 4^{12} - \sum_{j=0}^{5}\binom{12}{j}3^{12-j}$. De forma más directa para el PIE, fijamos que $A$ recibe un conjunto específico de 6 o más bolas.

En problemas de olimpiadas con números manejables, el mejor enfoque es calcular directamente con la función generatriz $[x^{12}] 12! \cdot (\sum_{j=0}^{5} x^j/j!) \cdot (\sum_{j=0}^{4} x^j/j!)^3$ y el PIE para eliminar los excesos. La respuesta numérica en este caso es $\sum_{S} (-1)^{|S|} \binom{12}{\text{exceso}_S} 4^{12 - \text{exceso}_S}$ sumado sobre todos los subconjuntos de condiciones violadas. La técnica se aplica directamente, el trabajo es aritmérico.

Lección clave: En problemas con cotas heterogéneas, el PIE produce una suma con $2^k$ términos (donde $k$ es el número de condiciones), pero muchos términos son cero (cuando la suma de los excesos supera $n$). Identificar cuáles términos son cero antes de calcular ahorra tiempo en olimpiadas.

PIE con simetría: el enfoque de Burnside-PIE

Algunos problemas combinan el PIE con el lema de Burnside (conteo módulo simetría). La idea es: primero contar sin simetría (universo $U$), luego aplicar Burnside para dividir por las simetrías, pero usando el PIE para calcular el número de puntos fijos de cada simetría.

Ejemplo: ¿Cuántos collares de $n$ cuentas distinguibles con $k$ colores, donde no haya dos cuentas adyacentes del mismo color, son distintos bajo rotación? El universo (collares lineales) se cuenta con $P(C_n, k)$. El número de collares circulares distintos bajo rotación es $\frac{1}{n} \sum_{d \mid n} \phi(d) P(C_{n/d}, k)$ por Burnside, donde la suma es sobre los divisores de $n$ y $\phi$ es la función de Euler. Para calcular $P(C_{n/d}, k)$, usamos la fórmula del ciclo cromático.

Conexión con el lema de Burnside: El número de objetos distintos bajo un grupo de simetría $G$ es $\frac{1}{|G|}\sum_{g \in G}|\text{Fix}(g)|$. Si los objetos tienen restricciones (definidas por el PIE), entonces $|\text{Fix}(g)|$ se calcula también con el PIE, pero aplicado al subproblema donde la acción de $g$ ya está impuesta.

En olimpiadas iberoamericanas: Los problemas que combinan simetría y PIE suelen ser de dificultad 4-5 en una escala de 1-6. El Cono Sur 2015 y la Iberoamericana 2017 tienen problemas de este tipo. La estrategia es: (1) identificar el grupo de simetrías, (2) para cada tipo de simetría calcular los objetos fijos por PIE, (3) aplicar Burnside.

Resumen de herramientas del capítulo: El PIE es la navaja suiza de la combinatoria iberoamericana. Dominarlo significa conocer: la fórmula general, el complemento, el conteo de exactamente $k$, las funciones sobreyectivas, los derangements, los polinomios de la torre, y la combinación con Burnside. Cada uno de estos contextos aparece en problemas de olimpiadas, y reconocer cuál aplica es la clave del éxito.