[skip-to-content]

Seção 2.2 Permutações Caóticas

Subseção 2.2.1 Nota Histórica

O primeiro problema notório relacionado a permutações caóticas é conhecido como "O Problema das Cartas Mal Endereçadas". Este enigma matemático tem conexões com figuras ilustres, como Pierre Raymond de Montmort (1678-1719) e Nicholas Bernoulli (1687-1759). Outro eminente matemático que se deparou com esse desafio foi Leonhard Euler (1707-1783). A solução por Euler foi publicada em seu artigo intitulado "Calcul de la probabilité dans le jeu de rencontre" [6.21], cuja versão em inglês pode ser encontrada em [6.22].

Atualmente, este 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 2.2.1. Leonarhd Euler, fonte: https://www.phylos.net

Subseção 2.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 2.2.2.

Determine o número de permutações simples dos elementos \(a_1, a_2, . . . , a_n\text{,}\) nas quais \(a_2\) está na segunda posição ou \(a_3\) está em terceira posição.

Solução

Definindo \(A_2\) como o conjunto das permutações em que \(a_2\) está em segunda posição e \(A_3\) como o conjunto das permutações em que \(a_3\) está em terceira posição, é fácil ver que

\begin{equation*} \#(A_{2})=\#(A_{3})=(n-1)! \end{equation*}

e que

\begin{equation*} \#(A_{2}\cap A_{3})=(n-2)!. \end{equation*}

