Ir ao conteúdo principal

Análise Combinatória e Probabilidade: Com Aplicações no SageMath

Ricardo Machado, Gabriel Guedes

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.25], cuja versão em inglês pode ser encontrada em [6.26].
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 Permutações Caóticas

Vamos iniciar este tópico com um exemplo para facilitar o entendimento do conceito de permutação caótica.

Exemplo 2.2.2.

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*}

Definição 2.2.3.

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.4.

As permutações caóticas dos elementos \(1, 2, 3, 4\) podem ser geradas no Sage, com o seguinte comando:

Tecnologia 2.2.5.

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.2:
\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.7.

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

Tecnologia 2.2.8.

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

Exemplo 2.2.10.

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.11.

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.3 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.13.

Calculando o número de permutações caóticas no Sage, usando o Teorema 2.2.12:
Pelo Teorema 2.2.6 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.15.

Calculando o número de permutações caóticas no Sage, usando o Teorema 2.2.14:
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.17.

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

Exercícios 2.2.4 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).\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*}

6.

Um chaveiro desastrado embaralha 6 chaves distintas que pertencem a 6 fechaduras diferentes. De quantas maneiras ele pode testar todas as chaves de forma que pelo menos uma chave abra a fechadura correta em que foi colocada?
Resposta.
455
Solução.
Calcular diretamente o cenário "pelo menos uma" exige a soma de vários casos (exatamente uma, exatamente duas, etc.). O caminho mais inteligente é usar o evento complementar.
O evento complementar de "pelo menos uma chave correta" é "nenhuma chave correta" (uma permutação caótica).
O total de maneiras de distribuir as 6 chaves nas 6 fechaduras é \(6! = 720\text{.}\)
O número de maneiras de errar todas as chaves é \(D_6 = 265\text{.}\)
Logo, o número de arranjos onde pelo menos uma chave acerta é:
\begin{equation*} 720 - 265 = 455 \text{ maneiras}. \end{equation*}

7.

Em uma corrida, 6 atletas receberam as raias de 1 a 6. Para a corrida seguinte, as raias foram sorteadas novamente. De quantas maneiras esse novo sorteio pode ocorrer de modo que exatamente a metade dos atletas permaneça na mesma raia da corrida anterior?
Resposta.
40
Solução.
O problema exige que exatamente 3 atletas fiquem em seus lugares (posições fixas) e os outros 3 atletas troquem de lugar entre si (nenhum pode ficar na raia original).
Primeiro, escolhemos quais 3 atletas permanecerão nas mesmas raias. Isso pode ser feito de \(C_6^3\) maneiras.
Em seguida, para os 3 atletas restantes, devemos distribuí-los de forma caótica nas 3 raias que sobraram. Isso pode ser feito de \(D_3\) maneiras.
Pelo Princípio Multiplicativo, o total de sorteios é:
\begin{equation*} C_6^3 \times D_3 = 20 \times 2 = 40 \text{ maneiras}. \end{equation*}

8.

Um grupo de 6 amigos (Alice, Bruno, Carlos, Diana, Eduardo e Fernanda) realiza um sorteio de amigo secreto. Sabendo que o sorteio foi validado (ou seja, ninguém tirou a si mesmo), em quantos desses sorteios válidos Alice tira especificamente o nome de Bruno?
Resposta.
53
Solução.
Sabemos que o número total de sorteios válidos (permutações caóticas) para 6 pessoas é \(D_6 = 265\text{.}\)
Em uma permutação caótica, Alice é obrigada a tirar o nome de outra pessoa. Como há 6 pessoas no grupo e ela não pode tirar a si mesma, Alice tem exatamente 5 opções possíveis para sortear (Bruno, Carlos, Diana, Eduardo ou Fernanda).
Por simetria, a quantidade de cenários em que Alice tira qualquer um de seus 5 amigos é idêntica. Logo, o número de sorteios em que Alice tira o nome de um amigo específico (neste caso, Bruno) é exatamente a quinta parte do total de permutações caóticas:
\begin{equation*} \frac{D_6}{5} = \frac{265}{5} = 53 \text{ maneiras}. \end{equation*}

9.

Ainda sobre o amigo secreto do exercício anterior, os 6 amigos decidiram refazer o sorteio. Porém, além da regra padrão (ninguém pode tirar a si mesmo), adicionou-se uma nova restrição: Carlos e Diana brigaram, então Carlos se recusa a tirar o nome de Diana. Quantos são os sorteios válidos agora?
Resposta.
212
Solução.
Podemos resolver isso utilizando a simetria deduzida no exercício anterior. O total de sorteios caóticos irrestritos para 6 pessoas é \(D_6 = 265\text{.}\)
Queremos excluir do total todos os cenários em que Carlos tira o nome de Diana. Pelo princípio da simetria, sabemos que a quantidade de sorteios caóticos em que uma pessoa "X" tira uma pessoa específica "Y" é exatamente \(\frac{D_n}{n-1}\text{.}\)
Portanto, existem exatamente \(\frac{265}{5} = 53\) sorteios válidos onde Carlos tira Diana. Subtraindo esses casos proibidos do total geral:
\begin{equation*} 265 - 53 = 212 \text{ sorteios válidos}. \end{equation*}

