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 valores de $d_{n}\,$:

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

Considere agora 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 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}=d_{1}-{\frac {1}{2}}d_{2}=-{\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\,$.