Questão 80 (FCC 2019/Prefeitura do Recife - Assistente de Gestão Pública). Os 10 funcionários de uma repartição trabalham cada um em uma mesa, todos na mesma sala. O chefe da repartição determinou que os funcionários trocassem de mesa entre si. De quantos modos os funcionários podem ser realocados na sala de modo que nenhum funcionário passe a ocupar a mesa que ocupava antes da realocação?

Passo 1

O enunciado dá e pede o seguinte (resumindo e listando exatamente o que importa):
  • 10 funcionários e 10 mesas; cada funcionário ocupa uma mesa antes da troca.
  • O chefe manda realocar os funcionários entre as mesas de modo que nenhum funcionário passe a ocupar a mesa que ocupava antes.
  • A pergunta: de quantos modos isso pode ser feito? Ou seja, contar o número de realocações (permutations) sem pontos fixos.

Passo 2

Qual método vou usar (sem mistério): precisamos contar permutações de 10 elementos sem pontos fixos — essas permutações chamam-se “desarranjos” ou “derangements”. Há várias formas de obter o número: princípio da inclusão-exclusão (direto e seguro), ou uma fórmula fechada/recorrência derivada disso. Vou usar inclusão-exclusão porque é um método elementar, direto e que dá a conta exata sem apelar a memorização. Vou explicar tudo passo a passo para você entender bem.

Passo 3

Primeiro, construção do modelo e do argumento (passo didático).
  • Denote por n o número de funcionários; aqui n=10.
  • Pense em uma permutação de n elementos que manda cada funcionário para alguma mesa. O total de permutações é n!.
  • Para aplicar inclusão-exclusão, defina, para cada funcionário i, o conjunto A_i das permutações que deixam o funcionário i na mesma mesa (isto é, que fixam i).
  • Queremos contar permutações que não pertencem a nenhum A_i; em símbolos, \left|\bigcap_{i=1}^n A_i^c\right|, o número de permutações que fixam ninguém.
Princípio da inclusão-exclusão (em palavras fáceis): para contar os objetos que não têm nenhuma das propriedades A_1,\dots,A_n, partimos do total n! e subtraímos os que têm pelo menos uma propriedade, mas então ajustamos somando e subtraindo interseções para não contar errado. Em fórmula (a forma que vamos usar):
\text{número de desarranjos} = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \binom{n}{3}(n-3)! + \cdots + (-1)^n \binom{n}{n}(n-n)!.ú
Explicação de cada termo:
  • \binom{n}{k} escolhe quais k funcionários ficam na própria mesa.
  • Se k funcionários estão fixos, os outros n-k podem ser permutados livremente em (n-k)! maneiras.
  • O sinal alternado vem do princípio da inclusão-exclusão.
Essa soma pode ser colocada em forma compacta:
!n = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!},
onde !n denota o número de desarranjos de n objetos. Aqui \frac{n!}{k!} = \binom{n}{k}(n-k)! foi usado para reescrever os termos.

Passo 4

Agora aplicamos a fórmula para n=10. Vou calcular termo a termo usando a fórmula com combinações (inteiros), porque isso evita aproximações e fica tranquilo de fazer na prova:
!10 = 10! - \binom{10}{1}9! + \binom{10}{2}8! - \binom{10}{3}7! + \binom{10}{4}6! - \binom{10}{5}5! + \binom{10}{6}4! - \binom{10}{7}3! + \binom{10}{8}2! - \binom{10}{9}1! + \binom{10}{10}0!.
Vou calcular cada pedaço (mostrando as contas para você acompanhar sem pular etapas):

Passo 5

Cálculo dos termos (cada linha é um termo da soma acima):
10! = 3628800.
\binom{10}{1}9! = 10\times 362880 = 3628800.
\binom{10}{2}8! = 45\times 40320 = 1814400.
\binom{10}{3}7! = 120\times 5040 = 604800.
\binom{10}{4}6! = 210\times 720 = 151200.
\binom{10}{5}5! = 252\times 120 = 30240.
\binom{10}{6}4! = 210\times 24 = 5040.
\binom{10}{7}3! = 120\times 6 = 720.
\binom{10}{8}2! = 45\times 2 = 90.
\binom{10}{9}1! = 10\times 1 = 10.
\binom{10}{10}0! = 1\times 1 = 1.

Passo 6

Agora vamos somar/subtrair alternadamente conforme a fórmula (faço aos poucos para ficar claro):
  • Primeiro 10! - \binom{10}{1}9! = 3628800 - 3628800 = 0.
  • Soma com o próximo termo: 0 + 1814400 = 1814400.
  • Subtrai o próximo: 1814400 - 604800 = 1209600.
  • Soma o próximo: 1209600 + 151200 = 1360800.
  • Subtrai o próximo: 1360800 - 30240 = 1330560.
  • Soma o próximo: 1330560 + 5040 = 1335600.
  • Subtrai o próximo: 1335600 - 720 = 1334880.
  • Soma o próximo: 1334880 + 90 = 1334970.
  • Subtrai o próximo: 1334970 - 10 = 1334960.
  • Soma o último: 1334960 + 1 = 1334961.
Portanto o total final é 1334961.

Passo 7

Interpretação rápida e dica para a prova:
  • O número 1334961 é o número de maneiras de realocar os 10 funcionários sem que nenhum volte à sua mesa original.
  • Uma observação útil para lembrar: para grandes n, !n fica próximo de \dfrac{n!}{e}. Para n=10, \dfrac{10!}{e} arredonda para 1334961, então essa aproximação dá uma checagem rápida na prova.
  • Se preferir uma relação de recorrência (útil para calcular sem fazer inclusão-exclusão completa): !n = (n-1)(!(n-1) + !(n-2)). Assim, conhecendo !1 e !2 dá pra subir até !10.

Resposta

1334961

Exercícios relacionados