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 $\varphi :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

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 desarranjos do conjunto $\{1,2,3,\dots ,n\}$ e divida-os em duas classes:

1. 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.
2. 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,\dots ,k-1,k+1,k+2,\dots ,n-1,k\}$.

A seqüência dos subfatoriais é, portanto, unicamente determinada pela sua relação de recorrência e pelos dois valores iniciais:

• $\{\begin{array}{c}{d}_1=0\\ d_2=1\\ d_n=(n-1)(d_{n-1}+d_{n-2})\end{array}$

Relação com o fatorial

É importante observar que o fatorial, $n!$ satisfaz a mesma relação, já que:

• $(n-1)[(n-1)!+(n-2)!]=(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}(f_{n-1}-f_{n-2})$

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\ge 2$

E, portanto,

• $\begin{array}{ccc}{f}_n& =& f_1+(f_2-f_1)+(f_3-f_2)+\dots (f_n-f_{n-1})\\ & =& 0+g_2+g_3+\dots +g_n\\ & =& \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}^{\mathrm{\infty }}(-1{)}^k\frac{1}{k!}=e^{-1}$ podemos escrever:

• $!n=d_n=\frac{n!}{e}-\sum _{k=n+1}^{\mathrm{\infty }}(-1{)}^k\frac{n!}{k!}$

O termo mais direita pode ser estimado pelo teste da série alternada:

• $|\sum _{k=n+1}^{\mathrm{\infty }}(-1{)}^k\frac{n!}{k!}|\le \frac{1}{n+1}$

E assim, temos:

• $|!n-\frac{n!}{e}|\le \frac{1}{n+1}<1/2,n\ge 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$.