15. (IME/83) Uma rua possui um estacionamento em fila com N vagas demarcadas junto ao meio-fio de um dos lados. N automóveis, numerados de 1 a N, d...

Para resolver esse problema, podemos utilizar o Princípio da Inclusão e Exclusão (PIE). Seja A_i o conjunto de configurações em que o carro i não está na posição correta. Queremos calcular o número de configurações em que pelo menos um carro não está na posição correta. Pelo PIE, temos que: |A_1 ∪ A_2 ∪ ... ∪ A_N| = Σ|A_i| - Σ|A_i ∩ A_j| + Σ|A_i ∩ A_j ∩ A_k| - ... + (-1)^(N+1)|A_1 ∩ A_2 ∩ ... ∩ A_N| O número total de configurações é N!, então o número de configurações em que todos os carros estão na posição correta é: N! - |A_1 ∪ A_2 ∪ ... ∪ A_N| Para calcular |A_i|, fixamos o carro i na posição errada e permutamos os outros N-1 carros. Temos (N-1)! configurações, mas precisamos multiplicar por 2, pois o carro i pode estar à esquerda ou à direita do carro que deveria estar na sua posição. Então: |A_i| = 2(N-1)! Para calcular |A_i ∩ A_j|, fixamos os carros i e j nas posições erradas e permutamos os outros N-2 carros. Temos (N-2)! configurações, mas precisamos multiplicar por 4, pois os carros i e j podem estar em qualquer ordem. Então: |A_i ∩ A_j| = 4(N-2)! Continuando dessa forma, podemos calcular todos os termos da expressão do PIE e obter o número de configurações em que pelo menos um carro não está na posição correta. Subtraindo esse número de N!, obtemos o número de configurações em que todos os carros estão na posição correta.