Desarranjo: diferenças entre revisões
m arrumendo ilink |
Correções de erros ortográficos ("desaranjo") e de um hiperlink (Bernoulli). |
||
Linha 1: | Linha 1: | ||
Em [[análise combinatória]], um ''' |
Em [[análise combinatória]], um '''desarranjo''', 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 desarranjo é 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 desarranjos em um conjunto de '''n''' elementos é definido como o '''subfatorial''' de '''n''' e é denotado <math>!n\,</math>. O problema de contar desarranjos foi primeiramente considerado por [[Pierre Raymond de Montmort]] em [[1708]] e resolvido em [[1713]]. [[Nicolau I Bernoulli|Nicholas Bernoulli]] obteve o mesmo resultado na mesma época. |
||
== Exemplos == |
== Exemplos == |
||
Os dois possíveis |
Os dois possíveis desarranjos das três letras da palavra "lua": |
||
* ual |
* ual |
||
* alu |
* alu |
||
Os nove possíveis |
Os nove possíveis desarranjos das quatro letras da palavra "cano": |
||
* acon, anoc, aocn |
* acon, anoc, aocn |
||
* ncoa, noca, noac |
* ncoa, noca, noac |
||
Linha 21: | Linha 21: | ||
* <math>d_4=9\,</math> |
* <math>d_4=9\,</math> |
||
Considere agora os possíveis |
Considere agora os possíveis desarranjos do conjunto <math>\{1,2,3,\ldots, n\}</math> e divido-os em duas classe: |
||
# Os |
# Os desarranjos 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 |
# Os desarranjos 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 '''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 |
* 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 desarranjos no conjunto <math>\{1,2,\ldots,k-1,k+1,k+2,\ldots,n-1,k\}</math>. |
||
A seqüência dos subfatoriais é, portanto, unicamente determinada pela sua relação de recorrência e pelos dois valores iniciais: |
A seqüência dos subfatoriais é, portanto, unicamente determinada pela sua relação de recorrência e pelos dois valores iniciais: |
Revisão das 03h19min de 22 de março de 2016
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.
Exemplos
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
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 desarranjos do conjunto e divido-os em duas classe:
- 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: 1234 → 4321.
- 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: 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 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 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 .