Encontre o número de inversões em cada uma das seguintes permutações de 1,2,3,4,5
(c) (32541)

Passo 1

O enunciado pede para encontrar o número de inversões na permutação (3,2,5,4,1) do conjunto 1,2,3,4,5. O conteúdo aqui é inversões em permutações, e vamos usar a definição: uma inversão é um par de posições (i,j) com i<j tal que o elemento na posição i é maior que o da posição j.

Passo 2

Escrevemos a permutação como sequência de valores em cada posição:
a1=3, a2=2, a3=5, a4=4, a5=1
Para cada i de 1 até 4, contamos quantos j>i satisfazem ai>aj.

Passo 3

Contagem de inversões por posição:
  • Para i=1 ( a1=3): à direita temos 2,5,4,1. Os menores que 3 são 2 e 1, gerando 2 inversões.
  • Para i=2 ( a2=2): à direita temos 5,4,1. O único menor que 2 é 1, gerando 1 inversão.
  • Para i=3 ( a3=5): à direita temos 4,1. Ambos são menores que 5, gerando 2 inversões.
  • Para i=4 ( a4=4): à direita temos 1. Como 1 < 4, gera 1 inversão.
  • Para i=5 ( a5=1): não há posições à direita, então 0 inversões.

Passo 4

Somando todas as inversões:
2 + 1 + 2 + 1 + 0 = 6

Resposta

O número de inversões na permutação (3,2,5,4,1) é 6.

Exercícios de Livros Relacionados