Seja
o número de permutações de
. Sem usar que
, deduza a equação de recorrência
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 é: