Desarranjo: diferenças entre revisões
Linha 69: | Linha 69: | ||
* <math>!n= \left[\frac{n!}{e}\right] </math> |
* <math>!n= \left[\frac{n!}{e}\right] </math> |
||
onde <math> \left[x\right] </math> representa o inteiro mais próximo de <math>x\,</math>. |
onde <math> \left[x\right] </math> representa o inteiro mais próximo de <math>x\,</math>. |
||
=== {{Ligações externas}} === |
|||
* [http://legauss.blogspot.com/2010/12/amigo-secreto-e-matematica.html Amigo secreto e matemática] |
|||
[[Categoria:Combinatória]] |
[[Categoria:Combinatória]] |
Revisão das 14h12min de 4 de janeiro de 2011
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 em um conjunto finito 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 . 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
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
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 desaranjos do conjunto e divido-os em duas classe:
- Os desaranjos em que o elemento n assume a posição de um elemento e o elemento k assume a posição de n. Exemplo: 1234 → 4321.
- Os desaranjos 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: 1234 → 4312
- 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 desaranjos 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 fatorial
É 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 Euler
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 .