Quantas inversões tem a permutação ( n n - 1 ... 2 1 ) dos números 1 , 2 , ... , n - 1 , n ?

Passo 1

O primeiro passo é relembrar a definição de inversão, o que você já fez através da teoria. Só pra te ajudar, é a definição 3.3.1 do livro. Show de bola?!

Passo 2

Agora vamos lá!! Observe que essa permutação é uma sequência descrescente, isto é, dado um termo, todos os termos posteriores são menores que ele. Beleza?!

Daí fica fácil saber o número de inversões, porque se você analisar o elemento k , existirão k - 1 inteiros que ele precede e que são menores que ele. Mas isso é o número de inversões, pela definição.

Agora, basta a gente somar isso de n até 2:

S = n - 1 + n - 2 + ... + 1

Beleza?! Mas o que é essa soma?

Essa soma é uma P.A. de razão 1 e primeiro termo 1. Sabemos então que a soma é dada por:

S = ((n - 1) (n - 1 + 1))/(2) = (n^2 - n)/(2)

Show de bola?!

Resposta

(n^2 - n)/(2)

Ver Outros Exercícios desse livro

Exercícios de Livros Relacionados