Prove que
Passo 1
O que o enunciado pede: provar a fórmula de recorrência
com as condições iniciais
Informações dadas/assumidas:
denota o número de permutações de um conjunto com
elementos que não deixam nenhum elemento fixo (ou seja, permutações sem pontos fixos). As condições iniciais significam que não há permutação de
sem ponto fixo (
) e que há exatamente uma permutação sem ponto fixo de
(a transposição), logo
.
Passo 2
Estratégia (em palavras simples): vou contar de duas maneiras as permutações sem ponto fixo de um conjunto com
elementos e obter uma relação de recorrência. Para casar com a fórmula do enunciado, tomo
; primeiro trabalho para um
genérico (com
) e depois faço a substituição
.
Passo 3
Fixe
. Considere o conjunto
e conte quantas permutações
desse conjunto satisfazem “nenhum ponto fixo” (ou seja,
para todo
). Esse número é
. Vou analisar essas permutações olhando para a imagem de
, isto é, o valor
.
Passo 4
A escolha de
: como
, existem exatamente
possibilidades para
. Escreva
, com
. Para cada escolha fixa de
vamos contar quantas permutações sem ponto fixo têm
. Há duas possibilidades mutuamente exclusivas para cada tal permutação:
- caso A:
; - caso B:
.
Vou contar separadamente quantas permutações correspondem a cada caso, para um
fixo, e depois multiplicar por
.
Passo 5
Contagem do caso A (quando
e
). Nesse caso os elementos
e
formam um par que se trocam entre si; os demais
elementos devem ser permutados de forma que nenhum fique fixo. Ou seja, a escolha das imagens dos demais é exatamente uma permutação sem ponto fixo de um conjunto de
elementos. Portanto, para um
fixo há
permutações desse tipo.
Passo 6
Contagem do caso B (quando
e
). Para um
fixo, vou construir uma bijeção entre as permutações
desse tipo e as permutações sem ponto fixo de um conjunto com
elementos, o que mostra que o número é
.
Construa a bijeção explicitamente: dado
com
e
, considere a restrição
de
ao conjunto
; isto é, para todo
defina
. Note que
é uma permutação de
que não tem ponto fixo, porque se existisse
com
então
, contradizendo que
não tem pontos fixos. Assim
é uma permutação sem ponto fixo de
elementos. Isso fornece uma função que associa a cada
tal
.
A inversa é simples: dado qualquer
permutação sem ponto fixo de
, definimos
por
e
para
. Como
não assume o valor
(o domínio e contradomínio são
), obtemos
e
não tem pontos fixos. Portanto existe bijeção e, para um
fixo, o número de permutações do caso B é exatamente
.
Passo 7
Somando os dois casos para um
fixo, o número de permutações sem ponto fixo com
é
Como havia
escolhas possíveis para
, pelo princípio da contagem total temos
Passo 8
Agora volte à notação do enunciado: substitua
. Então
e a relação anterior fica exatamente
com as condições iniciais dadas
. Isso conclui a prova da recorrência.