Definizione

Dato un insieme finito A, con | A| = n, si chiama insieme delle permutazioni di A, e si indica con S_n , l'insieme delle trasformazioni di A, ossia

S_n = { s : A®A / s  biiettiva }

Scrivere | A| = n è la stessa cosa che scrivere | A | = |{1, 2, ... , n }|, ossia esiste una funzione biiettiva  f : A®{1, 2, ... , n }. Non è quindi restrittivo porre fin dall'inizio A = {1, 2, ... , n } ed è ciò che faremo.

Definizione

Dato l'insieme {1, 2, ... , n }, si chiama insieme delle permutazioni su n elementi, e si indica con S_n , l'insieme delle trasformazioni dell'insieme {1, 2, ... , n}, ossia

S_n = { s : {1, 2, ... , n}®{1, 2, ... , n}  /  s biiettiva }

Proposizione

L'insieme S_n delle permutazioni su n elementi ha cardinalità n!

| S_n |  = n!

Dim.

Essendo S_n = { s : {1, 2, ... , n}®{1, 2, ... , n} / s biiettiva },

il dominio di ognuna queste funzioni è finito ed uguale al codominio e quindi è anche

S_n = { s : {1, 2, ... , n}®{1, 2, ... , n} / s  iniettiva }

e abbiamo già dimostrato che se | A | = n, allora  |{ f ÎA^A /  f iniettiva} | = n!

Q.E.D.

Esempio

Dato l'insieme A={1, 2, 3 }, l'insieme S₃ = { s : A®A / s biiettiva } è costituito dalle seguenti 6 funzioni

Notazioni

Un elemento s ÎS_n è una funzione biiettiva s : {1, 2, ... , n}®{1, 2, ... , n}ed essendo il dominio di s  finito, possiamo, come visto nell'esempio precedente, scrivere esplicitamente la funzione:

Questa notazione è però scomoda nei calcoli ed è preferibile disporre su una riga gli elementi del dominio di s  e sulla riga sottostante i secondi elementi delle coppie ordinate che costituiscono il grafico di s

A questo punto eliminiamo le frecce e chiudiamo tra parentesi il tutto, ottenenendo così la notazione definitiva

Osservazione

• Da questa notazione si può ricostruire la funzione s . Dal fatto che ci sono n colonne sappiamo che s  ha per dominio e codominio  l'insieme {1, 2, ... , n}; il grafico della funzione è l'insieme {(1, s(1)), (2, s(2)) ... ,(n, s(n))}. Vedremo poi che sarà possibile semplificare ulteriormente la notazione, eliminando la necessità di indicare in ogni caso tutte e n le colonne

• Nella notazione l'ordine delle colonne è irrilevante, infatti per quanto appena detto il grafico della funzione è dato dall'insieme delle coppie ( i, s(i)) "iÎ{1, 2, ... , n} e quando si elencano gli elementi di un insieme l'ordine non conta

• Essendo s   una funzione biiettiva, nella seconda riga compaiono tutti e soli gli elementi della prima riga

Esempio

Definizione (prodotto di permutazioni)

Date due permutazioni su n elementi s, t ÎS_n , trattandosi di due funzioni con lo stesso dominio e codominio possiamo considerare i  prodotti operatori s _°t    e   t _°s

• Ricordando che il prodotto operatorio di due funzioni biiettive è una funzione biiettiva, possiamo concludere che il prodotto di due permutazioni è una permutazione: s, t ÎS_n s _°t , t _°s ÎS_n

• Il prodotto di permutazioni sarà eseguito da destra a sinistra:

(s _°t )( i ) = s (t ( i ))    e   (t _°s )( i ) = t (s ( i ))  "iÎ{1, 2, ... , n}

• Il prodotto di permutazioni non è in generale commutativo

Esempio

Come sono stati ottenuti questi risultati?

equivale a 

ossia

s(1)=3, s(2)=4, s(3)=1, s(4)=5, s(5)=2

Analogamente si vede che

t(1)=5, t(2)=1, t(3)=4, t(4)=3, t(5)=2

Risulta dunque

s (t ( 1 )) = s (5) = 2

t (s ( 1 )) = t (3) = 4

In pratica non c'è bisogno di tornare alla notazione funzionale, basta procedere nel modo indicato in figura

Definizione

Si chiama permutazione identica di S_n la permutazione definita da

id( i ) = i   "iÎ{1, 2, ... , n}

Con la  notazione introdotta in precedenza si ha

