O princípio da inclusão-exclusão

O princípio de inclusão-exclusão é uma maneira combinatória importante de calcular o tamanho de um conjunto ou a probabilidade de eventos complexos. Ele relaciona o tamanho de conjuntos individuais com sua união.

Descrição

A fórmula verbal

O princípio de inclusão-exclusão pode ser expresso da seguinte maneira:

Para calcular o tamanho de uma união de vários conjuntos, é necessário somar os tamanhos desses conjuntos separadamente e subtrair os tamanhos de todos os pares de interseções dos conjuntos e, em seguida, adicionar novamente o tamanho das interseções de triplos dos conjuntos, subtraia o tamanho dos quádruplos dos conjuntos e assim por diante, até a interseção de todos os conjuntos.

A formulação em termos de conjuntos

A definição acima pode ser expressa matematicamente da seguinte maneira:

$$\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 |$$

E de uma forma mais 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 |}$$

A formulação usando diagramas de Venn

O diagrama mostra três conjuntos $A$, $B$ e $C$:

Venn diagram

Então a área de sua união $A \cup B \cup C$ é igual à soma das áreas $A$, $B$ e $C$ menos as "duplas-áreas" cobertas $A \cap B$, $A \cap C$, $B \cap C$, mas com a adição da área coberta pelos três 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)$$

Também pode ser generalizado para uma associação de $n$ conjuntos.

A formulação em termos de probabilidade teórica

Se $A_i$ $(i = 1,2...n)$ são eventos, e ${\cal P}(A_i)$ a probabilidade de um evento de $A_i$ ocorrer, então a probabilidade de sua união (ou seja, a probabilidade de ocorrer pelo menos um dos eventos) é igual a:

$$\begin{eqnarray} {\cal P} \left( \bigcup_{i=1}^n A_i \right) &=& \sum_{i=1}^n{\cal P}(A_i)\ - \sum_{1\leq i<j\leq n} {\cal P}(A_i \cap A_j)\ + \\\ &+& \sum _{1\leq i<j<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}$$

E de uma forma mais comprimida:

$${\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 )}$$

Prova

Para a prova, é conveniente usar a formulação matemática em termos da teoria dos 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 provar que qualquer elemento contido em pelo menos um dos conjuntos $A_i$ ocorrerá na fórmula apenas uma vez (observe que: elementos que não estão presentes em nenhum dos conjuntos $A_i$ nunca serão considerados na parte direita de a fórmula).

Considere um elemento $x$ ocorrendo em $k \geq 1$ conjuntos $A_i$. Mostraremos que é contado apenas uma vez na fórmula. Note:

Isso nos leva à seguinte soma dos coeficientes binomiais:

$$ 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}$$

Essa expressão é muito semelhante à expansão 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 $$

Quando $x = 1$, $(1 - x)^k$ se parece muito com $T$. No entanto, a expressão possui um adicional $\binom{k}{0} = 1$, e é multiplicado por $-1$. Isso nos leva a $(1 - 1)^k = 1 - T$. Portanto, $T = 1 - (1 - 1)^k = 1$, o que era necessário para provar. O elemento é contado apenas uma vez.

Generalização para calcular o número de elementos em $r$ conjuntos

O princípio de inclusão-exclusão pode ser reescrito para calcular o número de elementos presentes em conjuntos de zeros:

$$\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|$$

Considere sua generalização para calcular o número de elementos que estão presentes exatamente em $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 provar essa fórmula, considere um particular $B$. Devido ao princípio básico de inclusão-exclusão, podemos dizer 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|$$

Não há interseções dos conjuntos ao lado esquerdo para diferentes $B$, portanto, podemos somar diretamente. Também se deve observar que qualquer conjunto $X$ sempre terá o coeficiente $(-1)^{m-r}$ se ocorrer e ocorrerá exatamente por $\dbinom{m}{r}$ conjuntos $B$.

Uso na resolução de problemas

O princípio de inclusão-exclusão é difícil de entender sem estudar suas aplicações.

Primeiro, examinaremos três tarefas mais simples "no papel", ilustrando aplicações do princípio, e depois consideraremos problemas mais práticos que são difíceis de resolver sem o princípio de inclusão-exclusão.

As tarefas que pedem "encontrar o número de maneiras" merecem destaque, pois às vezes elas levam a soluções polinomiais, não necessariamente exponenciais.

Uma tarefa simples sobre permutações

Tarefa: conte quantas permutações de números de $0$ a $9$ existem para que o primeiro elemento seja maior que $1$ e o último seja menor que $8$.

Vamos contar o número de permutações "ruins", ou seja, permutações nas quais o primeiro elemento é $\leq 1$ e / ou o último é $\geq 8$.

Denotaremos por $X$ o conjunto de permutações em que o primeiro elemento é $\leq 1$ e $Y$ o conjunto de permutações em que o último elemento é $\geq 8$. Então, o número de permutações "ruins", como na fórmula de inclusão-exclusão, será:

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

Após um cálculo combinatório simples, chegaremos a:

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

A única coisa que resta é subtrair esse número do total $10!$ para obter o número de permutações "boas".

Uma tarefa simples com sequências (0, 1, 2)

Tarefa: conte quantas seqüências de comprimento $n$ existem consistindo apenas com números $0,1,2$ de modo que cada número ocorra pelo menos uma vez.

Novamente, voltemos ao problema inverso, ou seja, calculamos o número de sequências que não contêm pelo menos um dos números.

Vamos denotar por $A_i (i = 0,1,2)$ o conjunto de sequências em que pelo menos $i$ dos números não ocorrem. A fórmula da inclusão-exclusão no número de sequências "ruins" 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| $$

Como resolvemos o problema de maneira inversa, subtraímos do total de $3^n$ seqüências:

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

O número de soluções inteiras para a equação

Considere a seguinte equação: $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20$$ onde $0 \le x_i \le 8 (i = 1,2,\ldots 6)$.

Tarefa: conte o número de soluções para a equação.

Esqueça a restrição em $x_i$ por um momento e conte o número de soluções não-negativas para esta equação. Isso é feito facilmente usando coeficientes binomiais: queremos dividir uma sequência de $20$ unidades em $6$ grupos, que é o mesmo que distribuir $5$ "paredes" sobre $25$ slots:

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

Vamos agora calcular o número de soluções "ruins" com o princípio de inclusão-exclusão. As soluções "ruins" serão aquelas em que um ou mais $x_i$ são maiores que $9$.

Denotaremos por $A_k (k = 1,2\ldots 6)$ o conjunto de soluções em que $x_k \ge 9$, e todos os outros $x_i \ge 0 (i \ne k)$ (eles podem ser $\ge 9$ ou não). Para calcular o tamanho de $A_k$, observe que temos essencialmente o mesmo problema combinatório que foi resolvido nos dois parágrafos acima, mas agora $9$ das unidades são excluídos dos slots e definitivamente pertencem ao primeiro grupo. Portanto:

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

Da mesma forma, o tamanho da interseção entre os conjuntos $A_k$ e $A_p$ será igual a:

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

O tamanho de cada interseção de três conjuntos é zero, já que $20$ unidades não serão suficientes para três ou mais variáveis ​​maiores ou iguais a $9$.

Combinando tudo isso na fórmula de inclusões e exceções e considerando que resolvemos o problema inverso, finalmente obtemos a resposta:

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

O número de coprimos em um determinado intervalo

arefa: dados dois números $n$ e $r$, conte o número de números inteiros no intervalo $[1;r]$ que são relativamente primos(coprimos) com n (ou seja, o maior divisor comum entre eles será $gcd/mdc(i,n)=1$).

Vamos resolver o problema inverso - calcule a quantidade de números que não são mutuamente primos com $n$.

Vamos denotar os fatores primos de $n$ como $p_i (i = 1\cdots k)$.

Quantos números no intervalo $[1;r]$ são divisíveis por $p_i$? A resposta a esta pergunta é:

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

No entanto, se simplesmente somarmos esses números, alguns números serão resumidos várias vezes (aqueles que compartilham vários $p_i$ como seus fatores). Portanto, é necessário usar o princípio de inclusão-exclusão.

Iremos iterar todos os $2^k$ subconjuntos de $p_i$s, calcular seu produto e adicionar ou subtrair o número de múltiplos de seu produto.

Aqui está uma implementação em 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;
}

O comportamento assintótico da solução é $O (\sqrt{n})$.

O número de inteiros em um determinado intervalo que são múltiplos de pelo menos um dos números fornecidos

Dados $n$ números $a_i$ e um número $r$. Você deseja contar a quantidade de números inteiros no intervalo $[1; r]$ que são múltiplos de pelo menos um dos $a_i$.

O algoritmo da solução é quase idêntico ao da tarefa anterior - construa a fórmula de exclusão-inclusão nos números $a_i$, ou seja, cada termo nessa fórmula é o número de números divisíveis por um determinado subconjunto de números $a_i$ (em outras palavras, divisíveis pelo seu mínimo múltiplo comum).

Portanto, agora iteraremos todos os $2^n$ subconjuntos de inteiros $a_i$ com $O(n \log r)$ operações para encontrar seu mínimo múltiplo comum, adicionando ou subtraindo o número de múltiplos dele no intervalo. O comportamento assintótico é $O (2^n\cdot n\cdot \log r)$.

O número de strings que satisfazem um determinado padrão

Considere $n$ padrões de strings do mesmo tamanho, consistindo apenas de letras ($a...z$) e pontos de interrogação. Você também recebe um número $k$. Uma string corresponde a um padrão se ela tiver o mesmo comprimento que o padrão e, em cada posição, os caracteres correspondentes forem iguais ou o caractere no padrão for um ponto de interrogação. A tarefa é contar o número de strings que correspondem exatamente a $k$ dos padrões (primeiro problema) e pelo menos $k$ dos padrões (segundo problema).

Observe primeiro que podemos contar facilmente o número de strings que satisfazem ao mesmo tempo todos os padrões especificados. Para fazer isso, basta "cruzar" os padrões: itere sobre as posições ("slots") e observe uma posição sobre todos os padrões. Se todos os padrões tiverem um ponto de interrogação nessa posição, o caractere poderá ser qualquer letra de $a$ até $z$. Caso contrário, o caractere dessa posição é definido exclusivamente pelos padrões que não contêm um ponto de interrogação.

Precisamos resolver a primeira versão do problema: quando a sequência deve satisfazer exatamente $k$ padrões.

Para resolver, iremos iterar e fixar um subconjunto específico $X$ do conjunto de padrões consistindo de $k$ padrões. Então temos que contar o número de strings que satisfazem esse conjunto de padrões, e que apenas correspondem a ele, ou seja, eles não correspondem a nenhum outro padrão. Usaremos o princípio de inclusão-exclusão de uma maneira ligeiramente diferente: somamos todos os superconjuntos $Y$ (subconjuntos do conjunto original de strings que contêm $X$), e então adicionar a resposta atual ou subtrair do número de strings:

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

onde $f(Y)$ é o número de strings que correspondem a $Y$ (pelo menos $Y$).

(Se você tiver dificuldade para descobrir isso, tente desenhar diagramas de Venn.)

Se somarmos todos os $ans(X)$, obteremos a resposta final:

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

No entanto, o comportamento assintótico da solução é $O(3^k \cdot k)$. Para aprimorá-lo, observe que diferentes cálculos de $ans(X)$ eralmente compartilham $Y$ conjuntos.

Inverteremos a fórmula de inclusão-exclusão e somaremos em termos de $Y$ conjuntos. Agora fica claro que o mesmo conjunto $Y$ seria levado em consideração no cálculo de $ans(X)$ de $\binom{|Y|}{k}$ conjuntos com o mesmo sinal $(-1)^{|Y| - k}$.

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

Agora a solução passa a ter comportamento assintótico $O(2^k \cdot k)$.

Agora vamos resolver a segunda versão do problema: encontre o número de strings que correspondem a pelo menos "$k$" dos padrões.

Podemos apenas usar a solução para a primeira versão do problema e adicionar as respostas para conjuntos com tamanho maior que $k$. No entanto, você pode perceber que, nesse problema, um conjunto |Y| é considerado na fórmula para todos os conjuntos com tamanho $\ge k$ contidos em $Y$. Dito isto, podemos escrever a parte da expressão que está sendo multiplicada 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|} $$

Olhando na obra de Graham (Graham, Knuth, Patashnik. "Concrete mathematics" [1998] ), vemos uma fórmula bem conhecida para os coeficientes binomiais:

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

Aplicando-o aqui, descobrimos que toda a soma dos coeficientes binomiais é minimizada:

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

Assim, para esta tarefa, também obtivemos uma solução em $O(2^k \cdot k)$:

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

O número de maneiras de ir de uma célula para outra

Há um grid $n \times m$, e $k$ de suas células são paredes intransitáveis. Um robô está inicialmente na célula $(1,1)$. O robô só pode se mover para a direita ou para cima e, eventualmente, precisa entrar na célula $(n,m)$, evitando todos os obstáculos. Você precisa contar o número de maneiras pelas quais ele pode fazer isso.

Assumindo que os tamanhos $n$ e $m$ são muito largos (digamos, $10^9$), e o número $k$ é pequeno (por volta de $100$).

