El principio de inclusión-exclusión

El principio de inclusión-exclusión (inclusion-exclusion principle) es una técnica combinatoria importante para calcular el tamaño de un conjunto o la probabilidad de eventos complejos. Relaciona los tamaños de conjuntos individuales con el de su unión.

Enunciado

La fórmula verbal

El principio de inclusión-exclusión se puede expresar así:

Para calcular el tamaño de una unión de varios conjuntos, hay que sumar los tamaños de estos conjuntos por separado, luego restar los tamaños de todas las intersecciones por pares de los conjuntos, después volver a sumar el tamaño de las intersecciones de ternas de conjuntos, restar el tamaño de las cuádruplas de conjuntos, y así sucesivamente, hasta la intersección de todos los conjuntos.

Formulación en términos de conjuntos

La definición anterior se puede expresar matemáticamente de la siguiente manera:

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n|A_i| - \sum_{1\leq i<j\leq n} |A_i \cap A_j| + \sum _{1\leq i<j<k\leq n}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} | A_1 \cap \cdots \cap A_n |$$

Y de forma más compacta:

$$\left|\bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq J\subseteq {1,2,\ldots ,n}} (-1)^{|J|-1}{\Biggl |}\bigcap_{j\in J}A_{j}{\Biggr |}$$

Formulación con diagramas de Venn

Supongamos que el diagrama muestra tres conjuntos $A$, $B$ y $C$:

Entonces el área de su unión $A \cup B \cup C$ es igual a la suma de las áreas $A$, $B$ y $C$ menos las áreas cubiertas dos veces $A \cap B$, $A \cap C$, $B \cap C$, pero con la suma del área cubierta por los tres conjuntos $A \cap B \cap C$:

$$S(A \cup B \cup C) = S(A) + S(B) + S(C) - S(A \cap B) - S(A \cap C) - S(B \cap C) + S(A \cap B \cap C)$$

También se puede generalizar a una unión de $n$ conjuntos.

Formulación en términos de teoría de la probabilidad

Si $A_i$ $(i = 1,2…n)$ son eventos y ${\cal P}(A_i)$ la probabilidad de que ocurra un evento de $A_i$, entonces la probabilidad de su unión (es decir, la probabilidad de que ocurra al menos uno de los eventos) es igual a:

\begin{eqnarray} {\cal P} \left( \bigcup_{i=1}^n A_i \right) &amp;=&amp; \sum_{i=1}^n{\cal P}(A_i)\ - \sum_{1\leq i&lt;j\leq n} {\cal P}(A_i \cap A_j)\ + \ &amp;+&amp; \sum _{1\leq i&lt;j&lt;k\leq n}{\cal P}(A_i \cap A_j \cap A_k) - \cdots + (-1)^{n-1} {\cal P}( A_1 \cap \cdots \cap A_n ) \end{eqnarray}

Y de forma más compacta:

$${\cal P} \left(\bigcup_{i=1}^n A_i \right) = \sum_{\emptyset \neq J\subseteq {1,2,\ldots ,n}} (-1)^{|J|-1}\ {\cal P}{\Biggl (}\bigcap_{j\in J}A_{j}{\Biggr )}$$

Demostración

Para la demostración es conveniente usar la formulación matemática en términos de teoría de conjuntos:

$$\left|\bigcup_{i=1}^n A_i \right| = \sum_{\emptyset \neq J\subseteq {1,2,\ldots ,n}} (-1)^{|J|-1}{\Biggl |}\bigcap_{j\in J}A_{j}{\Biggr |}$$

Queremos probar que cualquier elemento contenido en al menos uno de los conjuntos $A_i$ aparece en la fórmula exactamente una vez (nótese que los elementos que no están presentes en ninguno de los conjuntos $A_i$ nunca se consideran en la parte derecha de la fórmula).

Consideremos un elemento $x$ que aparece en $k \geq 1$ conjuntos $A_i$. Mostraremos que se cuenta solo una vez en la fórmula. Nótese que:

