Considere uma sequência de letras, por exemplo, ABC e uma de suas permutações, por exemplo, BCA.

Dizemos que um par dessas letras forma uma inversão na permutação em relação à sequência original, se esse par de letras aparece na permutação na ordem inversa daquela em que aparece na sequência original. Por exemplo, o par de letras BA na permutação está na ordem inversa da que aparece na sequência original, AB, e, portanto, forma uma inversão. Já o par BC está, na permutação, na mesma ordem em que aparece na sequência original e, portanto, não forma uma inversão.

Considere agora a sequência ABCDE.

a) Quantas inversões há na permutação CADBE em relação à sequência original?

b) Qual a permutação da sequência original que apresenta o número máximo de inversões? Qual é esse número máximo?

a) Para a permutação CADBE, tem-se os seguintes casos:

começar estilo tamanho matemático 14px tabela linha com célula com CA espaço ✔ ︎ fim da célula célula com AD espaço reto X fim da célula célula com DB espaço ✔ ︎ fim da célula célula com BE espaço reto X fim da célula linha com célula com CD espaço reto X espaço espaço espaço fim da célula célula com AB espaço reto X fim da célula célula com DE espaço reto X espaço espaço espaço fim da célula blank linha com célula com CB espaço ✔ ︎ fim da célula célula com AE espaço reto X fim da célula blank blank linha com célula com CE espaço reto X espaço espaço espaço fim da célula blank blank blank fim da tabela fim do estilo

Logo, nesse caso há 3 inversões.

b) O número máximo de inversões ocorre quando o anagrama está completamente invertido em relação à ordem original ABCDE, ou seja, na permutação EDCBA.

Nesse caso, cada letra aparece antes de todas as que viriam depois na ordem original, o que configura uma inversão em todas essas comparações

começar estilo tamanho matemático 14px tabela linha com célula com ED espaço ✔ ︎ fim da célula célula com DC espaço ✔ ︎ fim da célula célula com CB espaço ✔ ︎ fim da célula célula com BA espaço ✔ ︎ fim da célula linha com célula com EC espaço ✔ ︎ fim da célula célula com DB espaço ✔ ︎ fim da célula célula com CA espaço ✔ ︎ fim da célula blank linha com célula com EB espaço ✔ ︎ fim da célula célula com DA espaço ✔ ︎ fim da célula blank blank linha com célula com EA espaço ✔ ︎ fim da célula blank blank blank fim da tabela fim do estilo

Portanto, a permutação EDCBA possui o número máximo de inversões: 10.