Desarranjo: diferenças entre revisões
Linha 29: | Linha 29: | ||
*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>. |
*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 |
A seqüência dos subfatoriais é, portanto, unicamente determinada pela sua relação de recorrência e pelos dois valores iniciais: |
||
*<math>\left\{ |
*<math>\left\{ |
||
\begin{array}{l} |
\begin{array}{l} |
||
Linha 36: | Linha 36: | ||
d_n= (n-1) \left(d_{n-1}+d_{n-2}\right) |
d_n= (n-1) \left(d_{n-1}+d_{n-2}\right) |
||
\end{array}\right.</math> |
\end{array}\right.</math> |
||
==Relação com o fatorial== |
|||
É importante observar que o [[fatorial]], <math>n!\,</math> satisfaz a mesma relação, já que: |
|||
*<math>(n-1)\left[(n-1)!+(n-2)!\right]=(n-1)(n-1)!+(n-1)!=n(n-1)!=n!</math> |
|||
Assim, é natural definir: |
|||
*<math>f_n= \frac{d_n}{n!}</math> |
|||
A seqüência <math>f_n\,</math>, assim definida satisfaz: |
|||
*<math>f_n-f_{n-1}= -\frac{1}{n}\left(f_{n-1}-f_{n-2}\right)</math> |
|||
Introduzimos, então, mais uma seqüência, <math>g_n=f_n-f_{n-1}</math>, que satisfaz: |
|||
*<math>g_n= -\frac{1}{n}g_{n-1}</math> |
|||
Como <math>g_2=f_2-f_1=d_1-\frac{1}{2}d_2=-\frac{1}{2}</math>, é fácil ver que: |
|||
*<math>g_k= \frac{(-1)^{k}}{k!},~~n\geq 2 </math> |
|||
E, portanto, |
|||
*<math> |
|||
\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} |
|||
</math> |
|||
Assim, obtemos, uma expressão para <math>!n\,</math> |
|||
*<math>!n=d_n=n! f_n = \sum_{k=0}^{n}(-1)^{k}\frac{n!}{k!} </math> |
|||
[[categoria:Combinatória]] |
[[categoria:Combinatória]] |
Revisão das 04h25min de 10 de julho de 2008
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 valored de :
Considere agora que 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