• en los términos con $|J| = 1$, el elemento $x$ se contará $+\ k$ veces;
• en los términos con $|J| = 2$, el elemento $x$ se contará $-\ \binom{k}{2}$ veces, porque se contará en aquellos términos que incluyen dos de los $k$ conjuntos que contienen a $x$;
• en los términos con $|J| = 3$, el elemento $x$ se contará $+\ \binom{k}{3}$ veces;
• $\cdots$
• en los términos con $|J| = k$, el elemento $x$ se contará $(-1)^{k-1}\cdot \binom{k}{k}$ veces;
• en los términos con $|J| \gt k$, el elemento $x$ se contará cero veces;

Esto nos lleva a la siguiente suma de coeficientes binomiales:

$$T = \binom{k}{1} - \binom{k}{2} + \binom{k}{3} - \cdots + (-1)^{i-1}\cdot \binom{k}{i} + \cdots + (-1)^{k-1}\cdot \binom{k}{k}$$

Esta expresión es muy similar a la expansión binomial de $(1 - x)^k$:

$$(1 - x)^k = \binom{k}{0} - \binom{k}{1} \cdot x + \binom{k}{2} \cdot x^2 - \binom{k}{3} \cdot x^3 + \cdots + (-1)^k\cdot \binom{k}{k} \cdot x^k$$

Cuando $x = 1$, $(1 - x)^k$ se parece mucho a $T$. Sin embargo, la expresión tiene un $\binom{k}{0} = 1$ adicional, y está multiplicada por $-1$. Eso nos lleva a $(1 - 1)^k = 1 - T$. Por lo tanto $T = 1 - (1 - 1)^k = 1$, que es lo que queríamos demostrar. El elemento se cuenta solo una vez.

Generalización para calcular el número de elementos en exactamente $r$ conjuntos {data-toc-label=“Generalización para calcular el número de elementos en exactamente r conjuntos”}

El principio de inclusión-exclusión se puede reescribir para calcular el número de elementos que están presentes en cero conjuntos:

$$\left|\bigcap_{i=1}^n \overline{A_i}\right|=\sum_{m=0}^n (-1)^m \sum_{|X|=m} \left|\bigcap_{i\in X} A_{i}\right|$$

Consideremos su generalización para calcular el número de elementos que están presentes en exactamente $r$ conjuntos:

$$\left|\bigcup_{|B|=r}\left[\bigcap_{i \in B} A_i \cap \bigcap_{j \not\in B} \overline{A_j}\right]\right|=\sum_{m=r}^n (-1)^{m-r}\dbinom{m}{r} \sum_{|X|=m} \left|\bigcap_{i \in X} A_{i}\right|$$

Para demostrar esta fórmula, consideremos un $B$ particular. Por el principio básico de inclusión-exclusión podemos decir sobre él que:

$$\left|\bigcap_{i \in B} A_i \cap \bigcap_{j \not \in B} \overline{A_j}\right|=\sum_{m=r}^{n} (-1)^{m-r} \sum_{\substack{|X|=m \newline B \subset X}}\left|\bigcap_{i\in X} A_{i}\right|$$

Los conjuntos del lado izquierdo no se intersecan para distintos $B$, así que podemos sumarlos directamente. También hay que notar que cualquier conjunto $X$ siempre tendrá coeficiente $(-1)^{m-r}$ si aparece, y aparecerá para exactamente $\dbinom{m}{r}$ conjuntos $B$.

Uso al resolver problemas

El principio de inclusión-exclusión es difícil de entender sin estudiar sus aplicaciones.

Primero veremos tres tareas sencillas “en papel”, que ilustran aplicaciones del principio, y luego consideraremos problemas más prácticos que son difíciles de resolver sin el principio de inclusión-exclusión.

Las tareas que piden “encontrar el número de formas” merecen atención, porque a veces conducen a soluciones polinomiales, no necesariamente exponenciales.

Una tarea sencilla sobre permutaciones

Tarea: contar cuántas permutaciones de los números del $0$ al $9$ existen tales que el primer elemento sea mayor que $1$ y el último sea menor que $8$.

Contemos el número de permutaciones “malas”, es decir, permutaciones en las que el primer elemento es $\leq 1$ y/o el último es $\geq 8$.

Denotaremos por $X$ el conjunto de permutaciones en las que el primer elemento es $\leq 1$ y por $Y$ el conjunto de permutaciones en las que el último elemento es $\geq 8$. Entonces el número de permutaciones “malas”, según la fórmula de inclusión-exclusión, será:

