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

Passo 1

O enunciado pede para encontrar o número de inversões na permutação (1,3,5,4,2) de S=1,2,3,4,5. 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 (a1,a2,dots,an), dizemos que o par de posições (i,j) com i<j é uma inversão se, e somente se,
ai > aj

Passo 3

Para a permutação (1,3,5,4,2) vamos checar cada índice i e contar quantos elementos posteriores são menores que ai.
i =1: a1=1. Elementos posteriores são 3,5,4,2. Como 1 é menor que todos, não gera inversão.
i =2: a2=3. Elementos posteriores são 5,4,2. Apenas 3>2 forma uma inversão.
i =3: a3=5. Elementos posteriores são 4,2. Aqui 5>4 e 5>2 geram duas inversões.
i =4: a4=4. Elemento posterior é 2. Como 4>2, mais uma inversão.
i =5: a5=2. Não há elementos posteriores.
Somando as inversões: 1+2+1 = 4.

Resposta

O número de inversões na permutação 13542 é 4.

Exercícios relacionados