Desarranjo: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
← nova página: Em análise combinatória, um '''desaranjo''', também conhecido como '''permutação caótica''' ou '''''derangement''''' (do francês) é u... |
|||
Linha 1:
Em [[análise combinatória]], um '''desaranjo''', também conhecido como '''permutação caótica''' ou '''''derangement''''' (do [[Língua francesa|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]] <math>\phi:S\to S \,</math> em um [[conjunto]] finito <math>S\,</math> que não possui [[ponto fixo|pontos fixos]]. O número de diferentes desaranjos em um conjunto de '''n''' elementos é definido como o '''subfatorial''' de '''n''' e é denotado <math>!n\,</math>. O problema de contar desaranjos foi primeiramente considerado por [[Pierre Raymond de Montmort]] em [[1708]] e resolvido em [[1713]]. [[Nicolaus I Bernoulli|Nicholas Bernoulli]] obteve o mesmo resultado na mesma época.
Os dois possíveis desaranjos das três letras da palavra "lua":
*ual
Linha 11:
*ocan, onca, onac
==Subfatoriais==
[[imagem:inclusão.jpg|thumb|right|'''O enésimo elemento troca de posição com o primeiro elemento.''']]
Defina <math>d_n:=!n\,</math> o número de possíveis desarranjos para um conjunto de <math>n\,</math> elementos. Podemos
encontrar uma [[relação de recorrência]] para <math>d_n\,</math> usando o método de inclusão-exclusão.
É fácil calcular os primeiros valored de <math>d_n\,</math>:
*d_1=0
*d_2=1
*d_3=2
*d_4=9
Considere agora que os possíveis desaranjos do conjunto <math>\{1,2,3,\ldots, n\}</math> e divido-os em duas classe:
#Os desaranjos em que o elemento '''n''' assume a posição de um elemento <math>k\,</math> e o elemento '''k''' assume a posição de '''n'''. Exemplo: '''1'''23'''4''' -> '''4'''32'''1'''.
#Os desaranjos em que o elemento '''n''' assume a posição de um elemento <math>k\,</math> e o elemento '''k''' '''não''' assume a posição de '''n'''. Exemplo: '''1'''23'''4''' -> '''4'''3'''1'''2
*O número de desarranjos na classe '''1''' deve ser igual ao número de desarranjos de um conjunto com <math>n-2\,</math> elementos para cada possível posição que o enésimo elemento pode assumir, ou seja: <math>(n-1)d_{n-2}\,</math>.
*O número de desarranjos na classe '''2''' deve ser igual ao número de desarranjos de um conjunto com <math>n-1\,</math> elementos para cada possível posição que o enésimo elemento pode assumir, ou seja: <math>(n-1)d_{n-1}\,</math>. 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 <math>\{1,2,\ldots,k-1,k+1,k+2,\ldots,n-1,k\}</math>.
A relação de recorrência para <math> d_n\,</math> é portanto dada por:
*<math>\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.</math>
[[categoria:Combinatória]]
| |||