$$|X \cup Y| = |X| + |Y| - |X \cap Y|$$

Tras un cálculo combinatorio sencillo, llegamos a:

$$2 \cdot 9! + 2 \cdot 9! - 2 \cdot 2 \cdot 8!$$

Solo queda restar este número del total de $10!$ para obtener el número de permutaciones “buenas”.

Una tarea sencilla sobre secuencias de (0, 1, 2)

Tarea: contar cuántas secuencias de longitud $n$ existen formadas solo por los números $0,1,2$ tales que cada número ocurre al menos una vez.

De nuevo pasamos al problema inverso, es decir, calculamos el número de secuencias que no contienen al menos uno de los números.

Denotemos por $A_i (i = 0,1,2)$ el conjunto de secuencias en las que el dígito $i$ no ocurre. La fórmula de inclusión-exclusión para el número de secuencias “malas” será:

$$|A_0 \cup A_1 \cup A_2| = |A_0| + |A_1| + |A_2| - |A_0 \cap A_1| - |A_0 \cap A_2| - |A_1 \cap A_2| + |A_0 \cap A_1 \cap A_2|$$

• El tamaño de cada $A_i$ es $2^n$, porque cada secuencia solo puede contener dos de los dígitos.
• El tamaño de cada intersección por pares $A_i \cap A_j$ es igual a $1$, porque solo habrá un dígito con el que construir la secuencia.
• El tamaño de la intersección de los tres conjuntos es igual a $0$, porque no habrá dígitos con los que construir la secuencia.

Como resolvimos el problema inverso, lo restamos del total de $3^n$ secuencias:

$$3^n - (3 \cdot 2^n - 3 \cdot 1 + 0)$$

Consideremos la siguiente ecuación:

$$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20$$

donde $0 \le x_i \le 8 ~ (i = 1,2,\ldots 6)$.

Tarea: contar el número de soluciones de la ecuación.

Olvidemos por un momento la restricción sobre $x_i$ y contemos simplemente el número de soluciones no negativas de esta ecuación. Esto se hace fácilmente usando estrellas y barras: queremos partir una secuencia de $20$ unidades en $6$ grupos, lo que es lo mismo que disponer $5$ barras y $20$ estrellas:

$$N_0 = \binom{25}{5}$$

Ahora calcularemos el número de soluciones “malas” con el principio de inclusión-exclusión. Las soluciones “malas” serán aquellas en las que uno o más $x_i$ son mayores o iguales que $9$.

Denotemos por $A_k ~ (k = 1,2\ldots 6)$ el conjunto de soluciones donde $x_k \ge 9$, y todos los demás $x_i \ge 0 ~ (i \ne k)$ (pueden ser $\ge 9$ o no). Para calcular el tamaño de $A_k$, nótese que esencialmente tenemos el mismo problema combinatorio que se resolvió en los dos párrafos anteriores, pero ahora $9$ de las unidades se excluyen de las ranuras y pertenecen definitivamente al primer grupo. Así:

$$| A_k | = \binom{16}{5}$$

De manera similar, el tamaño de la intersección entre dos conjuntos $A_k$ y $A_p$ (para $k \ne p$) es igual a:

$$\left| A_k \cap A_p \right| = \binom{7}{5}$$

El tamaño de cada intersección de tres conjuntos es cero, porque $20$ unidades no alcanzarán para tres o más variables mayores o iguales que $9$.

Combinando todo esto en la fórmula de inclusión-exclusión y dado que resolvimos el problema inverso, obtenemos por fin la respuesta:

$$\binom{25}{5} - \left(\binom{6}{1} \cdot \binom{16}{5} - \binom{6}{2} \cdot \binom{7}{5}\right)$$

Esto se generaliza fácilmente a $d$ números que suman $s$ con la restricción $0 \le x_i \le b$:

$$\sum_{i=0}^d (-1)^i \binom{d}{i} \binom{s+d-1-(b+1)i}{d-1}$$

Como arriba, tratamos los coeficientes binomiales con índice superior negativo como cero.

Nótese que este problema también se podría resolver con programación dinámica o funciones generatrices. La respuesta de inclusión-exclusión se calcula en tiempo $O(d)$ (suponiendo que las operaciones matemáticas como el coeficiente binomial son de tiempo constante), mientras que un enfoque de DP sencillo tomaría tiempo $O(ds)$.

El número de coprimos en un intervalo dado

Tarea: dados dos números $n$ y $r$, contar el número de enteros en el intervalo $[1;r]$ que son coprimos con $n$ (su máximo común divisor es $1$).

Resolvamos el problema inverso: calcular el número de enteros que no son coprimos con $n$.

Denotaremos los factores primos de $n$ como $p_i (i = 1\cdots k)$.

¿Cuántos números en el intervalo $[1;r]$ son divisibles por $p_i$? La respuesta a esta pregunta es:

$$\left\lfloor \frac{ r }{ p_i } \right\rfloor$$

Sin embargo, si simplemente sumamos estos números, algunos se contarán varias veces (aquellos que comparten varios $p_i$ como factores). Por lo tanto, es necesario usar el principio de inclusión-exclusión.

Iteraremos sobre todos los $2^k$ subconjuntos de los $p_i$, calcularemos su producto y sumaremos o restaremos el número de múltiplos de su producto.

Aquí hay una implementación en C++:

int solve (int n, int r) {
	vector<int> p;
	for (int i=2; i*i<=n; ++i)
		if (n % i == 0) {
			p.push_back (i);
			while (n % i == 0)
				n /= i;
		}
	if (n > 1)
		p.push_back (n);
 
	int sum = 0;
	for (int msk=1; msk<(1<<p.size()); ++msk) {
		int mult = 1,
			bits = 0;
		for (int i=0; i<(int)p.size(); ++i)
			if (msk & (1<<i)) {
				++bits;
				mult *= p[i];
			}
 
		int cur = r / mult;
		if (bits % 2 == 1)
			sum += cur;
		else
			sum -= cur;
	}
 
	return r - sum;
}

La cota asintótica de la solución es $O (\sqrt{n})$.

El número de enteros en un intervalo dado que son múltiplos de al menos uno de los números dados

Dados $n$ números $a_i$ y un número $r$. Se quiere contar el número de enteros en el intervalo $[1; r]$ que son múltiplos de al menos uno de los $a_i$.

El algoritmo de solución es casi idéntico al de la tarea anterior: construir la fórmula de inclusión-exclusión sobre los números $a_i$, es decir, cada término de esta fórmula es el número de números divisibles por un subconjunto dado de números $a_i$ (en otras palabras, divisibles por su mínimo común múltiplo).

Así que ahora iteraremos sobre todos los $2^n$ subconjuntos de enteros $a_i$ con $O(n \log r)$ operaciones para hallar su mínimo común múltiplo, sumando o restando el número de múltiplos de este en el intervalo. La cota asintótica es $O (2^n\cdot n\cdot \log r)$.

El número de strings que satisfacen un patrón dado

Consideremos $n$ patrones de strings de la misma longitud, formados solo por letras ($a…z$) o signos de interrogación. También se da un número $k$. Un string coincide con un patrón si tiene la misma longitud que el patrón y, en cada posición, o bien los caracteres correspondientes son iguales, o bien el carácter del patrón es un signo de interrogación. La tarea es contar el número de strings que coinciden exactamente con $k$ de los patrones (primer problema) y con al menos $k$ de los patrones (segundo problema).

Nótese primero que podemos contar fácilmente el número de strings que satisfacen a la vez todos los patrones especificados. Para ello, simplemente “cruzamos” los patrones: iteramos por las posiciones (“ranuras”) y miramos una posición en todos los patrones. Si todos los patrones tienen un signo de interrogación en esta posición, el carácter puede ser cualquier letra de $a$ a $z$. En caso contrario, el carácter de esta posición queda unívocamente determinado por los patrones que no contienen un signo de interrogación.

Aprendamos ahora a resolver la primera versión del problema: cuando el string debe satisfacer exactamente $k$ de los patrones.

Para resolverlo, iteramos y fijamos un subconjunto específico $X$ del conjunto de patrones formado por $k$ patrones. Entonces tenemos que contar el número de strings que satisfacen este conjunto de patrones, y solo coinciden con él, es decir, no coinciden con ningún otro patrón. Usaremos el principio de inclusión-exclusión de una manera un poco distinta: sumamos sobre todos los superconjuntos $Y$ (subconjuntos del conjunto original de strings que contienen a $X$), y o bien sumamos a la respuesta actual o la restamos del número de strings:

$$ans(X) = \sum_{Y \supseteq X} (-1)^{|Y|-k} \cdot f(Y)$$

Donde $f(Y)$ es el número de strings que coinciden con $Y$ (al menos $Y$).

(Si cuesta visualizar esto, se pueden dibujar diagramas de Venn.)

Si sumamos sobre todos los $ans(X)$, obtendremos la respuesta final:

$$ans = \sum_{X ~ : ~ |X| = k} ans(X)$$

Sin embargo, la cota asintótica de esta solución es $O(3^k \cdot k)$. Para mejorarla, nótese que distintos cálculos de $ans(X)$ comparten muy a menudo conjuntos $Y$.

Invertiremos la fórmula de inclusión-exclusión y sumaremos en términos de conjuntos $Y$. Ahora queda claro que el mismo conjunto $Y$ se tendría en cuenta en el cálculo de $ans(X)$ de $\binom{|Y|}{k}$ conjuntos con el mismo signo $(-1)^{|Y| - k}$.

$$ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot \binom{|Y|}{k} \cdot f(Y)$$

Ahora nuestra solución tiene cota asintótica $O(2^k \cdot k)$.

Resolveremos ahora la segunda versión del problema: hallar el número de strings que coinciden con al menos $k$ de los patrones.

Por supuesto, podemos usar la solución de la primera versión del problema y sumar las respuestas para conjuntos de tamaño mayor que $k$. Sin embargo, se puede notar que en este problema un conjunto $|Y|$ se considera en la fórmula para todos los conjuntos de tamaño $\ge k$ que están contenidos en $Y$. Dicho esto, podemos escribir la parte de la expresión que se multiplica por $f(Y)$ como:

$$(-1)^{|Y|-k} \cdot \binom{|Y|}{k} + (-1)^{|Y|-k-1} \cdot \binom{|Y|}{k+1} + (-1)^{|Y|-k-2} \cdot \binom{|Y|}{k+2} + \cdots + (-1)^{|Y|-|Y|} \cdot \binom{|Y|}{|Y|}$$

Mirando el libro de Graham (Graham, Knuth, Patashnik. “Concrete mathematics” [1998] ), vemos una fórmula conocida para coeficientes binomiales:

$$\sum_{k=0}^m (-1)^k \cdot \binom{n}{k} = (-1)^m \cdot \binom{n-1}{m}$$

Aplicándola aquí, encontramos que toda la suma de coeficientes binomiales se reduce a:

$$(-1)^{|Y|-k} \cdot \binom{|Y|-1}{|Y|-k}$$

Así, para esta tarea también obtuvimos una solución con cota asintótica $O(2^k \cdot k)$:

$$ans = \sum_{Y ~ : ~ |Y| \ge k} (-1)^{|Y|-k} \cdot \binom{|Y|-1}{|Y|-k} \cdot f(Y)$$

El número de formas de ir de una celda a otra

Hay un tablero $n \times m$, y $k$ de sus celdas son paredes intransitables. Un robot está inicialmente en la celda $(1,1)$ (abajo a la izquierda). El robot solo puede moverse a la derecha o hacia arriba, y eventualmente necesita llegar a la celda $(n,m)$, evitando todos los obstáculos. Hay que contar el número de formas en que puede hacerlo.

Supongamos que los tamaños $n$ y $m$ son muy grandes (por ejemplo, $10^9$), y el número $k$ es pequeño (alrededor de $100$).

Por ahora, ordenemos los obstáculos por su coordenada $x$ y, en caso de empate, por la coordenada $y$.

También aprendamos simplemente a resolver un problema sin obstáculos: es decir, a contar el número de formas de ir de una celda a otra. En un eje tenemos que atravesar $x$ celdas y en el otro, $y$ celdas. Por combinatoria elemental, obtenemos una fórmula usando coeficientes binomiales:

$$\binom{x+y}{x}$$

