Seja o número de permutações caóticas de . Sem usar a fórmula para , deduza a equação de recorrência
Passo 1
Beleza, vamos lá! O enunciado pede para deduzirmos uma equação de recorrência para , que são as permutações caóticas ou derangements de um conjunto com elementos. Isso está no campo da Combinatória, mais especificamente em Permutações sem Fixos. Para resolver isso, vamos precisar entender como contar as permutações onde nenhum elemento fica na posição original.
Passo 2
Primeiro, vamos pensar em como formar uma permutação caótica de elementos. Vamos escolher um elemento específico, digamos o número 1, e ver para onde ele pode ir. Como estamos falando de permutações sem fixos, o 1 não pode ficar na primeira posição. Então, ele tem posições possíveis para ir.
Passo 3
Suponha que o 1 vá para a posição (onde ). Agora temos duas possibilidades:
O elemento que estava na posição vai para a posição 1.
O elemento que estava na posição não vai para a posição 1.
Passo 4
Caso 1: Se o elemento na posição vai para a posição 1, então estamos basicamente trocando esses dois elementos. Agora, o restante dos elementos precisa ser uma permuta��ão caótica de si mesmos. Ou seja, há maneiras de fazer isso.
Caso 2: Se o elemento na posição não vai para a posição 1, então ele deve ir para outra posição diferente de . Nesse caso, os elementos restantes (excluindo o 1 que já foi colocado) precisam formar uma permutação caótica. Portanto, há maneiras de fazer isso.
Passo 5
Como o elemento 1 tem opções para escolher onde vai, e para cada uma dessas escolhas temos possibilidades (dos casos 1 e 2), a equação de recorrência fica: