Seja Dn o número de permutações caóticas de {1, ..., n}. Sem usar a fórmula para Dn, deduza a equação de recorrência
{ Dn = (n - 1) * (Dn-2 + Dn-1), para todo n ≥ 3; D1 = 0; D2 = 1 }

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:
  1. O elemento que estava na posição k vai para a posição 1.
  2. 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 k nã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:

Resposta

A equação de recorrência deduzida é:

Exercícios relacionados