Ahora, para contar el número de formas de ir de una celda a otra evitando todos los obstáculos, se puede usar inclusión-exclusión para resolver el problema inverso: contar el número de formas de recorrer el tablero pisando un subconjunto de obstáculos (y restarlo del número total de formas).

Al iterar sobre un subconjunto de obstáculos que pisaremos, para contar el número de formas de hacerlo basta multiplicar el número de todos los caminos desde la celda inicial hasta el primero de los obstáculos seleccionados, del primer obstáculo al segundo, y así sucesivamente, y luego sumar o restar este número de la respuesta, de acuerdo con la fórmula estándar de inclusión-exclusión.

Sin embargo, esto de nuevo no será polinomial, con complejidad $O(2^k \cdot k)$.

Aquí va una solución polinomial:

Usaremos programación dinámica. Por conveniencia, insertamos $(1,1)$ al principio y $(n,m)$ al final del arreglo de obstáculos. Calculemos los números $d[i]$: el número de formas de ir del punto de partida ($0$-ésimo) al $i$-ésimo, sin pisar ningún otro obstáculo (excepto $i$, por supuesto). Calcularemos este número para todas las celdas-obstáculo, y también para la de llegada.

Olvidemos por un segundo los obstáculos y contemos simplemente el número de caminos de la celda $0$ a $i$. Hay que considerar algunos caminos “malos”, los que pasan por los obstáculos, y restarlos del número total de formas de ir de $0$ a $i$.

Al considerar un obstáculo $t$ entre $0$ e $i$ ($0 < t < i$) sobre el que podemos pisar, vemos que el número de caminos de $0$ a $i$ que pasan por $t$ y que tienen a $t$ como el primer obstáculo entre el inicio e $i$. Podemos calcularlo como: $d[t]$ multiplicado por el número de caminos arbitrarios de $t$ a $i$. Podemos contar el número de formas “malas” sumando esto para todo $t$ entre $0$ e $i$.

Podemos calcular $d[i]$ en $O(k)$ para $O(k)$ obstáculos, así que esta solución tiene complejidad $O(k^2)$.

El número de cuádruplas coprimas

Se dan $n$ números: $a_1, a_2, \ldots, a_n$. Se pide contar el número de formas de elegir cuatro números de modo que su máximo común divisor conjunto sea igual a uno.

Resolveremos el problema inverso: calcular el número de cuádruplas “malas”, es decir, cuádruplas en las que todos los números son divisibles por un número $d > 1$.

Usaremos el principio de inclusión-exclusión sumando sobre todos los grupos posibles de cuatro números divisibles por un divisor $d$.

$$ans = \sum_{d \ge 2} (-1)^{deg(d)-1} \cdot f(d)$$

donde $deg(d)$ es el número de primos en la factorización del número $d$ y $f(d)$ el número de cuádruplas divisibles por $d$.

Para calcular la función $f(d)$, basta contar el número de múltiplos de $d$ (como se mencionó en una tarea anterior) y usar coeficientes binomiales para contar el número de formas de elegir cuatro de ellos.

Así, usando la fórmula de inclusión-exclusión sumamos el número de grupos de cuatro divisibles por un número primo, luego restamos el número de cuádruplas que son divisibles por el producto de dos primos, sumamos cuádruplas divisibles por tres primos, etc.

El número de ternas armónicas

Se da un número $n \le 10^6$. Se pide contar el número de ternas $2 \le a < b < c \le n$ que satisfacen una de las siguientes condiciones:

• o bien ${\rm gcd}(a,b) = {\rm gcd}(a,c) = {\rm gcd}(b,c) = 1$,
• o bien ${\rm gcd}(a,b) > 1, {\rm gcd}(a,c) > 1, {\rm gcd}(b,c) > 1$.

Primero, pasemos directo al problema inverso: es decir, contar el número de ternas no armónicas.

Segundo, nótese que cualquier terna no armónica está formada por un par de coprimos y un tercer número que no es coprimo con al menos uno del par.

Así, el número de ternas no armónicas que contienen a $i$ es igual al número de enteros de $2$ a $n$ que son coprimos con $i$ multiplicado por el número de enteros que no son coprimos con $i$.

