Desarranjo
Em análise combinatória, um desarranjo, também conhecido como permutação caótica ou derangement é 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.
Imagem: Acidum Project · BY-NC-SA · Openverse
Os dois possíveis desarranjos das três letras da palavra "lua": Os nove possíveis desarranjos das quatro letras da palavra "cano":
Defina d n := ! n {\displaystyle d_{n}:=!n\,} o número de possíveis desarranjos para um conjunto de n {\displaystyle n\,} elementos. Podemos encontrar uma relação de recorrência para d n {\displaystyle d_{n}\,} usando o método de inclusão-exclusão. É fácil calcular os primeiros valores de d n {\displaystyle d_{n}\,} : Considere agora os possíveis desarranjos do conjunto { 1 , 2 , 3 , … , n } {\displaystyle \{1,2,3,\ldots ,n\}} e divida-os em duas classes: A seqüência dos subfatoriais é, portanto, unicamente determinada pela sua relação de recorrência e pelos dois valores iniciais:
Imagem: Min. Agricultura Brasil · BY-NC · Openverse
É importante observar que o fatorial, n ! {\displaystyle n!\,} satisfaz a mesma relação, já que: A seqüência f n {\displaystyle f_{n}\,} , assim definida satisfaz: Introduzimos, então, mais uma seqüência, g n = f n − f n − 1 {\displaystyle g_{n}=f_{n}-f_{n-1}} , que satisfaz: Como g 2 = f 2 − f 1 = 1 2 d 2 − d 1 = 1 2 {\displaystyle g_{2}=f_{2}-f_{1}={\frac {1}{2}}d_{2}-d_{1}={\frac {1}{2}}} , é fácil ver que: Assim, obtemos, uma expressão para ! n {\displaystyle !n\,}
Imagem: Min. Agricultura Brasil · BY-NC · Openverse
Se observarmos que ∑ k = 0 ∞ ( − 1 ) k 1 k ! = e − 1 {\displaystyle \sum _{k=0}^{\infty }(-1)^{k}{\frac {1}{k!}}=e^{-1}} podemos escrever: O termo mais direita pode ser estimado pelo teste da série alternada: onde [ x ] {\displaystyle \left[x\right]} representa o inteiro mais próximo de x {\displaystyle x\,} .
