Quantas permutações de
possuem pelo menos um ponto fixo?
Passo 1
O que o enunciado pede:
- Contar quantas permutações do conjunto
têm pelo menos um ponto fixo.
Informações dadas (explícitas ou implícitas):
- Trabalhamos com todas as permutações de cinco elementos.
- Um “ponto fixo” numa permutação é um elemento
tal que a permutação envia em si mesma.
Passo 2
Estratégia escolhida (ideia principal):
- É mais fácil contar o complementar: primeiro conto quantas permutações NÃO têm nenhum ponto fixo (essas são chamadas de derangements) e depois subtraio do total.
- Em palavras: número pedido = (total de permutações) − (número de permutações sem ponto fixo).
Explicação do total de permutações:
- O número total de permutações de
elementos é . - Lembrete sobre fatorial: para
natural, . - Portanto
Passo 3
Como contar permutações sem ponto fixo (introdução da técnica):
- Vamos usar o princípio da inclusão-exclusão para contar quantas permutações não fixam nenhum elemento.
- Ideia do princípio (em palavras simples): somar as contagens que fixam cada elemento, subtrair as que fixam pares (porque foram contadas duas vezes), somar as que fixam triplas, e assim por diante, alternando sinais.
Formulação para este problema:
- Se fixarmos exatamente um subconjunto de
elementos, o número de permutações que fixam esses elementos é (porque os demais elementos podem permutar livremente). - Há
maneiras de escolher quais elementos ficam fixos. - Pela inclusão-exclusão, o número de permutações sem ponto fixo vale
Passo 4
Cálculo termo a termo da soma (cada passo explicado):
- Para
: (termo positivo) - Para
: - Para
: - Para
: - Para
: - Para
:
Soma dos termos:
- Interpretação: existem
permutações de que não têm nenhum ponto fixo.
Passo 5
Alternativa (fórmula rápida de derangement) e verificação mental:
- Existe uma fórmula compacta para derangements: para
,
- Para
isso dá , confirmando o resultado do passo anterior.
Passo 6
Agora obtenho o número de permutações que têm pelo menos um ponto fixo:
- Usando a estratégia do Passo 2: número desejado
.