Assim o número procurado nada mais é do que \(\#(A_{2} \cup A_{3})\) que é igual a:

\begin{align*} \#(A_2\cup A_3) = \amp ~ \#(A_2) + \#(A_3) - \#(A_2\cap A_3) \\ = \amp ~ (n-1)! + (n-1)!-(n-2)! \\ = \amp ~ 2\cdot(n-1)! - (n-2)! \\ = \amp ~ 2\cdot(n - 1)\cdot(n - 2)! - (n - 2)! \\ = \amp ~ (n-2)!\cdot(2n-2-1) \\ = \amp ~ (2n-3)\cdot(n-2)! \end{align*}
Exemplo 2.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.

Solução

Definimos \(A_i\text{,}\) para \(i = 2, 3, 4\text{,}\) como o conjunto das permutações em que \(a_i\) está no \(i\)-ésima posição, para \(i = 2, 3, 4\text{.}\) Queremos encontrar o número de elementos no complementar de \(A_2\cup A_3\cup A_4\text{.}\)

As cardinalidade dos conjuntos \(A_i's\) e das interseções dos \(A_i's\text{,}\) dois a dois e três a três são:

\(\#(A_2) = \#(A_3) = \#(A_4) = (n-1)!;\)

\(\#(A_2\cap A_3) = \#(A_2\cap A_4) = \#(A_3\cap A_4) = (n-2)!;\)

\(\#(A_2\cap A_3\cap A_4) = (n-3)!.\)

Sabendo que o número total de permutações é \(n!\text{,}\) a solução para o questionamento é

\begin{gather*} n!-\#(A_2)-\#(A_3)-\#(A_4)+\#(A_2\cap A_3)+ \\ ~~~~~~~~~~~~~ +\#(A_2\cap A_4)+\#(A_3\cap A_4)-\#(A_2\cap A_3\cap A_4) \end{gather*}

Que é igual a:

\begin{equation*} n!-3\times (n-1)!+3 \times (n-2)!-(n-3)! \end{equation*}

Subseção 2.2.3 Permutações Caóticas

Definição 2.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:

\begin{equation*} D_n \text{ ou } D(n) \end{equation*}
Tecnologia 2.2.5.
As permutações caóticas dos elementos \(1, 2, 3, 4\) podem ser geradas no Sage, com o seguinte comando:
Tecnologia 2.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.

Considere todas as permutações dos elementos \(a_1 , a_2 , \ldots , a_n\text{.}\) Indicando por \(A_i\) todas as permutações formadas pelos elementos \(a_1 , a_2 , \ldots , a_n\) com \(a_i\) no \(i\)-ésimo lugar, calcularemos \(D_n\text{,}\) usando a ideia do Exemplo 2.2.3:

\begin{align*} D_n = \amp~n! - \#(A_1\cup A_2\cup \cdots \cup A_n)\\ = \amp ~ n! - \sum_{i=1}^{n}\#A_i + \sum_{0\lt i\lt j\leq n}\#(A_i\cap A_j)+\cdots \\ \amp ~ \quad \cdots +(-1)^{n-1}\#(A_1\cap A_2\cap \cdots\cap A_n). \end{align*}

Visto que existem \(n\) termos no primeiro somatório, \(C_n^2\) termos no segundo, \(C_n^3\) termos no terceiro,\(\cdots\text{,}\) \(C_n^n=1\) no último e

\begin{align*} \#(A_i) \amp = (n-1)! \\ \#(A_i\cap A_j) \amp = (n-2)! \\ \#(A_i\cap A_j\cap A_k) \amp = (n-3)! \\ \vdots ~~~~~ \amp = ~~ \vdots \\ \#(A_1\cap A_2\cap\cdots\cap A_n) \amp = 1 \end{align*}

temos

\begin{align*} D_n \amp = ~ n!-n\cdot(n-1)!+C_n^2\cdot(n-2)!-C_n^3\cdot(n-3)!+\cdots +(-1)^n\cdot 1 \\ \amp = ~ n!-\dfrac{n!}{1!}+\dfrac{n!}{2!}-\dfrac{n!}{3!}+\cdots +(-1)^n\cdot \dfrac{n!}{n!} \end{align*}

evidenciando \(n!\text{,}\) obtém-se:

\begin{align*} D_n \amp = ~ n!\cdot\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+(-1)^n\cdot \dfrac{1}{n!}\right) \\ \amp = ~ n!\cdot\sum_{i=0}^{n}\dfrac{(-1)^i}{i!} \end{align*}
Tecnologia 2.2.8.
Calculando o número de permutações caóticas no Sage:
Tecnologia 2.2.9.

Escolha um intervalo de variação, para obter uma lista com as permutações caóticas para cada valor do intervalo.

Figura 2.2.10.
Exemplo 2.2.11.

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?

Solução

Uma clássica questão de permutação caótica, visto que durante a distribuição dos papéis nenhum dos participantes poderá retirar seu próprio nome. Assim o número de maneiras de ocorrer tal evento, é dado por:

\begin{align*} D_5 \amp = ~5!\cdot\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\right) \\ \amp = ~5!-5! + \frac{5!}{2!} -\frac{5!}{3!} + \frac{5!}{4!}-\frac{5!}{5!} \\ \amp = ~5\cdot 4 \cdot 3 -5\cdot 4 + 5 - 1 \\ \amp = ~60-20+5-1 \\ \amp = ~44 \end{align*}
Exemplo 2.2.12.

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?

Solução

O número de modos de escolher os quatro elementos que ocuparão o seu lugar primitivo é \(C_{10}^4\text{.}\)

Com estes elementos em seus lugares, os outros seis elementos devem ser arrumados de forma caótica. o que pode ser feito de \(D_6\) formas. A resposta é

\begin{equation*} C_{10}^4\times D_6 = 55650. \end{equation*}

Subseção 2.2.4 Outras formas de calcular \(D_n\)

Para \(n=1\) e \(n=2\) a verificação é direta. Para \(n>2\) vamos usar a expansão em série de portência de \(e^x\text{:}\)

\begin{equation*} e^x = \frac{1}{0!} + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!}+\cdots \end{equation*}

para \(x = -1\) temos

\begin{equation*} e^{-1} = \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}+\cdots \end{equation*}

Calculando

\begin{align*} \left| D_n -\frac{n!}{e} \right| \amp = ~n!\times\left| \frac{(-1)^{n+1}}{(n+1)!} + \frac{(-1)^{n+2}}{(n+2)!} +\cdots \right| \\ \amp \leq n!\times \left( \frac{1}{(n+1)!} + \frac{1}{(n+2)!}+\cdots \right) \\ \amp \leq \frac{1}{(n+1)} + \frac{1}{(n+1)(n+2)} +\cdots \\ \amp \leq \frac{1}{(n+1)} + \frac{1}{(n+1)^2} + \cdots \end{align*}

Aplicando a fórmula da soma da PG, ficamos com

\begin{equation*} \left| D_n -\frac{n!}{e} \right| \leq \frac{\frac{1}{n+1}}{1-\frac{1}{n+1}} = \frac{1}{n}\lt \frac{1}{2}. \end{equation*}
Tecnologia 2.2.14.
Calculando o número de permutações caóticas no Sage, usando o Teorema 2.2.13:

Pelo Teorema 2.2.7 temos

\begin{equation*} D_n = n!\times \left( \frac{1}{0!} - \frac{1}{1!} + \cdots + \frac{(-1)^n}{n!} \right). \end{equation*}

Isolando a última parcela da soma, ficamos com

