Desarranjo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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: 12344321.
  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: 12344312
  • 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[editar | editar código-fonte]

É 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[editar | editar código-fonte]

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