Permutação Caótica – Explorando o tema

Permutação Caótica – Explorando o tema

Um problema análogo ao do amigo-secreto é o seguinte:

  • De quantas maneiras distintas podemos colocar cartas em envelopes endereçados a destinatários diferentes, de modo que nenhuma das cartas seja colocada no envelope correto?

Relatos históricos indicam que esse problema foi originalmente proposto por Nicolaus Bernoulli, membro da prestigiosa família Bernoulli, no séc XVIII, e resolvido pelo célebre matemático Leonhard Euler.
Esse problema ilustra uma daquelas situações nas quais nos perguntamos:
– E se der tudo errado? E se nada ocorrer conforme prevíamos?
Em Análise Combinatória, situações como essas são estudadas utilizando o que a matemática denomina como Permutação Caótica.
Aqui, vamos explorar um pouco da matemática desse assunto que apresentamos de uma maneira informal na Sala Inicial.




O que você precisa saber

Para que você entenda sem problemas o que iremos apresentar, você vai precisar de dois objetos e um princípio da matemática. Vamos fazer uma brevíssima apresentação dos três assuntos e deixaremos indicadas Salas do nosso Blog nas quais você encontrará material que pode ajudá-lo, caso você queira ou precise aprofundar seu conhecimento.
Para acessar as informações de um dos quatro tema, clique no botão correspondente.




Permutações caóticas

Definição: Considere [tex]n[/tex] elementos colocados em uma certa ordem definindo uma sequência que denotaremos por [tex]\left(a_1,a_2,a_3,\cdots,a_n \right)[/tex].
Uma permutação dos elementos dessa sequência é dita uma Permutação Caótica ou um Desarranjo quando nenhum dos elementos [tex]a_i[/tex] está na sua posição original, isto é, na [tex]i[/tex]-ésima posição.
Denotaremos por [tex]D_{n}[/tex] o número de permutações caóticas de [tex]n[/tex] elementos.
Observe que o conceito de Permutação Caótica é relativo a uma disposição inicial que tomamos como referencial ou padrão. Além disso, o número [tex]D_{n}[/tex] não está associado ao tipo de elementos de uma sequência, mas sim às posições ocupadas por tais elementos. Dessa forma, é comum em alguns livros sobre o assunto que a definição de Permutação Caótica de [tex]n[/tex] elementos se refira à sequência [tex](1,\, 2,\, 3,\, \cdots\, ,n).[/tex]

A nossa discussão inicial será sobre uma justificativa da fórmula para o número de permutações caóticas [tex]D_{n}[/tex] apresentada na Sala inicial :

[tex]\fcolorbox{black}{#B2EDE0}{$D_{n}=n! \cdot \left[\dfrac{1}{0!} – \dfrac{1}{1!} + \dfrac{1}{2!} – \dfrac{1}{3!} + \dots + \dfrac{(-1)^{n}}{n!}\right]$}\, [/tex].

Para acompanhar a discussão, basta clicar no próximo botão.







Continuando a nossa discussão, vamos aproveitar a ideia utilizada na discussão informal que antecedeu a apresentação da fórmula de recorrência

[tex]\fcolorbox{black}{#B2EDE0}{$D_{n}=(n-1) \cdot \left(D_{n-2}+D_{n-1}\right)$}\,[/tex].

na Sala inicial para fazer uma justificativa mais completa dessa fórmula de recorrência.

Para acompanhar mais esta discussão, basta clicar no próximo botão.

Um vídeo para ilustrar…

Este vídeo mostra a solução genérica do problema da prateleira com livros apresentado na Sala inicial .
O raciocínio utilizado é bem parecido com a demonstração que fizemos para a fórmula de recorrência das Permutações Caóticas.


Livros na prateleira







Para que você não pense que as duas fórmulas que apresentamos não estão relacionadas ou não forneçam os mesmos valores, vamos obter a primeira como consequência da segunda.

Acompanhe a dedução clicando no botão abaixo.







Esperamos que você tire proveito da explanação feita aqui.
Nosso objetivo é tentar sempre facilitar o seu entendimento sobre assuntos importantes da Matemática.




Equipe COM – OBMEP

Voltar para Sala Inicial

Link permanente para este artigo: http://clubes.obmep.org.br/blog/permutacao-caotica-explorando-o-tema/