\begin{equation*} D_n = n!\times \left( \frac{1}{0!} - \frac{1}{1!} + \cdots + \frac{(-1)^{n-1}}{(n-1)!} \right) + n!\times \frac{(-1)^n}{n!}. \end{equation*}

Cancelando \(n!\) do último termo e reescrevendo \(n!\) como \(n\times (n-1)!\text{,}\) obtemos

\begin{equation*} D_n = n\times\underbrace{(n-1)!\times \left( \frac{1}{0!} - \frac{1}{1!} + \cdots + \frac{(-1)^{n-1}}{(n-1)!} \right)}_{D_{n-1}} + (-1)^n, \end{equation*}

Ou seja,

\begin{equation*} D_n = n\times D_{n-1}+(-1)^n. \end{equation*}
Tecnologia 2.2.16.
Calculando o número de permutações caóticas no Sage, usando o Teorema 2.2.15:

Vamos separar as permutações caóticas de \(1, 2, 3, \ldots, n\) em dois casos.

1º caso: permutações caóticas em que o elemento que ocupa o primeiro lugar tem seu lugar original ocupado pelo 1.

Como temos \(n-1\) elementos, diferentes do \(1\text{,}\) para cada um deles podemos colocar o elemento na 1ª posição e o número 1 na posição deste número, ou seja, temos \(n-1\) maneiras de fazer isto. Depois disto, os outros elementos podem ser distribuídos de \(D_{n-2}\) formas.

2º caso: permutações caóticas em que o elemento que ocupa o primeiro lugar não tem seu lugar original ocupado pelo 1.

Temos \(n-1\) formas de escolher o elemento que ocupará o primeiro lugar, já que o número 1 não pode ocupar esta posição. Depois disto precisamos contar o número de maneiras de distribuir (de forma caótica) os \(n-1\) elementos nos \(n-1\) lugares, de forma que o número 1 não fique na posição original do número que está na 1ª posição. Para contar esta quantidade, podemos contar o número de permutações caóticas desses \(n-1\) elementos organizados da seguinte maneira: coloque os \(n-2\) elementos em suas posições originais e o número 1 na posição do elemento que está na 1ª posição. O número dessas permutações caóticas é \(D_{n-1}.\)

Como os dois casos são excludentes e cobrem todas as possibilidades, pelo princípio aditivo, temos

\begin{equation*} D_n = (n-1)\times D_{n-2} + (n-1)\times D_{n-1} = (n-1)\times (D_{n-1}+D_{n-2}). \end{equation*}

Tecnologia 2.2.18.
Calculando o número de permutações caóticas no Sage, usando o Teorema 2.2.17:

Exercícios 2.2.5 Exercícios

1.

Suponha que \(\#A=n\text{.}\) Quantas são as funções \(f:A\rightarrow A\) para as quais a equação \(f(x)=x\) não possui solução? Quantas são as funções \(f:A\rightarrow A\) bijetoras para as quais a equação \(f(x)=x\) não possui solução?

Resposta

a) \((n-1)^n\text{,}\) b) \(D_n\text{.}\)

Solução

item a) A imagem de cada elemento do domínio pode ser escolhida de \(n-1\) maneiras, assim, o total é \((n-1)^n\text{.}\)

item b) Como \(f\) é bijetiva, cada elemento do domínio terá uma imagem diferente, e além disso, a imagem precisa ser diferente do argumento da função, então existem \(D_n\) funções.

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?

Resposta

1468368

Solução

Podemos escolher os 5 elementos que ocuparão seus lugares primitivos de \(C_{12}^5\) maneiras. Em seguida, podemos escolher as posições dos 7 elementos restantes de \(D_7\) maneiras. Logo, o total é

\begin{equation*} C_{12}^5\times D_7=1468368. \end{equation*}
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.

Resposta

81576

Solução

Podemos escolher a posição dos 5 primeiros elementos de \(D_5\) maneiras e a posição dos 7 últimos elementos de \(D_7\) maneiras. Portanto, o total é

\begin{equation*} D_5 \times D_7 = 81576. \end{equation*}
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?

Resposta

9344160

Solução

O horário do turno da manhã pode ser escolhido de \(P_7\) maneiras, uma vez feita a escolha, o horário do turno da tarde pode ser feito de \(D_7\) maneiras. O total de maneiras é

\begin{equation*} P_7\times D_7 = 9344160. \end{equation*}
5.

(OBM 2019 - Nível Universitário 2ª Fase Q6 - Modificado) Um grupo de \(n\) pessoas fará um amigo oculto e o sorteio dos nomes deverá satisfazer duas condições:

  1. Ninguém pode tirar o próprio nome;
  2. Não podem existir duas pessoas \(A\) e \(B\) tais que \(A\) tirou \(B\) e \(B\) tirou \(A\text{.}\)

