# Desarranjo

Em análise combinatória, um desarranjo, 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 desarranjo é uma bijeção $\phi :S\to S\,$ em um conjunto finito $S\,$ que não possui pontos fixos. O número de diferentes desarranjos em um conjunto de n elementos é definido como o subfatorial de n e é denotado $!n\,$. O problema de contar desarranjos 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 desarranjos das três letras da palavra "lua":
* ual
* alu
Os nove possíveis desarranjos das quatro letras da palavra "cano":
* acon, anoc, aocn
* ncoa, noca, noac
* ocan, onca, onac

## Subfatoriais

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 valores de $d_{n}\,$:
* $d_{1}=0\,$
* $d_{2}=1\,$
* $d_{3}=2\,$
* $d_{4}=9\,$
Considere agora os possíveis desarranjos do conjunto $\{1,2,3,\ldots ,n\}$ e divida-os em duas classes:
* Os desarranjos 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.
* Os desarranjos 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 desarranjos no conjunto $\{1,2,\ldots ,k-1,k+1,k+2,\ldots ,n-1,k\}$.
A seqüência dos subfatoriais é, portanto, unicamente determinada pela sua relação de recorrência e pelos dois valores iniciais:
* $\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.$

## Relação com o fatorial

É importante observar que o fatorial, $n!\,$ satisfaz a mesma relação, já que:
* $(n-1)\left[(n-1)!+(n-2)!\right]=(n-1)(n-1)!+(n-1)!=n(n-1)!=n!$
Assim, é natural definir:
* $f_{n}={\frac {d_{n}}{n!}}$
A seqüência $f_{n}\,$, assim definida satisfaz:
* $f_{n}-f_{n-1}=-{\frac {1}{n}}\left(f_{n-1}-f_{n-2}\right)$
Introduzimos, então, mais uma seqüência, $g_{n}=f_{n}-f_{n-1}$, que satisfaz:
* $g_{n}=-{\frac {1}{n}}g_{n-1}$
Como $g_{2}=f_{2}-f_{1}={\frac {1}{2}}d_{2}-d_{1}={\frac {1}{2}}$, é fácil ver que:
* $g_{k}={\frac {(-1)^{k}}{k!}},~~n\geq 2$
E, portanto,
* ${\begin{array}{rcl}f_{n}&=&f_{1}+(f_{2}-f_{1})+(f_{3}-f_{2})+\ldots (f_{n}-f_{n-1})\\&=&0+g_{2}+g_{3}+\ldots +g_{n}\\&=&\displaystyle \sum _{k=2}^{n}g_{k}=\sum _{k=2}^{n}{\frac {(-1)^{k}}{k!}}=\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\end{array}}$
Assim, obtemos, uma expressão para $!n\,$
* $!n=d_{n}=n!f_{n}=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}$

## Relação com o número de Euler

Se observarmos que $\sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}=e^{-1}$ podemos escrever:
* $!n=d_{n}={\frac {n!}{e}}-\sum _{k=n+1}^{\infty }(-1)^{k}{\frac {n!}{k!}}$
O termo mais direita pode ser estimado pelo teste da série alternada:
* $\left|\sum _{k=n+1}^{\infty }(-1)^{k}{\frac {n!}{k!}}\right|\leq {\frac {1}{n+1}}$
E assim, temos:
* $\left|!n-{\frac {n!}{e}}\right|\leq {\frac {1}{n+1}}<1/2,~~n\geq 2$
E portanto é fácil concluir que
* $!n=\left[{\frac {n!}{e}}\right]$
onde $\left[x\right]$ representa o inteiro mais próximo de $x\,$.