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 em um conjunto finito 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 . 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.

ExemplosEditar

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

SubfatoriaisEditar

 
O enésimo elemento troca de posição com o primeiro elemento.

Defina   o número de possíveis desarranjos para um conjunto de   elementos. Podemos encontrar uma relação de recorrência para   usando o método de inclusão-exclusão. É fácil calcular os primeiros valores de  :

  •  
  •  
  •  
  •  

Considere agora os possíveis desarranjos do conjunto   e divida-os em duas classes:

  1. Os desarranjos em que o elemento n assume a posição de um elemento   e o elemento k assume a posição de n. Exemplo: 12344321.
  2. Os desarranjos em que o elemento n assume a posição de um elemento   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   elementos para cada possível posição que o enésimo elemento pode assumir, ou seja:  .
  • O número de desarranjos na classe 2 deve ser igual ao número de desarranjos de um conjunto com   elementos para cada possível posição que o enésimo elemento pode assumir, ou seja:  . 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  .

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

  •  

Relação com o fatorialEditar

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

  •  

Assim, é natural definir:

  •  

A seqüência  , assim definida satisfaz:

  •  

Introduzimos, então, mais uma seqüência,  , que satisfaz:

  •  

Como  , é fácil ver que:

  •  

E, portanto,

  •  

Assim, obtemos, uma expressão para  

  •  

Relação com o número de EulerEditar

Se observarmos que   podemos escrever:

  •  

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

  •  

E assim, temos:

  •  

E portanto é fácil concluir que

  •  

onde   representa o inteiro mais próximo de  .