O bien $gcd(a,b) = 1 \wedge gcd(a,c) > 1 \wedge gcd(b,c) > 1$

o bien $gcd(a,b) = 1 \wedge gcd(a,c) = 1 \wedge gcd(b,c) > 1$

En ambos casos se contará dos veces. El primer caso se contará cuando $i = a$ y cuando $i = b$. El segundo caso se contará cuando $i = b$ y cuando $i = c$. Por lo tanto, para calcular el número de ternas no armónicas, sumamos este cálculo para todo $i$ de $2$ a $n$ y lo dividimos por $2$.

Ahora solo nos queda aprender a contar el número de coprimos con $i$ en el intervalo $[2;n]$. Aunque este problema ya se mencionó, la solución anterior no sirve aquí: requeriría la factorización de cada uno de los enteros de $2$ a $n$, y luego iterar por todos los subconjuntos de estos primos.

Es posible una solución más rápida con esta modificación de la criba de Eratóstenes:

1. Primero, hallamos todos los números en el intervalo $[2;n]$ tales que su factorización en primos no incluye un factor primo dos veces. También necesitaremos saber, para estos números, cuántos factores incluye.

   • Para ello mantendremos un arreglo $deg[i]$ para guardar el número de primos en la factorización de $i$, y un arreglo $good[i]$, para marcar si $i$ contiene cada factor a lo sumo una vez ($good[i] = 1$) o no ($good[i] = 0$). Al iterar de $2$ a $n$, si llegamos a un número que tiene $deg$ igual a $0$, entonces es primo y su $deg$ es $1$.
   • Durante la criba de Eratóstenes, iteraremos $i$ de $2$ a $n$. Al procesar un número primo recorremos todos sus múltiplos y aumentamos su $deg[]$. Si uno de estos múltiplos es múltiplo del cuadrado de $i$, entonces podemos poner $good$ como falso.

2. Segundo, necesitamos calcular la respuesta para todo $i$ de $2$ a $n$, es decir, el arreglo $cnt[]$: el número de enteros no coprimos con $i$.

   • Para ello, recordemos cómo funciona la fórmula de inclusión-exclusión: en realidad aquí implementamos el mismo concepto, pero con la lógica invertida: iteramos sobre un componente (un producto de primos de la factorización) y sumamos o restamos su término en la fórmula de inclusión-exclusión de cada uno de sus múltiplos.
   • Así, digamos que estamos procesando un número $i$ tal que $good[i] = true$, es decir, interviene en la fórmula de inclusión-exclusión. Iteramos por todos los números que son múltiplos de $i$, y o bien sumamos o restamos $\lfloor N/i \rfloor$ de su $cnt[]$ (el signo depende de $deg[i]$: si $deg[i]$ es impar, entonces debemos sumar; en caso contrario, restar).

Aquí hay una implementación en C++:

int n;
bool good[MAXN];
int deg[MAXN], cnt[MAXN];
 
long long solve() {
	memset (good, 1, sizeof good);
	memset (deg, 0, sizeof deg);
	memset (cnt, 0, sizeof cnt);
 
	long long ans_bad = 0;
	for (int i=2; i<=n; ++i) {
		if (good[i]) {
			if (deg[i] == 0)  deg[i] = 1;
			for (int j=1; i*j<=n; ++j) {
				if (j > 1 && deg[i] == 1)
					if (j % i == 0)
						good[i*j] = false;
					else
						++deg[i*j];
				cnt[i*j] += (n / i) * (deg[i]%2==1 ? +1 : -1);
			}
		}
		ans_bad += (cnt[i] - 1) * 1ll * (n-1 - cnt[i]);
	}
 
	return (n-1) * 1ll * (n-2) * (n-3) / 6 - ans_bad / 2;
}

La cota asintótica de nuestra solución es $O(n \log n)$, porque para casi todo número hasta $n$ hacemos $n/i$ iteraciones en el bucle anidado.

El número de permutaciones sin puntos fijos (desarreglos)

Probar que el número de permutaciones de longitud $n$ sin puntos fijos (es decir, ningún número $i$ está en la posición $i$; también llamadas desarreglos o derangements) es igual al siguiente número:

