Questão 63. De quantos modos podemos permutar as letras da palavra SORTE de modo que nenhuma delas fique na posição inicial?

Passo 1

O enunciado dá a palavra SORTE, que tem 5 letras distintas. As letras ocupam inicialmente posições 1 a 5 na ordem S,O,R,T,E.
A pergunta é: de quantos modos podemos permutar as letras dessa palavra de modo que nenhuma letra fique em sua posição inicial? Em outras palavras: contar as permutações das 5 letras sem pontos fixos (nenhuma letra permanece na mesma posição que tinha originalmente).
Informações relevantes:
  • Número de letras: n=5.
  • Todas as letras são distintas.
  • Queremos permutações sem nenhum ponto fixo (derangements).

Passo 2

Vamos entender o que significa “derangement” (desarranjo). Uma permutação de n objetos tem um ponto fixo quando um objeto fica na mesma posição que no arranjo inicial. Um derangement é uma permutação sem pontos fixos.
Fórmula e ideia que vamos usar (princípio da inclusão-exclusão):
  • O número total de permutações de n objetos é n!.
  • Para contar permutações sem pontos fixos, podemos usar inclusão-exclusão: conte todas as permutações e subtraia as que têm pelo menos 1 ponto fixo, corrija as sobrecontagens adicionando as que têm pelo menos 2 pontos fixos, e assim por diante.
  • O número de permutações que fixam exatamente k posições é: escolher quais k posições ficam fixas, \binom{n}{k}, e permutar livremente as n-k restantes, (n-k)!. Então, por inclusão-exclusão,
!n=\sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)!.
Podemos reorganizar essa soma para a forma mais conhecida
!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.
Aqui n! é o fatorial de n ( n!=n\cdot(n-1)\cdots1) e k! é o fatorial de k.

Passo 3

Aplicando a fórmula para n=5. Primeiro cálculo por inclusão-exclusão termo a termo, usando \binom{5}{k}(5-k)!:
  • k=0: \binom{5}{0}(5-0)! = 1\cdot 5! = 120.
  • k=1: \binom{5}{1}(5-1)! = 5\cdot 4! = 5\cdot 24 = 120.
  • k=2: \binom{5}{2}(5-2)! = 10\cdot 3! = 10\cdot 6 = 60.
  • k=3: \binom{5}{3}(5-3)! = 10\cdot 2! = 10\cdot 2 = 20.
  • k=4: \binom{5}{4}(5-4)! = 5\cdot 1! = 5\cdot 1 = 5.
  • k=5: \binom{5}{5}(5-5)! = 1\cdot 0! = 1\cdot 1 = 1.
Agora aplicamos os sinais alternados da inclusão-exclusão:
!5 = 120 - 120 + 60 - 20 + 5 - 1.
Fazendo as somas:
120 - 120 = 0,
0 + 60 = 60,
60 - 20 = 40,
40 + 5 = 45,
45 - 1 = 44.
Portanto !5 = 44.

Passo 4

Para reforçar a intuição: existe também a fórmula recorrente
!n = (n-1)\bigl(!(n-1) + !(n-2)\bigr),
com !1=0 e !2=1. Usando essa recorrência:
  • !3=(3-1)(!2+!1)=2(1+0)=2.
  • !4=(4-1)(!3+!2)=3(2+1)=9.
  • !5=(5-1)(!4+!3)=4(9+2)=4\cdot11=44.
    Essa verificação alternativa confirma o resultado obtido por inclusão-exclusão.

Passo 5

Um exemplo pequeno para fixar a ideia: para n=3 com letras A,B,C, as permutações sem nenhuma na posição original são B,C,A e C,A,B, ou seja, !3=2. Esse tipo de contagem é exatamente o que fizemos para n=5, mas com cálculo maior.
Força aí — derangements podem parecer chatos, mas com inclusão-exclusão ou a recorrência eles caem bem.

Resposta

44

Exercícios relacionados