Encontre o número de inversões em cada um dos seguintes permutações de S=1,2,3,4,5.
45213

Passo 1

O enunciado pede o número de inversões na permutação
pi=(4,5,2,1,3) de S=1,2,3,4,5. Uma inversão é um par de índices (i,j) com i<j e pii>pij. Para resolver, vamos, para cada posição i, contar quantos elementos posteriores são menores que pii.

Passo 2

Aplicamos a definição: para cada i de 1 a 5, contamos o número de índices j>i tais que pij<pii.

Passo 3

Contagem por posição:
  • Para i=1, pi1=4. Os elementos posteriores são (5,2,1,3) e os menores que 4 são (2,1,3), total de 3 inversões.
  • Para i=2, pi2=5. Os posteriores são (2,1,3) e todos são menores que 5, total de 3 inversões.
  • Para i=3, pi3=2. Os posteriores são (1,3) e o único menor que 2 é 1, total de 1 inversão.
  • Para i=4, pi4=1. O único posterior é (3) e não há elemento menor que 1, total de 0 inversões.
  • Para i=5, não há posteriores, total de 0 inversões.

Passo 4

Somando as inversões de cada posição:
3 + 3 + 1 + 0 + 0 = 7

Resposta

O número de inversões na permutação 45213 é 7.

Exercícios relacionados