Encontre o número de inversões em cada um dos seguintes permutações de
.
45213
45213
Passo 1
O enunciado pede o número de inversões na permutação
de
. Uma inversão é um par de índices
com
e
. Para resolver, vamos, para cada posição
, contar quantos elementos posteriores são menores que
.
Passo 2
Aplicamos a definição: para cada
de 1 a 5, contamos o número de índices
tais que
.
Passo 3
Contagem por posição:
- Para
, . Os elementos posteriores são e os menores que 4 são , total de 3 inversões. - Para
, . Os posteriores são e todos são menores que 5, total de 3 inversões. - Para
, . Os posteriores são e o único menor que 2 é 1, total de 1 inversão. - Para
, . O único posterior é e não há elemento menor que 1, total de 0 inversões. - Para
, não há posteriores, total de 0 inversões.
Passo 4
Somando as inversões de cada posição:
Resposta
O número de inversões na permutação
é
.