Desarranjo

Em análise combinatória, um desaranjo, também conhecido como permutação caótica ou derangement (do francês) é uma espécie de permutação em que nenhum elemento do conjunto permanece na mesma posição. Formalmente falando, um desaranjo é uma bijeção $\phi :S\to S\,$ em um conjunto finito $S\,$ que não possui pontos fixos. O número de diferentes desaranjos em um conjunto de n elementos é definido como o subfatorial de n e é denotado $!n\,$. O problema de contar desaranjos foi primeiramente considerado por Pierre Raymond de Montmort em 1708 e resolvido em 1713. Nicholas Bernoulli obteve o mesmo resultado na mesma época.

Exemplos

Os dois possíveis desaranjos das três letras da palavra "lua":

• ual
• alu

Os nove possíveis desaranjos das quatro letras da palavra "cano":

• acon, anoc, aocn
• ncoa, noca, noac
• ocan, onca, onac

Subfatoriais

O enésimo elemento troca de posição com o primeiro elemento.

Defina $d_{n}:=!n\,$ o número de possíveis desarranjos para um conjunto de $n\,$ elementos. Podemos encontrar uma relação de recorrência para $d_{n}\,$ usando o método de inclusão-exclusão. É fácil calcular os primeiros valored de $d_{n}\,$:

• $d_{1}=0\,$
• $d_{2}=1\,$
• $d_{3}=2\,$
• $d_{4}=9\,$

Considere agora que os possíveis desaranjos do conjunto $\{1,2,3,\ldots ,n\}$ e divido-os em duas classe:

1. Os desaranjos em que o elemento n assume a posição de um elemento $k\,$ e o elemento k assume a posição de n. Exemplo: 1234 -> 4321.
2. Os desaranjos em que o elemento n assume a posição de um elemento $k\,$ e o elemento k não assume a posição de n. Exemplo: 1234 -> 4312

• O número de desarranjos na classe 1 deve ser igual ao número de desarranjos de um conjunto com $n-2\,$ elementos para cada possível posição que o enésimo elemento pode assumir, ou seja: $(n-1)d_{n-2}\,$.

• O número de desarranjos na classe 2 deve ser igual ao número de desarranjos de um conjunto com $n-1\,$ elementos para cada possível posição que o enésimo elemento pode assumir, ou seja: $(n-1)d_{n-1}\,$. Para chegar a esta conclusão, observar que se o enésimo elemento assume a posição k, podemos permutar k com n e realizar os desaranjos no conjunto $\{1,2,\ldots ,k-1,k+1,k+2,\ldots ,n-1,k\}$.

A relação de recorrência para $d_{n}\,$ é portanto dada por:

• $\left\{{\begin{array}{l}d_{1}=0\\d_{2}=1\\d_{n}=(n-1)\left(d_{n-1}+d_{n-2}\right)\end{array}}\right.$