De quantas maneiras poderá ser realizado o sorteio?

Resposta
\(\displaystyle D_n + \sum_{k=1}^{\lfloor \frac{n}{2} \rfloor} n!\cdot \left(-\frac{1}{2} \right)^k\cdot \frac{D_{n-2k}}{(n-2k)!}\)
Solução

Denote as \(n\) pessoas por \(P_1, P_2, \ldots, P_n\text{.}\) Sejam \(A_{ij}\text{,}\) com \(1\leq i\lt j\leq n\text{,}\) os conjuntos das permutações caóticas em que a pessoa \(P_i\) tirou a pessoa \(P_j\) e a pessoa \(P_j\) tirou a pessoa \(P_i\text{.}\) A resposta deste problema é dada por

\begin{equation} D_n - \#\left( \bigcup_{1\leq i \lt j \leq n} A_{ij} \right).\label{que-cao-obm}\tag{2.2.1} \end{equation}

Para obter este valor, usaremos o Princípio da Inclusão-Exclusão.

Observe que \(A_{ij}\) possui a mesma cardinalidade, independetemente dos valores dos índices, assim como \(A_{ij}\cap A_{kl}\) também possui a mesma cardinalidade, independentemente dos índices, e assim por diante. Então, para usar o Princípio da Inclusão-Exclusão, precisamos calcular essas cardinalidades e as quantidades dos conjuntos \(A_{ij}\text{,}\) das interseções duas a duas, três a três e assim por diante. Sem perda de generalidade, vamos fixar os índices:

  • \(\#A_{12}=D_{n-2}\) e no total são \(C_n^2\) conjuntos deste tipo, pois para formar um conjunto \(A_{ij}\text{,}\) precisamos escolher duas pessoas de \(n\) disponíveis.
  • \(\#(A_{12}\cap A_{34})=D_{n-4}\) e no total são \(C_n^2C_{n-2}^2\) conjuntos deste tipo, pois para formar uma interseção \(A_{ij}\cap A_{ls}\text{,}\) precisamos escolher duas pessoas de \(n\) disponíveis e depois mais duas de \(n-2\) disponíveis.
  • A cardinalidade da interseção de \(k\) conjuntos é \(D_{n-2k}\) e no total são \(C_n^2C_{n-2}^2\cdots C_{n-2k}^2\) conjuntos deste tipo, pois para formar uma interseção de \(k\) conjuntos, precisamos escolher duas pessoas de \(n\) disponíveis e depois mais duas de \(n-2\) disponíveis e assim por diante, até que precisamos escolher duas pessoas de \(n-2k\) disponíveis.

Antes de escrever o resultado da Expressão (2.2.1) vamos obter uma expressão para \(C_n^2C_{n-2}^2\cdots C_{n-2k}^2\text{.}\)

\begin{align*} C_n^2C_{n-2}^2\cdots C_{n-2k}^2 =\amp~ \frac{n!}{2!(n-2)!}\cdot \frac{(n-2)!}{2!(n-4)!}\cdots \frac{(n-2k)!}{2!(n-2(k+1))!}\\ =\amp~\frac{n!}{(n-2(k+1))!2^{k+1}}. \end{align*}

Utilizando essas informações na Expressão (2.2.1), obtemos

\begin{equation*} D_n - \#\left( \bigcup_{1\leq i \lt j \leq n} A_{ij} \right)=\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \end{equation*}
\begin{align*} \quad\quad=\amp~ D_n - C_n^2D_{n-2} +C_n^2C_{n-2}^2D_{n-4} - \cdots\\ =\amp~ D_n - \frac{n!}{2!(n-2)!}\cdot D_{n-2} + \frac{n!}{2!(n-2)!}\cdot\frac{(n-2)!}{2!(n-4)!}\cdot D_{n-4}-\cdots\\ =\amp~D_n +\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \frac{n!(-1)^{k+1}D_{n-2(k+1)}}{(n-2(k+1))!2^{k+1}} \end{align*}

Fazendo a mudança \(p=k+1\text{,}\)

\begin{equation*} D_n - \#\left( \bigcup_{1\leq i \lt j \leq n} A_{ij} \right)= D_n + \sum_{p=1}^{\lfloor \frac{n}{2} \rfloor} n!\cdot \left(-\frac{1}{2} \right)^p \cdot \frac{D_{n-2p}}{(n-2p)!}. \end{equation*}