Questão 3 de Combinatória estilo ITA resolvida

Enunciado

Seja $\mathcal S$ o conjunto das permutações $\sigma$ de $\{1,2,\ldots,8\}$ que satisfazem: $\sigma(\sigma(j))=j$ para todo $j$; exatamente dois elementos são fixos; e, para cada elemento não fixo, $\sigma(j)-j$ é ímpar. Determine $|\mathcal S|$. Escolhendo-se $\sigma$ uniformemente em $\mathcal S$, calcule a probabilidade de $\sigma(1)=2$.

Resolução comentada

Resposta: $|\mathcal S|=96$; probabilidade $3/16$.

A condição $\sigma^2=\mathrm{id}$ permite apenas ciclos de tamanho um ou dois. Há dois pontos fixos e três pares trocados. Cada par deve conter um número par e um ímpar. Como há quatro números de cada paridade, os pontos fixos devem consistir em um par e um ímpar. Há $4\cdot4=16$ escolhas dos pontos fixos. Os três ímpares restantes são emparelhados com os três pares restantes por uma bijeção, de $3!=6$ maneiras. Portanto $|\mathcal S|=96$. Se $\sigma(1)=2$, o par trocado $\{1,2\}$ fica determinado. Dos três ímpares e três pares restantes, escolhem-se um fixo de cada paridade: $3\cdot3=9$ maneiras. Os outros quatro elementos formam dois pares por uma bijeção, com $2!=2$ possibilidades. Assim, há 18 permutações favoráveis e a probabilidade é $18/96=3/16$. Cada configuração construída determina uma única permutação, sem identificar permutações distintas por trocas de nomes.