Desarranjo: diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
Correções de erros ortográficos ("desaranjo") e de um hiperlink (Bernoulli).
m Correções ortográficas
Linha 13: Linha 13:
== Subfatoriais ==
== Subfatoriais ==
[[Ficheiro:Inclusão.JPG|thumb|right|'''O enésimo elemento troca de posição com o primeiro elemento.''']]
[[Ficheiro: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
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 valores de <math>d_n\,</math>:
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 valores de <math>d_n\,</math>:
* <math>d_1=0\,</math>
* <math>d_1=0\,</math>
* <math>d_2=1\,</math>
* <math>d_2=1\,</math>
Linha 21: Linha 19:
* <math>d_4=9\,</math>
* <math>d_4=9\,</math>


Considere agora os possíveis desarranjos do conjunto <math>\{1,2,3,\ldots, n\}</math> e divido-os em duas classe:
Considere agora os possíveis desarranjos do conjunto <math>\{1,2,3,\ldots, n\}</math> e divida-os em duas classes:
# 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 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 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
# 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

Revisão das 01h01min de 28 de maio de 2020

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

O enésimo elemento troca de posição com o primeiro elemento.

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 divida-os em duas classes:

  1. 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: 12344321.
  2. 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: 12344312
  • 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 .