Si verifica immediatamente che

s _° id = id _°s = s     "sÎS_n

Definizione

Sia data una permutazione sÎS_n. Essendo s   una funzione biiettiva, esiste la permutazione inversa s ^-1caratterizzata da

s _°s ^-1 = s ^-1_°s = id

Come si trova la permutazione inversa di una permutazione?  Se è data

basta scambiare le due righe per ottenere

Se dà fastidio non avere gli elementi della prima riga in ordine si possono riordinare le colonne e ottenere

L'ultimo passaggio non è comunque indispensabile, dato che sappiamo che l'ordine delle colonne è irrilevante

Definizione (ciclo)

Consideriamo la permutazione

Per rendere la cosa più evidente possiamo riordinare le colonne della permutazione e ottenere così

Una permutazione di questo tipo si chiama per ovvi motivi ciclo. Per i cicli possiamo ulteriormente semplificare la notazione e scrivere s = (1 3 4 2 5). Questa scrittura significa che s(1)=3, s(3)=4, s(4)=2, s(2)=5 e s(5)=1.

Evidentemente risulta s  = (1 3 4 2 5) = (3 4 2 5 1) = (4 2 5 1 3) = (2 5 1 3 4) = (5 1 3 4 2)

Consideriamo adesso la permutazione

Notiamo che t(2)=2 e t(5)=5, ossia questi due elementi non vengono "spostati", rimangono fissi per effetto della permutazione.

Notiamo anche che t(1)=3, t(3)=4, t(4)=1 e quindi se penso nell'ordine gli elementi 1,3,4 disposti circolarmente, la permutazione manda ognuno di questi elementi nel successivo.

Tutto questo si può vedere meglio riordinando le colonne della permutazione per ottenere

Rispetto al caso precedente c'è però una differenza: nella scrittura (1 3 4) non compaiono gli elementi che non vengono spostati dalla permutazione e quindi questa scrittura ha un significato diverso a seconda dell' "ambiente" S_n che si sta considerando. Ad esempio in S₉ il simbolo (1 3 4) sta per

Dato un sottoinsieme {i₁, i₂, ... , i_h} di {1, 2, ... , n }, si chiama ciclo (i₁ i₂ ... i_h) la permutazione sÎS_n definita da

s(i₁) = i₂, s(i₂) = i₃ ,... ,s(i_h) = i₁     mentre     s(i) = i      "iÎ{1, 2, ... , n }\{i₁, i₂, ... , i_h}

ossia la permutazione che manda ogni elemento del ciclo nel successivo e l'ultimo nel primo e fissa tutti gli altri elementi

(1 6 5 2) = (6 5 2 1) = (5 2 1 6) = (2 1 6 5)

Definizione

Il numero di elementi di un ciclo si chiama lunghezza del ciclo e un ciclo di lunghezza h si dice h-ciclo

• Un h-ciclo si puo scrivere in h modi diversi: (2 5 3) = (5 3 2) = (3 2 5)

Proposizione

Se si fissano h numeri distinti, il numero di h-cicli che con essi si possono formare è

Dim.

Un h-ciclo si può scrivere in h modi diversi e quindi per contare gli h-cicli possiamo supporre che  inizino tutti con lo stesso elemento. I rimanenti h-1 elementi li possiamo permutare in (h-1)! modi diversi.

Q.E.D.

Proposizione

Il numero di h-cicli di S_n (con h=1,2, ...n) è

Dim.

Abbiamo appena dimostrato che se si fissano h numeri distinti con essi si possono formare (h-1)! cicli di lunghezza h.

Definizione (cicli di una permutazione)

Siano dati una permutazione sÎS_n    e aÎ{1, 2, ... , n}. Se considero la sua immagine s(a) e poi s(s(a)) = s ²(a) e così via, ad un certo punto, poichè il numero di elementi su cui opera s è finito, devo necessariamente riottenere uno degli elementi che si sono già presentati. Essendo n il numero di elementi su cui opera s, il primo elemento ripetuto si avrà al massimo dopo n passi e la cosa interessante è che si tratta proprio dell'elemento a da cui siamo partiti. Dimostriamolo.

Sia s ^k(a), con 1£ k £ n, il primo elemento che si ripete e supponiamo che sia s ^k(a) = s ^h(a) con 1£ h<k (quindis ^k(a) ¹ a)

Da s ^k(a) = s ^h(a) segue (dato che 0 £ h-1)

s (s ^{k -1}(a)) = s (s ^{h -1}(a))

da cui,  essendo s iniettiva,

s ^{k -1}(a) = s ^{h -1}(a)

ma questo non è possibile dato che per ipotesi s ^k(a) è il primo elemento che si ripete.

Notiamo che con questo procedimento abbiamo ottenuto un ciclo

(a  s(a)  s ²(a) ... s ^k -1(a))

Possiamo quindi dare la seguente definizione

Sia data una permutazione sÎS_n.  Preso un elemento aÎ{1, 2, ... , n}   e  indicato con k il minimo intero positivo per cui

s ^k(a) = a,  il ciclo

(a  s(a)  s ²(a) ... s ^k -1(a)) 

si chiama ciclo di a mediantes  e k si dice lunghezza del ciclo (in realtà considero la permutazione corrispondente, che fissa gli elementi fuori dal ciclo)

Evidentemente, siccome (a  s(a)  s ²(a) ... s ^k -1(a)) = (s(a)  s ²(a) ... s ^k -1(a) a) = ...= (s ^k -1(a)  a  s(a)  s ²(a) ... s ^k -2(a)), il ciclo di a è anche il ciclo di s ⁱ(a) con 1£ i £ h-1

Se il ciclodi a non ha lunghezza n, scegliamo un elemento che non ne fa parte, sia esso b, e ripetiamo il procedimento. Otteniamo il ciclo di b e sicuramente i due cicli non hanno elementi comuni:

{a, s(a), s ²(a), ... ,s ^k -1(a)}Ç {b, s(b), s ²(b), ... ,s ^h -1(b)}= f

Infatti se fosse s ⁱ(a) =s ^j(b) allora s ^{i -j}(a) = b, ma questo è assurdo perchè b per ipotesi non apparteneva al ciclo di a.

Se gli elementi dei due cicli non esauriscono {1, 2, ... , n}, possiamo andare avanti nello stesso modo e il procedimento, dato che gli elementi a disposizione sono in numero finito, deve avere fine.

In definitiva a partire da una permutazione sÎS_n abbiamo ottenuto un certi numero di cicli disgiunti. Quali e quanti cicli disgiunti si ottengono dipende dalla permutazione che si sta considerando. Il numero massimo di cicli disgiunti che si possono ottenere è evidentemente n e questo accade quando

dato che ogni ciclo in questo caso deve avere lunghezza 1.

Il numero minimo di cicli ottenibili è ovviamente 1. Quante sono le permutazioni di S_n che danno luogo a un unico ciclo di lunghezza n? Evidentemente sono proprio gli n-cicli e sappiamo che in S_n sono in numero di (n-1)!

Esempio

Data la seguente permutazione sÎS₉ ,

utilizzando il metodo visto, si trovano i cicli (1 8), (2 4 9), (3 5 7 6).

Si pone ora una questione. Data una permutazione abbiamo determinato i suoi cicli, ma si può tornare indietro? Noti che siano i cicli di una permutazione è possibile ricostruirla? Prima di rispondere a questa questione, definiamo il prodotto di cicli.

Proposizione

Un ciclo è una particolare permutazione e quindi, avendo già definito il prodotto di permutazioni, siamo in grado di calcolare il prodotto di cicli

qui si può introdurre il teorema sul numero di permutazione avente una certa struttura ciclica (definirla) definiamo poi la nuova notazione con i cicli dopo avere proposizione su permutazuione come prodotto dei suoi cicli

??? no perchè finora non ho imparato a ricavare i cicli dalle permutazioni e quindi non è detto che il prodotto di cue cicli sia ancora un ciclo secondo la nostra definizione!!!

Definizione (prodotto di cicli)

Un ciclo è una particolare permutazione e quindi, avendo già definito il prodotto di permutazioni, siamo in grado di calcolare il prodotto di cicli

Esempio

Siano s  = (1 3 4) e t  = (2 3) cicli di S₅. Il modo più ovvio per calcolare ad esempio s _°t è quello di scrivere per esteso

e quindi

Ma si poteva evitare tutto questo e procedere nel seguente modo.

Partendo dal primo elemento del ciclo t  = (2 3), si vede che t (2)=3. Ma per effetto del ciclo s   = (1 3 4)  risulta s (3)=4 e quindi s(t(2))=4.

Possiamo quindi cominciare a scrivere s i t = (2 4 ...

Per poter andare avanti, ci serve s(t(4))

Il 4 non compare in t, ovvero t(4)=4, e per effetto di s si ha s(t(4))=s(4)=1.

Possiamo quindi scrivere s i t = (2 4 1 ...

Ora ci serve s(t(1)) e siccome 1 non compare in t, ovvero t(1)=1, si ha s(t(1))=s(1)=3.

Possiamo quindi scrivere s i t = (2 4 1 3 ...

Ora ci serve s(t(3)). Risulta s(t(3)))=s(2) e siccome 2 non compare in s, ovvero s(2)=2, si ha s(t(3))=s(2)=2.

Avendo riottenuto l'elemento da cui siamo partiti, possiamo chiudere il ciclo e scrivere s _°t = (1 3 4)(2 3) = (2 4 1 3)

Siamo sicuri di aver finito? Certamente sì, dato che nel ciclo ottenuto compaiono tutti gli elementi presenti nei due cicli che abbiamo moltiplicato.

Nell' esempio siamo partiti da due cicli e abbiamo ottenuto un ciclo, ma questo non è sempre vero come risulta dal prossimo esempio.

Siano s  = (4 2 3 1) e t  = (5 2 1 7 3 6) cicli di S₇. (però questo lo posso scrivere se so già che una permutazione è prodotto dei suoi cicli??

5 va in 2 per effetto di t e 2 va in 3 per effetto di s e quindi 5 va in 3 per effetto di s _°t

6 va in 5 per effetto di t e 5 va in 5 per effetto di s e quindi 6 va in 5 per effetto di s _°t . Eravamo partiti da 5 e lo abbiamo ritrovato, quindi è ora di chiudere il ciclo. Abbiamo ottenuto il ciclo (5 3 6). Abbiamo finito? No, perchè non abbiamo ottenuto tutti gli elementi presenti nei due cicli s  e t.

Partiamo adesso da 2, che è uno degli elementi che non appartengono al ciclo trovato (5 3 6).

2 va in 1 per effetto di t e 1 va in 4 per effetto di s e quindi 2 va in 4 per effetto di s _°t

4 va in 4 per effetto di t e 4 va in 2 per effetto di s e quindi 4 va in 2 per effetto di s _°t. Eravamo partiti da 2 e lo abbiamo ritrovato, quindi è ora di chiudere il ciclo. Abbiamo ottenuto il ciclo (2 4). Abbiamo finito? No, perchè non abbiamo ottenuto tutti gli elementi presenti nei due cicli s  e t.

Partiamo adesso da 1, che è uno degli elementi che non appartengono ai cicli trovati (5 3 6) e (2 4).

1 va in 7 per effetto di t e 7 va in 7 per effetto di s e quindi 1 va in 7 per effetto di s _°t

7 va in 3 per effetto di t e 3 va in 1 per effetto di s e quindi 7 va in 1 per effetto di s _°t. Eravamo partiti da 1 e lo abbiamo ritrovato, quindi è ora di chiudere il ciclo. Abbiamo ottenuto il ciclo (1 7). Abbiamo finito? Sì, dato che nei cicli trovati (5 3 6), (2 4) e (1 7) sono presenti tutti gli elementi dei due cicli s  e t di cui stavamo calcolando il prodotto.

In definitiva si ha (4 2 3 1)(5 2 1 7 3 6) = (5 3 6)(2 4)(1 7)

E se considero il prodotto di due cicli che non hanno elementi comuni? In questo caso non devo proprio fare niente, perchè l'effetto di un ciclo non viene modificato dall'altro ciclo.

Definizione (inverso di un ciclo, inversa di un prodotto di trasposizioni)prodotto di permutazioni tramite prodotto dei cicli

Un ciclo è una particolare permutazione e quindi, avendo già definito l'inversa di una permutazione, siamo in grado di calcolare l'inversa di un ciclo

Non è però necessario scrivere esplicitamente la permutazione corrispondente al ciclo. L' inverso di un ciclo è ancora un ciclo e si ottiene scrivendone gli elementi in ordine inverso.

Data s = (2 5 3 1 4), si ha s ^-1 = (4 1 3 5 2). Si può anche scrivere s ^-1 = (2 4 1 3 5), cioè lasciare al suo posto il primo elemento del ciclo e invertendo l'ordine dei rimanenti.

Una trasposizione ha per inversa se stessa

Proposizione

Ogni ciclo si può scrivere come prodotto di trasposizioni

s _°t = (   1   3   4  )(  2    3  ) = (  2    4     1    3  )