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 ${\displaystyle \phi :S\to S\,}$ em um conjunto finito ${\displaystyle 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 ${\displaystyle !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 ${\displaystyle d_{n}:=!n\,}$ o número de possíveis desarranjos para um conjunto de ${\displaystyle n\,}$ elementos. Podemos encontrar uma relação de recorrência para ${\displaystyle d_{n}\,}$ usando o método de inclusão-exclusão. É fácil calcular os primeiros valores de ${\displaystyle d_{n}\,}$:

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

Considere agora os possíveis desarranjos do conjunto ${\displaystyle \{1,2,3,\ldots ,n\}}$ e divida-os em duas classes:

1. Os desarranjos em que o elemento n assume a posição de um elemento ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n-2\,}$ elementos para cada possível posição que o enésimo elemento pode assumir, ou seja: ${\displaystyle (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 ${\displaystyle n-1\,}$ elementos para cada possível posição que o enésimo elemento pode assumir, ou seja: ${\displaystyle (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 ${\displaystyle \{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:

• ${\displaystyle \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, ${\displaystyle n!\,}$ satisfaz a mesma relação, já que:

• ${\displaystyle (n-1)\left[(n-1)!+(n-2)!\right]=(n-1)(n-1)!+(n-1)!=n(n-1)!=n!}$

Assim, é natural definir:

• ${\displaystyle f_{n}={\frac {d_{n}}{n!}}}$

A seqüência ${\displaystyle f_{n}\,}$, assim definida satisfaz:

• ${\displaystyle f_{n}-f_{n-1}=-{\frac {1}{n}}\left(f_{n-1}-f_{n-2}\right)}$

Introduzimos, então, mais uma seqüência, ${\displaystyle g_{n}=f_{n}-f_{n-1}}$, que satisfaz:

• ${\displaystyle g_{n}=-{\frac {1}{n}}g_{n-1}}$

Como ${\displaystyle g_{2}=f_{2}-f_{1}={\frac {1}{2}}d_{2}-d_{1}={\frac {1}{2}}}$, é fácil ver que:

• ${\displaystyle g_{k}={\frac {(-1)^{k}}{k!}},~~n\geq 2}$

E, portanto,

• ${\displaystyle {\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 ${\displaystyle !n\,}$

• ${\displaystyle !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 ${\displaystyle \sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}=e^{-1}}$ podemos escrever:

• ${\displaystyle !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:

• ${\displaystyle \left|\sum _{k=n+1}^{\infty }(-1)^{k}{\frac {n!}{k!}}\right|\leq {\frac {1}{n+1}}}$

E assim, temos:

• ${\displaystyle \left|!n-{\frac {n!}{e}}\right|\leq {\frac {1}{n+1}}<1/2,~~n\geq 2}$

E portanto é fácil concluir que

• ${\displaystyle !n=\left[{\frac {n!}{e}}\right]}$

onde ${\displaystyle \left[x\right]}$ representa o inteiro mais próximo de ${\displaystyle x\,}$.