Por enquanto, ordene os obstáculos pela coordenada $x$, em caso de igualdade - coordenada $y$.

Aprenda também como resolver um problema sem obstáculos: ou seja, aprenda como contar o número de maneiras de ir de uma célula para outra, isso pode ser feito com uma DFS. Em um eixo, precisamos passar por $x$ células, e no outro, $y$ células. Da combinatória obtemos uma fórmula usando coeficientes binomiais:

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

Agora, para contar o número de maneiras de se deslocar de uma célula para outra, evitando todos os obstáculos, você pode usar a exclusão de inclusão para resolver o problema inverso: conte o número de maneiras de percorrer o grid, percorrendo em um subconjunto de obstáculos (e subtrair do número total de maneiras).

WAo iterar sobre um subconjunto dos obstáculos que iremos enfrentar, para contar o número de maneiras de fazer isso, multiplique o número de todos os caminhos, desde a célula inicial até o primeiro dos obstáculos selecionados, de um primeiro obstáculo para o segundo e assim por diante, e então, adicione ou subtraia esse número da resposta, de acordo com a fórmula padrão de inclusão-exclusão.

No entanto, isso novamente terá complexidade não polinomial $O(2^k \cdot k)$.

Aqui está outra solução:

Usaremos a programação dinâmica: vamos calcular os números $d[i][j]$ — o número de maneiras de ir do $i-ésimo$ ponto para o $j-ésimo$, sem percorrer nenhum outro obstáculo (exceto por $i$ e $j$). Nós calcularemos esse número para todas as células-obstáculo e também para as células inicial e final (todos os pares possíveis de células).

Vamos esquecer por um segundo os obstáculos e apenas contar o número de caminhos da célula $i$ a $j$. Precisamos considerar alguns caminhos "ruins", os que atravessam os obstáculos, e subtraí-los do número total de maneiras de passar de $i$ para $j$.

Ao considerar um obstáculo $t$ entre $i$ e $j$ ($i < t < j$), no qual podemos pisar, vemos que o número de caminhos de $i$ para $j$ que passa por $t$ no qual tem $t$ como o primeiro obstáculo entre $i$ e $j$. Podemos calcular isso como: $d[i][t]$ multiplicado pelo número de caminhos arbitrários de $t$ para $j$. Podemos contar o número de maneiras "ruins" que somam isso para todos os $t$ entre $i$ e $j$.

Podemos calcular $d[i][j]$ em $O(k)$ para $O(k^2)$ pares, então, essa solução tem complexidade $O(k^3)$.

O número de coprimos quadruplos

Dado $n$ números: $a_1, a_2, \ldots, a_n$. Você deve contar o número de maneiras de escolher quatro números para que seu maior divisor comum combinado seja igual a um($gcd(x,y,z,t)=1$).

Vamos resolver o problema inverso - calcule o número de quádruplos "ruins", ou seja, quádruplos nos quais todos os números são divisíveis por um número $d > 1$.

Usaremos o princípio de inclusão-exclusão ao somar todos os grupos possíveis de quatro números divisíveis por um divisor $d$.

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

onde $deg(d)$ é o número de primos na fatoração do número $d$ e $f(d)$ o número de quádruplos divisíveis por $d$.

Para calcular a função $f(d)$, basta contar o número de múltiplos de $d$ e usar os coeficientes binomiais para contar o número de maneiras de escolher quatro deles.

Assim, usando a fórmula de inclusões-exclusões, somamos o número de grupos quadruplos divisíveis por um número primo e subtraímos o número de quádruplos que são divisíveis pelo produto de dois números primos, adicionamos quádruplos divisíveis por três números primos, etc.

O número de triplos harmônicos

Você recebe um número $n \le 10^6$. Você deve contar o número de triplos $2 \le a < b < c \le n$ que atendem a uma das seguintes condições:

nota: gcd = mdc

Primeiro, vá direto ao problema inverso - ou seja, conte o número de triplos não harmônicos.

Segundo, observe que qualquer trigêmeo não harmônico é composto de um par de coprimos($mdc(x,y) = 1$) e um terceiro número que não é coprimo com pelo menos um do par.

Assim, o número de triplos não harmônicos que contêm $i$ é igual ao número de inteiros de $2$ a $n$ que são coprimos com $i$ multiplicado pelo número de inteiros que não são coprimos com $i$.

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

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

Nos dois casos, será contado duas vezes. O primeiro caso será contado quando $i = a$ e quando $i = b$. O segundo caso será contado quando $i = b$ e quando $i = c$. Portanto, para calcular o número de triplos não harmônicos, somamos esse cálculo a todos os $i$ de $2$ a $n$ e dividimos por $2$.

