Seja Pn o número de permutações de {1, ..., n}. Sem usar que Pn = n!, deduza a equação de recorrência
P_n = n * P_{n-1}, ∀ n ≥ 2; P_{1} = 1

Passo 1

Vamos entender o que o exercício está pedindo. Temos um conjunto com os números de 1 até e queremos descobrir quantas maneiras diferentes podemos organizar (permutar) esses números. O conteúdo que vamos usar aqui é o conceito de permutação e a ideia de recorrência, que nos ajuda a encontrar uma relação entre o número de permutações para elementos e para elementos.

Passo 2

Primeiro, pense em quantas permutações existem para um conjunto com apenas 1 elemento, que é . Como só há um elemento, só há uma maneira de organizá-lo. Então, temos:

Passo 3

Agora, vamos considerar um conjunto com elementos. Para encontrar , pense que você já sabe quantas permutações existem para elementos, que é .

Passo 4

Para cada uma dessas permutações, você pode inserir o -ésimo elemento em qualquer uma das posições disponíveis. Por exemplo, se e você tem uma permutação de 2 elementos, você pode inserir o terceiro número em 3 lugares diferentes.

Passo 5

Então, para cada permutação de elementos, há exatamente maneiras de adicionar o elemento extra. Isso significa que o número total de permutações é vezes .

Resposta

A equação de recorrência é:

Exercícios relacionados