Encontre o número de inversões em cada um dos seguintes permutações de
.
13542
13542
Passo 1
O enunciado pede para encontrar o número de inversões na permutação
de
. O conteúdo aqui é permutações e número de inversões, e vamos usar a definição de inversão para resolver.
Passo 2
Definição de inversão: dada uma permutação
, dizemos que o par de posições
com
é uma inversão se, e somente se,
Passo 3
Para a permutação
vamos checar cada índice
e contar quantos elementos posteriores são menores que
.
i
:
. Elementos posteriores são
. Como
é menor que todos, não gera inversão.
i :
. Elementos posteriores são
. Apenas
forma uma inversão.
i :
. Elementos posteriores são
. Aqui
e
geram duas inversões.
i :
. Elemento posterior é
. Como
, mais uma inversão.
i :
. Não há elementos posteriores.
i
i
i
i
Somando as inversões:
.
Resposta
O número de inversões na permutação
é
.