permutazione di n numeri naturali

Ogni insieme formato con i primi n numeri naturali, essendo ciascun insieme diverso dagli altri solo per l’ordine di scrittura dei numeri, si dice permutazione degli n numeri dati.

La permutazione 1, 2, 3, ..., n si dice permutazione fondamentale.

In una generica permutazione i_1, i_2, ..., i_n dei primi n numeri naturali si dice che una coppia di elementi i_h, i_k presenta una inversione rispetto alla permutazione fondamentale quando per h<k si ha i_h>i_k; in altre parole si ha una inversione quando il numero maggiore precede il numero minore.

Il numero totale delle inversioni di una data permutazione si ha sommando le inversioni che ogni suo elemento ha con i successivi elementi ovvero contando il numero delle coppie i_h, i_k con h<k in cui il primo numero è maggiore del secondo.

Una permutazione dei primi n numeri naturali si dice di classe pari o di classe dispari rispetto alla permutazione fondamentale se risulta rispettivamente pari o dispari il numero totale delle inversioni.

Si dimostra che scambiando fra di loro due elementi di una permutazione questa cambia di classe ovvero da pari diventa dispari e viceversa.