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=\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\,$.