Agora, tudo o que temos a resolver é aprender a contar o número de coprimos até i no intervalo $[2;n]$. Embora esse problema já tenha sido mencionado, a solução acima não é adequada aqui - exigiria a fatoração de cada um dos inteiros de $2$ a $n$ e, em seguida, a iteração por todos os subconjuntos desses números primos.

Uma solução mais rápida é possível com essa modificação do crivo de Eratóstenes:

  1. Primeiro, encontramos todos os números no intervalo $[2;n]$ de modo que sua simples fatoração não inclua um fator primo duas vezes. Também precisamos saber, para esses números, quantos fatores isso inclui.

    • Para fazer isso, manteremos uma array $deg[i]$ para armazenar o número de primos na fatoração de $i$, e uma array $good[i]$, para marcar se $i$ contém cada fator no máximo duas vezes ($good[i] = 1$) ou não ($good[i] = 0$). Ao iterar de $2$ até $n$, se atingirmos um número que tem $deg$ igual a $0$, então, será um primo e seu $deg$ será $1$.
    • Durante o crivo de Eratóstenes, iteraremos $i$ de $2$ até $n$. Ao processar um número primo, passamos por todos os seus múltiplos e aumentamos seus $deg[]$. Se um desses múltiplos é múltiplo do quadrado de $i$, então podemos definir $good$ como falso.
  2. Segundo, precisamos calcular a resposta para todos os $i$ de $2$ até $n$, ou seja, a array $cnt[]$ — o número de inteiros que não são coprimos com $i$.

    • Para fazer isso, lembre-se de como a fórmula da inclusão-exclusão funciona - na verdade, implementamos o mesmo conceito, mas com lógica invertida: iteramos sobre um componente (um produto dos primos da fatoração) e adicionamos ou subtraímos seu termo à fórmula inclusão-exclusão de cada um de seus múltiplos.
    • Então, digamos que estamos processando um número $i$, no qual $good[i] = true$, ou seja: que esteja envolvido na fórmula da inclusão-exclusão. Itere por todos os números que são múltiplos de $i$, e adicione ou subtraia $\lfloor N/i \rfloor$ do $cnt[]$ deles (o sinal depende de $deg[i]$: se $deg[i]$ for ímpar, deveremos adicionar, caso contrário subtraímos).

Implementação:

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;
}

O comportamento assintótico da solução é $O(n \log n)$, pois para quase todos os números até $n$ fazemos $n/i$ iterações no loop.

O número de permutações sem pontos fixos - desarranjos

Prove que o número de permutações de comprimento $n$ sem pontos fixos (ou seja, nenhum número $i$ está na posição $i$ - desarranjo) é igual ao seguinte 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)! $$

e aproximadamente igual a:

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

(se você arredondar essa expressão para o número inteiro mais próximo - você obtém exatamente o número de permutações sem pontos fixos)

Denote por $A_k$ o conjunto de permutações de tamanho $n$ com um ponto fixo na posição $k$ ($1 \le k \le n$) (ou seja, o elemento $k$ está na posição $k$).

Agora usamos a fórmula da inclusão-exclusão para contar o número de permutações com pelo menos um ponto fixo. Para isso, precisamos aprender a contar os tamanhos de uma interseção dos conjuntos $A_i$, da seguinte maneira:

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

porque se soubermos que o número de pontos fixos é igual a $x$, saberemos a posição de $x$ elementos da permutação e todos os outros $(n-x)$ elementos podem ser colocados em qualquer outro lugar.

Substituindo isso na fórmula de inclusão-exclusão, e considerando que o número de maneiras de escolher um subconjunto de tamanho $x$ do conjunto de $n$ elementos é igual a $\binom{n}{x}$, obtemos uma fórmula para o número de permutações com pelo menos um ponto fixo:

$$\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)! $$

Então o número de permutações sem pontos fixos é 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 expressão, obtemos expressões exatas e aproximadas para o número de permutações sem pontos fixos:

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

(a soma entre parênteses são os primeiros $n+1$ termos da expansão na série de Taylor $e^{-1}$)

Vale a pena notar que um problema semelhante pode ser resolvido desta maneira: quando você precisa dos pontos fixos e eles não estão dentre os $m$ primeiros elementos das permutações (e também não entre todos, como acabamos de resolver). A fórmula obtida irá até a soma de $k$, em vez de $n$.

Problemas