10.

Em Álgebra Linear, uma "matriz de permutação" é uma matriz quadrada formada apenas por zeros e uns, contendo exatamente um '1' em cada linha e em cada coluna. Quantas matrizes de permutação de tamanho \(5 \times 5\) possuem a diagonal principal inteiramente preenchida por zeros?
Resposta.
44
Solução.
As matrizes de permutação representam algebricamente rearranjos de elementos. Uma matriz \(n \times n\) desse tipo tem os seus '1's em posições \((i, p_i)\text{,}\) onde \(p_i\) é a nova posição do elemento da linha \(i\text{.}\)
A diagonal principal é formada pelas coordenadas \((i, i)\text{.}\) Exigir que a diagonal principal tenha apenas zeros significa garantir que nenhum '1' ocupe a posição \((i, i)\text{.}\) Em linguagem combinatória, isso significa que \(p_i \neq i\) para todo \(i\text{.}\)
Isso é a definição exata de uma permutação caótica. Para \(n=5\text{,}\) o número de matrizes que satisfazem essa condição é simplesmente:
\begin{equation*} D_5 = 44. \end{equation*}

11.

Prove, utilizando a relação de recorrência \(D_n = n \cdot D_{n-1} + (-1)^n\text{,}\) que o número de permutações caóticas \(D_n\) é um número ímpar se, e somente se, \(n\) for um número par.
Solução.
Vamos demonstrar analisando a paridade termo a termo, sabendo que os casos base são \(D_1 = 0\) (par) e \(D_2 = 1\) (ímpar).
Se \(n\) é par:
Como \(n\) é par, a multiplicação \(n \cdot D_{n-1}\) resultará obrigatoriamente em um número par (pois qualquer inteiro multiplicado por um par resulta em par).
O termo \((-1)^n\text{,}\) com \(n\) par, resulta em \(+1\) (que é ímpar).
A soma de um número par com um número ímpar sempre resulta em um número ímpar. Logo, se \(n\) é par, \(D_n\) é ímpar.
Se \(n\) é ímpar:
Como \(n\) é ímpar, então o antecessor \(n-1\) é par. Pela conclusão acima, se \(n-1\) é par, sabemos indutivamente que \(D_{n-1}\) é ímpar.
A multiplicação de dois números ímpares (\(n\) e \(D_{n-1}\)) resulta em um número ímpar.
O termo \((-1)^n\text{,}\) com \(n\) ímpar, resulta em \(-1\) (que também é ímpar).
A soma ou subtração de dois números ímpares sempre resulta em um número par. Logo, se \(n\) é ímpar, \(D_n\) é par.
Isso prova definitivamente que \(D_n\) é ímpar se e somente se \(n\) for par.

12.

A identidade combinatória \(\sum_{k=0}^n C_n^k D_{n-k} = n!\) relaciona binômios, permutações caóticas e permutações totais. Justifique a veracidade desta identidade utilizando um raciocínio puramente combinatório, sem manipulações algébricas.
Solução.
Considere o conjunto de todas as permutações possíveis de \(n\) elementos. Sabemos que a quantidade total dessas permutações é, inegavelmente, \(n!\) (o lado direito da equação).
Toda permutação possui uma quantidade exata de "pontos fixos" (elementos que permaneceram em suas posições originais). Essa quantidade, chamemos de \(k\text{,}\) pode variar de \(0\) (nenhum elemento no lugar) até \(n\) (todos os elementos no lugar).
Se quisermos construir uma permutação que tenha exatamente \(k\) pontos fixos, precisamos realizar duas tarefas:
  • Tarefa 1: Escolher quais serão os \(k\) elementos privilegiados que não mudarão de lugar. Isso pode ser feito de \(C_n^k\) maneiras.
  • Tarefa 2: Pegar os \(n-k\) elementos que sobraram e rearranjá-los de modo que nenhum deles caia em sua posição original. Por definição, isso é uma permutação caótica, que pode ser feita de \(D_{n-k}\) maneiras.
Pelo Princípio Multiplicativo, existem exatamente \(C_n^k \times D_{n-k}\) permutações contendo exatamente \(k\) pontos fixos.
Como os cenários variando o valor de \(k\) (de 0 até \(n\)) formam casos mutuamente exclusivos e cobrem absolutamente todas as permutações possíveis, o Princípio Aditivo garante que a soma de todos os casos deve resultar no total incondicional de permutações:
\begin{equation*} \sum_{k=0}^n C_n^k D_{n-k} = n! \end{equation*}
<Anterior^TopPróximo>
Feito com PreTeXt
Powered by Runestone