$$n! - \binom{n}{1} \cdot (n-1)! + \binom{n}{2} \cdot (n-2)! - \binom{n}{3} \cdot (n-3)! + \cdots \pm \binom{n}{n} \cdot (n-n)!$$

y aproximadamente igual a:

$$\frac{ n! }{ e }$$

(si se redondea esta expresión al entero más cercano, se obtiene exactamente el número de permutaciones sin puntos fijos)

Denotemos por $A_k$ el conjunto de permutaciones de longitud $n$ con un punto fijo en la posición $k$ ($1 \le k \le n$) (es decir, el elemento $k$ está en la posición $k$).

Ahora usamos la fórmula de inclusión-exclusión para contar el número de permutaciones con al menos un punto fijo. Para ello necesitamos aprender a contar tamaños de una intersección de conjuntos $A_i$, como sigue:

\begin{eqnarray} \left| A_p \right| &amp;=&amp; (n-1)!\ , \ \left| A_p \cap A_q \right| &amp;=&amp; (n-2)!\ , \ \left| A_p \cap A_q \cap A_r \right| &amp;=&amp; (n-3)!\ , \ \cdots , \end{eqnarray}

porque si sabemos que el número de puntos fijos es igual a $x$, entonces conocemos la posición de $x$ elementos de la permutación, y los demás $(n-x)$ elementos se pueden colocar en cualquier parte.

Sustituyendo esto en la fórmula de inclusión-exclusión, y dado que el número de formas de elegir un subconjunto de tamaño $x$ del conjunto de $n$ elementos es igual a $\binom{n}{x}$, obtenemos una fórmula para el número de permutaciones con al menos un punto fijo:

$$\binom{n}{1} \cdot (n-1)! - \binom{n}{2} \cdot (n-2)! + \binom{n}{3} \cdot (n-3)! - \cdots \pm \binom{n}{n} \cdot (n-n)!$$

Entonces el número de permutaciones sin puntos fijos es igual a:

$$n! - \binom{n}{1} \cdot (n-1)! + \binom{n}{2} \cdot (n-2)! - \binom{n}{3} \cdot (n-3)! + \cdots \pm \binom{n}{n} \cdot (n-n)!$$

Simplificando esta expresión, obtenemos expresiones exactas y aproximadas para el número de permutaciones sin puntos fijos:

$$n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{n!} \right ) \approx \frac{n!}{e}$$

(porque la suma entre paréntesis son los primeros $n+1$ términos de la expansión en serie de Taylor de $e^{-1}$)

Vale la pena notar que un problema similar se puede resolver de esta manera: cuando se necesita que los puntos fijos no estén entre los $m$ primeros elementos de las permutaciones (y no entre todos, como acabamos de resolver). La fórmula obtenida es como la fórmula exacta dada arriba, pero irá hasta la suma de $k$, en lugar de $n$.

Problemas de práctica

Una lista de tareas que se pueden resolver usando el principio de inclusión-exclusión:

• UVA #10325 “The Lottery” [difficulty: low] 
• UVA #11806 “Cheerleaders” [difficulty: low] 
• TopCoder SRM 477 “CarelessSecretary” [difficulty: low] 
• TopCoder TCHS 16 “Divisibility” [difficulty: low] 
• SPOJ #6285 NGM2 , “Another Game With Numbers” [difficulty: low] 
• TopCoder SRM 382 “CharmingTicketsEasy” [difficulty: medium] 
• TopCoder SRM 390 “SetOfPatterns” [difficulty: medium] 
• TopCoder SRM 176 “Deranged” [difficulty: medium] 
• TopCoder SRM 457 “TheHexagonsDivOne” [difficulty: medium] 
• SPOJ #4191 MSKYCODE “Sky Code” [difficulty: medium] 
• SPOJ #4168 SQFREE “Square-free integers” [difficulty: medium] 
• CodeChef “Count Relations” [difficulty: medium] 
• SPOJ - Almost Prime Numbers Again 
• SPOJ - Find number of Pair of Friends 
• SPOJ - Balanced Cow Subsets 
• SPOJ - EASY MATH [difficulty: medium] 
• SPOJ - MOMOS - FEASTOFPIGS [difficulty: easy] 
• Atcoder - Grid 2 [difficulty: easy] 
• Codeforces - Count GCD