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

Passo 1

O enunciado fornece a permutação (5,2,1,3,4) de S=1,2,3,4,5 e pede o número de inversões. Uma inversão é um par de índices (i,j) com i<j e pi>pj.

Passo 2

Para contar as inversões, vamos olhar cada posição i e verificar quantos elementos à direita são menores que pi.

Passo 3

Para p1=5 há os pares (1,2),(1,3),(1,4),(1,5), pois 2,1,3,4<5. Total de inversões geradas por p1: 4.

Passo 4

Para p2=2 há o par (2,3) com 1<2. Já para p3=1, p4=3 e p5=4 não há nenhum elemento menor à direita. Total adicional: 1.

Passo 5

Somando todas as inversões, temos 4+1=5.

Resposta

5

Exercícios relacionados