Prove que D_{n+2}=(n+1) \cdot\left(D_{n+1}+D_{n}\right)
\begin{aligned} & D_{1}=0 \\\ & D_{2}=1 \end{aligned}

Passo 1

O que o enunciado pede: provar a fórmula de recorrência
D_{n+2}=(n+1)\cdot\bigl(D_{n+1}+D_{n}\bigr)
com as condições iniciais
D_{1}=0,\qquad D_{2}=1.
Informações dadas/assumidas: D_{m} denota o número de permutações de um conjunto com m 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 \{1\} sem ponto fixo ( D_{1}=0) e que há exatamente uma permutação sem ponto fixo de \{1,2\} (a transposição), logo D_{2}=1.

Passo 2

Estratégia (em palavras simples): vou contar de duas maneiras as permutações sem ponto fixo de um conjunto com m elementos e obter uma relação de recorrência. Para casar com a fórmula do enunciado, tomo m=n+2; primeiro trabalho para um m genérico (com m\ge3) e depois faço a substituição m=n+2.

Passo 3

Fixe m\ge3. Considere o conjunto \{1,2,\dots,m\} e conte quantas permutações \sigma desse conjunto satisfazem “nenhum ponto fixo” (ou seja, \sigma(i)\neq i para todo i). Esse número é D_{m}. Vou analisar essas permutações olhando para a imagem de 1, isto é, o valor \sigma(1).

Passo 4

A escolha de \sigma(1): como \sigma(1)\neq1, existem exatamente m-1 possibilidades para \sigma(1). Escreva k=\sigma(1), com k\in\{2,\dots,m\}. Para cada escolha fixa de k vamos contar quantas permutações sem ponto fixo têm \sigma(1)=k. Há duas possibilidades mutuamente exclusivas para cada tal permutação:
  • caso A: \sigma(k)=1;
  • caso B: \sigma(k)\neq1.
Vou contar separadamente quantas permutações correspondem a cada caso, para um k fixo, e depois multiplicar por m-1.

Passo 5

Contagem do caso A (quando \sigma(1)=k e \sigma(k)=1). Nesse caso os elementos 1 e k formam um par que se trocam entre si; os demais m-2 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 m-2 elementos. Portanto, para um k fixo há D_{m-2} permutações desse tipo.

Passo 6

Contagem do caso B (quando \sigma(1)=k e \sigma(k)\neq1). Para um k fixo, vou construir uma bijeção entre as permutações \sigma desse tipo e as permutações sem ponto fixo de um conjunto com m-1 elementos, o que mostra que o número é D_{m-1}.
Construa a bijeção explicitamente: dado \sigma com \sigma(1)=k e \sigma(k)\neq1, considere a restrição \tau de \sigma ao conjunto \{2,3,\dots,m\}; isto é, para todo i\in\{2,\dots,m\} defina \tau(i)=\sigma(i). Note que \tau é uma permutação de \{2,\dots,m\} que não tem ponto fixo, porque se existisse i com \tau(i)=i então \sigma(i)=i, contradizendo que \sigma não tem pontos fixos. Assim \tau é uma permutação sem ponto fixo de m-1 elementos. Isso fornece uma função que associa a cada \sigma tal \tau.
A inversa é simples: dado qualquer \tau permutação sem ponto fixo de \{2,\dots,m\}, definimos \sigma por \sigma(1)=k e \sigma(i)=\tau(i) para i\ge2. Como \tau não assume o valor 1 (o domínio e contradomínio são \{2,\dots,m\}), obtemos \sigma(k)=\tau(k)\neq1 e \sigma não tem pontos fixos. Portanto existe bijeção e, para um k fixo, o número de permutações do caso B é exatamente D_{m-1}.

Passo 7

Somando os dois casos para um k fixo, o número de permutações sem ponto fixo com \sigma(1)=k é
D_{m-1}+D_{m-2}.
Como havia m-1 escolhas possíveis para k, pelo princípio da contagem total temos
D_{m}=(m-1)\cdot\bigl(D_{m-1}+D_{m-2}\bigr).

Passo 8

Agora volte à notação do enunciado: substitua m=n+2. Então m-1=n+1 e a relação anterior fica exatamente
D_{n+2}=(n+1)\cdot\bigl(D_{n+1}+D_{n}\bigr),
com as condições iniciais dadas \;D_{1}=0,\;D_{2}=1. Isso conclui a prova da recorrência.

Resposta

D_{n+2}=(n+1)\cdot\bigl(D_{n+1}+D_{n}\bigr)

Exercícios relacionados