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 Dn, que são as permutações caóticas ou derangements de um conjunto com n 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 n 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 n-1 posições possíveis para ir.
Passo 3
Suponha que o 1 vá para a posição k (onde ). Agora temos duas possibilidades:
O elemento que estava na posição k vai para a posição 1.
O elemento que estava na posição k não vai para a posição 1.
Passo 4
Caso 1: Se o elemento na posição k 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 knão vai para a posição 1, então ele deve ir para outra posição diferente de k. Nesse caso, os n-1 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 n-1 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: