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

Passo 1

O enunciado pede o número de inversões na permutação 4,2,1,3,5 do conjunto S=1,2,3,4,5. Vamos usar o conceito de inversão em permutações.

Passo 2

Definição de inversão: numa permutação (a1,a2,dots,an) dizemos que o par (i,j) com i<j é uma inversão se e somente se ai>aj. O número de inversões é a quantidade total desses pares.

Passo 3

Analisando posição a posição na permutação (4,2,1,3,5):
  • Para i=1: a1=4 forma inversões com a2=2, a3=1 e a4=3, mas não com a5=5. Total: 3 inversões.
  • Para i=2: a2=2 forma inversão apenas com a3=1. Total: 1 inversão.
  • Para i=3: a3=1 não forma inversões com a4=3 nem com a5=5. Total: 0.
  • Para i=4: a4=3 não forma inversão com a5=5. Total: 0.
  • Para i=5: não há termos à frente.

Passo 4

Somando as inversões encontradas em cada passo:
3 + 1 + 0 + 0 = 4

Resposta

4

Exercícios relacionados