Permutação Caótica

Objetivos

Nota Histórica.
Definir Permutação Caótica.
Exemplificar.
Definir uma função no Sage para calcular o número de permutações caóticas.

3.2.1 Nota Histórica

O célebre matemático e físico suiço, Leonhard Paul Euler (1707-1783), empenhou-se em resolver uma questão, um tanto quanto curiosa, proposta por Nicolaus Bernoulli (1687-1759), conhecida como "O PROBLEMA DAS CARTAS MAL ENDEREÇADAS" que se fundamenta em esclarecer de quantas formas distintas pode-se colocar

n

cartas em

n

envelopes, endereçados a

n

destinatários diferentes, de modo que nenhuma das cartas seja colocada no envelope correto.

Nessas condições, estamos perante um problema de análise combinatória, intitulado por Permutações Caóticas, também conhecida como Desarranjos ou Desordenamentos, uma Permutação em que nenhum de seus elementos estará presente no seu lugar de origem.

🔗
Figura 3.2.1. Leonarhd Euler, fonte: https://www.phylos.net

3.2.2 Exemplos introdutórios

Vamos iniciar este tópico com dois exemplos para facilitar o entendimento do conceito de permutação caótica e também da demonstração.

Exemplo 3.2.2.

Determine o número de permutações simples dos elementos

$a_{1}, a_{2}, . . ., a_{n},$

nas quais

a_{2}

está na segunda posição ou

a_{3}

está em terceira posição.

Exemplo 3.2.3.

Dentre as permutações simples dos

$n$

elementos

a_{1}, a_{2}, . . ., a_{n}

determine o número daquelas em que

a_{2}

não está na segunda posição,

a_{3}

não está na terceira posição e nem

a_{4}

está na quarta posição.

3.2.3 Permutações Caóticas

Definição 3.2.4.

Uma permutação de uma lista de

$n$

elementos é chamada de permutação caótica, quando nenhum dos elementos da permutação está na posição original, ou seja, uma permutação de

a_{1}, a_{2}, . . ., a_{n}

é chamada de caótica quando nenhum dos

a_{i}^{'} s

se encontra na

i

-ésima posição.

Notação:

�_{�} ou � (�)

Tecnologia 3.2.5.

As permutações caóticas dos elementos

1, 2, 3, 4

podem ser geradas no Sage, com o seguinte comando:

Derangements(4).list()

Tecnologia 3.2.6.

Todos os anagramas de AMOR, de forma que nenhuma letra fique na posição original. Troque as informações da lista para obter o número de permutações caóticas e as permutações caóticas da sua lista.

D = Derangements(['A', 'M', 'O', 'R'])
print('número de permutações caóticas:', len(D))
print('todas as permutações caóticas:')
D.list()

Teorema 3.2.7.

A quantidade de permutações caóticas de um conjunto com

$n$

elementos distintos, pode ser calculada da seguinte maneira:

�_{�} = �! \cdot \sum_{� = 0}^{�} \frac{(- 1)^{�}}{�!} .

Demonstração.

Tecnologia 3.2.8.

Calculando o número de permutações caóticas no Sage:

def D(n):
    d = 0
    for i in range(n+1):
        d = d + (-1)^(i)*(factorial(n)/factorial(i))
    return d
D(8)

Exemplo 3.2.9.

Luiz, Cláudia, Paulo, Rodrigo e Ana brincam entre si de amigo-secreto (ou amigo-oculto). O nome de cada um é escrito em um pedaço de papel, que é colocado em uma urna. Em seguida, cada participante da brincadeira retira da urna um dos pedaços de papel, ao acaso. De quantas formas pode ocorrer a distribuição dos papéis de modo que nenhum dos participantes retire seu próprio nome?

Exemplo 3.2.10.

Quantas são as permutações de

$(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)$

que têm exatamente 4 elementos no seu lugar primitivo?

3.2.4 Outras formas de calcular
$D_{n}$

Teorema 3.2.11.

$D_{n}$

é igual ao inteiro mais próximo de

\frac{n!}{e} .

Demonstração.

Tecnologia 3.2.12.

Calculando o número de permutações caóticas no Sage, usando o Teorema 3.2.11:

def D(n):
    t = (factorial(n)/e).n()
    r = abs(floor(t)-t)
    if r > 1/2:
        return floor(t)+1
    else:
        return floor(t)
D(8)

Teorema 3.2.13.

$n \geq 2,$

�_{�} = � \times �_{� - 1} + (- 1)^{�} .

Demonstração.

Tecnologia 3.2.14.

Calculando o número de permutações caóticas no Sage, usando o Teorema 3.2.13:

def D(n):
    if n==1:
        return 0
    else:
        return n*D(n-1) + (-1)^n
D(8)

Teorema 3.2.15.

$n \geq 3,$

�_{�} = (� - 1) \times (�_{� - 1} + �_{� - 2}) .

Demonstração.

Tecnologia 3.2.16.

Calculando o número de permutações caóticas no Sage, usando o Teorema 3.2.15:

def D(n):
    if n==1:
        return 0
    elif n==2:
        return 1
    else:
        return (n-1)*(D(n-1)+D(n-2))
D(8)

3.2.5 Permutações Caóticas com Repetições

Observe que a Tecnologia 3.2.6 também faz o cálculo no caso de existirem elementos repetidos, mas precisa listar todas as possibilidades, dependendo da quantidade de permutações o cálculo pode demorar.

Esta seção ainda não está pronta, mas a Tecnologia 3.2.17 já está funcionando e usa um algoritmo eficiente, fazendo o cálculo via polinômios de torre.

Tecnologia 3.2.17. Faça você mesmo.

O número de anagramas da palavra MATEMATICA, de forma que nenhuma letra fique na posição original, ou seja, o número de permutações caóticas. Troque as informações da lista para obter o número de permutações caóticas da sua lista.

Figura 3.2.18. Número de Permutações Caóticas podendo ter elementos repetidos.

3.2.6 Exercícios

1.

Suponha que

$# A = n .$

Quantas são as funções

f : A \to A

para as quais a equação

f (x) = x

não possui solução? Quantas são as funções

f : A \to A

bijetoras para as quais a equação

f (x) = x

não possui solução?

2.

Quantas são as permutações de

$(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)$

que têm exatamente 5 elementos no seu lugar primitivo?

3.

Determine o número de permutações caóticas de

$(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)$

nas quais os números

1, 2, 3, 4, 5

ocupam, em alguma ordem, os cinco primeiro lugares.

4.

Uma empresa tem sete estagiárias. Cada uma delas deve cumprir três horas de trabalho semanais, sendo duas horas no turno da manhã e uma no turno da tarde. De quantas maneiras o Recursos Humanos pode montar a agenda de trabalho semanal (segunda a domingo) desses estagiárias, de modo que todas cumpram as três horas semanais, trabalhando diariamente apenas em um turno?