4. Permutazioni di un insieme finito

4. Permutazioni di un insieme finito
Considerato un insieme finito non vuoto X, studieremo l’insieme S (X) delle permutazioni di X.
La prima osservazione da fare è che non importa il nome e la natura degli elementi di X, mentre è
ovviamente importante come gli elementi di X vengono ”mossi” dalle singole permutazioni. È lecito
quindi ed è prassi comune identificare tali elementi con i numeri naturali 1, 2, 3, ... . Se quindi X ha
cardinalità n ≥ 1, potremo identificare X con {1, 2, 3, ... , n} e denotare S (X) semplicemente con
S n.
Dunque S n denota l’insieme delle permutazioni di ogni insieme di n elementi. Per indicare le
permutazioni di S n vengono spesso usate lettere dell’alfabeto greco come σ, τ ecc. .
In base al Coroll. 1 di Cap. 1.2, S n ha cardinalità n!. Dobbiamo però stabilire la strategia da
adottare per poter scrivere tutte queste n! permutazioni.
Possiamo procedere come segue. Prima consideriamo tutte le permutazioni che trasformano 1 in
1. Si tratta di (n − 1)! permutazioni [quelle che permutano gli elementi dell’insieme {2, ... , n}].
Poi consideriamo quelle che trasformano 1 in 2. Si tratta ancora di (n − 1)! permutazioni [quelle
che permutano gli elementi dell’insieme {1, 3, ... , n}]. Procediamo in questo modo fino ad ottenere
n insiemi (a due a due disgiunti) formati ciascuno da (n − 1)! permutazioni, cioé complessivamente
(per il principio generalizzato della somma) n! permutazioni.
Ora cerchiamo un modo efficiente per indicare come una permutazione σ ∈ S n agisce sui singoli
elementi di X. Ovviamente, ponendo σi al posto di σ(i), possiamo scrivere

1 −→ σ1



 2 −→ σ
2
σ:




n −→ σn.
Ma per economia di spazio è preferibile scrivere la stessa σ nella forma
1 2 ... n
σ=
,
σ1 σ2 ... σn
convenendo quindi che ogni elemento della prima riga sia mandato da σ in quello disposto esattamente
al di sotto. Ad esempio la permutazione identica 1 X di S 4 si scrive nella forma
1 2 3 4
.
1 2 3 4
Nel seguito del paragrafo troveremo però un modo ”più economico” (ad una sola riga) per scrivere le
permutazioni.
Due permutazioni possono ovviamente essere ”composte”, secondo l’operazione di prodotto operatorio (o composizione). Se quindi σ, τ ∈ S n, allora
1
2 ... n
τ ◦σ = τ
.
τ
... τ
σ1
σ2
σn
2 3 4
1 2 3 4
, τ=
∈ S 4, allora
3 4 1
2 4 1 3
1 2 3 4
1 2 3 4
1 2 3 4
◦
τ σ=
◦
=
.
2 3 4 1
2 4 1 3
4 1 3 2
Se ad esempio σ =
1
2
Osserviamo poi che, nel calcolare τ ◦ σ, prima agisce σ e poi τ . Quindi, come sopra evidenziato,
occorre seguire ”a ritroso” l’azione di τ ◦ σ sugli elementi 1, 2, ... , n. Poiché ciò è in contrasto con
22
G. CAMPANELLA
APPUNTI DI ALGEBRA PER INFORMATICA
la nostra abitudine di leggere da sinistra verso destra, scriveremo σ τ al posto di τ ◦ σ, per cui
στ =
1 2 3 4
2 3 4 1
1 2 3 4
2 4 1 3
=
1 2 3 4
4 1 3 2
= τ ◦ σ.
Dunque abbiamo convenuto di definire
σ τ = τ ◦ σ, ∀ σ, τ ∈ S n.
Tale convenzione non è generalmente adottata nei testi matematici che si occupano di questi argomenti.
Molti preferiscono mantenerere la notazione con il prodotto operatorio e leggere a ritroso l’azione della
composizione sui singoli elementi.
Sappiamo che ogni permutazione σ, in quanto applicazione
−1
osservando che, se
Assegnata σ possiamo subito ottenere σ
−1
Dunque per determinare σ basta associare ad ogni elemento
basso verso l’alto. Ad esempio, se
1 2 3 4
1
−1
σ=
, allora σ =
2 3 4 1
4
[Si verifichi che σ
−1
σ = 1X = σ σ
−1
−1
biiettiva, è dotata di inversa σ .
−1
σ : i → σi , allora σ : σi → i.
la sua immagine guardando σ dal
2
1
3
2
4
.
3
].
Si osserva subito che, ∀ σ ∈ S n, risulta:
σ 1 X = σ = 1 X σ.
Dunque la permutazione identica 1 X funge da ”elemento
posizione. Un’altro fatto da osservare è che in generale
permutazioni non è in generale un’operazione commutativa.
1 2 3
1
σ=
, τ=
2 1 3
1
si ha:
στ =
1
3
2
1
3
2
, τσ=
neutro” rispetto all’operazione di comσ τ = τ σ, cioè che la composizione di
Ad esempio scelti in S 3:
2 3
,
3 2
1
2
2
3
3
.
1
Per semplificare le notazioni porremo nel seguito, ∀ n ≥ 1:
σ := σ·
... ·σ
, σ := 1 X , σ
n
0
−n
−1 n
:= (σ ) .
n fattori
Ne segue che, ∀ n, m ∈ Z : σ
n+m
=σ ·σ .
n
m
Come promesso, presentiamo ora un modo più economico di scrivere le permutazioni. Abbiamo
bisogno di introdurre certe permutazioni speciali, dette cicli.
Definizione 1. Sia σ ∈ S n e sia k un intero tale che 1 ≤ k ≤ n. La permutazione σ è detta
ciclo o k-ciclo o ciclo di lunghezza k se ∃ c1, c2, ... , ck ∈ X, a due a due distinti, tali che
σ(c1) = c2, σ(c2) = c3, .... , σ(ck−1) = ck , σ(ck) = c1
e
σ(t) = t, ∀ t ∈ X, t = c1, c2, ... , ck .
Tale k-ciclo σ è usualmente denotato (c1, c2, ... , ck), ovvero, più brevemente, (c1 c2 ... ck). I 2-cicli
vengono anche chiamati trasposizioni.
Diremo poi, per brevità, che i naturali c1, ... , ck sono ”elementi” del ciclo (c1 c2 ... ck). Infine, due
cicli di S n, di lunghezza ≥ 2, sono detti cicli disgiunti se non hanno elementi in comune.
Ad esempio, considerata in S 5 la permutazione
1 2 3
σ=
2 3 4
si osserva subito che essa è il 5-ciclo (1 2 3 4 5).
4
5
5
,
1
Tale ciclo può essere anche scritto in altre forme:
CAP. 1.4
PERMUTAZIONI DI UN INSIEME FINITO
23
infatti (1 2 3 4 5) = (2 3 4 5 1) = (3 4 5 1 2) = (4 5 1 2 3) = (5 1 2 3 4).
Più in generale possiamo dire che, se 2 ≤ k ≤ n, ogni k-ciclo si scrive in k modi diversi [basta
iniziarne la scrittura da uno qualsiasi dei suoi k elementi e scriverli tutti, mantenendone l’ordine, con
una sorta di ”rotazione oraria”].
Di 1-cicli ne esiste uno solo e coincide con la permutazione identica 1 X . Infatti, ∀ t ∈ X, l’1-ciclo
(t) fissa ogni elemento di X. Ovviamente (t) = (s), ∀ s ∈ X.
È facile, assegnato un ciclo di S n, scriverlo in forma di permutazione. Ad esempio, considerato il
4-ciclo σ = (3 5 4 1) ∈ S 6, risulta:
1 2 3 4 5 6
σ=
3
5 1 4
e quindi, scrivendo anche le immagini degli altri due elementi (che restano fissi), si ottiene
1 2 3 4 5 6
σ=
.
3 2 5 1 4 6
Osservazione 1. (i) Tutte le permutazioni di S 1, S 2, S 3 sono cicli. Infatti:
S 1 = {(1)},
S 2 = {(1), (1 2)},
S 3 = {(1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2)}.
Si noti che i cicli scritti sopra vanno ovviamente interpretati nel corrispondente
Ad esempio
S n. 1 2
1 2 3
(1 2) ∈ S 2 è la permutazione
, mentre (1 2) ∈ S 3 è la permutazione
.
2 1
2 1 3
(ii) Non ogni permutazione σ ∈ S n è un ciclo. Ad esempio la permutazione
1 2 3 4
σ=
∈ S4
2 1 4 3
non è un ciclo. Si vede subito però che essa contiene due cicli disgiunti, e cioè le due trasposizioni
(1 2) e (3 4). In effetti, essa è proprio il prodotto di queste due trasposizioni. Infatti
1 2 3 4
1 2 3 4
1 2 3 4
(1 2) (3 4) =
=
= σ.
2 1 3 4
1 2 4 3
2 1 4 3
Tale fatto non è casuale, come messo in luce nella successiva Prop.1.
(iii) Come si ottengono i cicli (a due a due disgiunti) di una permutazione non identica σ ∈ S n ? Si
apra un ciclo con l’elemento 1 ∈ X e si considerino successivamente gli elementi
2
3
σ(1), σ(σ(1)) = σ (1), σ(σ(σ(1))) = σ (1), ... .
Si continui con questa procedura finché tali elementi sono = 1; appena si incontrerà l’elemento 1 si
interrompa il procedimento, e si otterrà cosı̀ il ciclo
γ1 := 1, σ(1), σ(σ(1)), σ(σ(σ(1))), ...
Si passi ora ad aprire un altro ciclo a partire dal più piccolo naturale di X rimasto estraneo al ciclo
γ1. Si ottiene nello stesso modo un nuovo ciclo γ2, disgiunto dal precedente. Dopo un numero
finito di passi, tutti gli elementi di X si troveranno all’interno di un (unico) ciclo ed il procedimento
termina. Ad esempio, se
1 2 3 4 5 6 7
σ=
∈ S 7,
2 1 3 4 7 5 6
si ottengono i cicli (1 2), (3), (4), (5 7 6). Si può verificare, eseguendo il prodotto di tali cicli, che
(1 2) (3) (4) (5 7 6) = (1 2) (5 7 6) = σ.
[si noti che gli 1-cicli (3), (4) possono essere omessi dal prodotto, in quanto coincidono con 1 X ].
Dunque σ è prodotto dei suoi cicli disgiunti di lunghezza ≥ 2.
Proposizione 1.
lunghezza ≥ 2.
Ogni permutazione non identica σ ∈ S n è prodotto dei suoi cicli disgiunti di
Dim. Sia σ = 1X e siano γ1, ... , γt tutti i cicli (a due a due disgiunti) di σ di lunghezza ≥ 2.
Bisogna verificare che σ = γ1 ... γt , cioè che, ∀ x ∈ X, risulta σ(x) = (γ1 ... γt)(x).
24
G. CAMPANELLA
APPUNTI DI ALGEBRA PER INFORMATICA
Se x non appartiene ad alcuno dei cicli γi , allora σ(x) = x = (γ1 ... γt)(x).
l’unico k-ciclo di σ contenente x. Allora:
k−1
2
γi = x, σ(x), σ (x), ... , σ (x) .
Altrimenti, sia γi
Si ha:
(γ1 ... γt)(x) = (γt ◦ ... ◦ γ1)(x) = (γt ◦ ... ◦ γi)(x) = (γt ◦ ... ◦ γi+1)(σ(x)) = ... = σ(x),
in quanto x non appartiene ai cicli γ1, ... , γi−1 e σ(x) non appartiene ai cicli γi+1, ... , γt (in quanto
appartene a γi ). Dunque è provato che σ = γ1 ... γt.
Osservazione 2. (i) Due cicli disgiunti di S n commutano. Siano infatti γ1 = (c1 c2 ... ck) e
γ2 = (d1 d2 ... dh) due cicli disgiunti di S n. Si tratta di verificare che
(γ1γ2)(x) = (γ2γ1)(x), ∀ x ∈ X.
Se x ∈ X − {c1, ... , ck, d1, ... , dh}, allora γ1(x) = γ2(x) = x e dunque (γ1γ2)(x) = (γ2γ1)(x) = x. Se
invece x ∈ {c1, ... , ck}, si ha:
(γ1γ2)(x) = (γ2 ◦ γ1)(x) = γ2(γ1(x)) = γ1(x) [perché γ1(x) ∈ {d1, ... , dh}],
(γ2γ1)(x) = (γ1 ◦ γ2)(x) = γ1(γ2(x)) = γ1(x) [perché x ∈ {d1, ... , dh}].
Se infine x ∈ {d1, ... , dh}, si ottiene ancora, con analoghe considerazioni, che (γ1γ2)(x) = (γ2γ1)(x).
(ii) Ogni k-ciclo (k ≥ 2) è sempre esprimibile come prodotto di k − 1 trasposizioni non disgiunte.
Infatti si verifica con calcolo diretto che:
(c1 c2 ... ck) = (c1 c2)(c1 c3) ... (c1 ck).
Ne segue che ogni permutazione σ è esprimibile come prodotto di sole trasposizioni (a due a due
non disgiunte).
(iii) Si verifica con calcolo diretto che l’inverso del k-ciclo (c1 c2 ... ck−1 ck) è il k-ciclo (ck ck−1 ... c2 c1).
Infatti
(c1 c2 ... ck−1 ck)(ck ck−1 ... c2 c1) = (c1)(c2) ... (ck−1)(ck) = 1 X .
Dalla Prop.1 e dall’Osserv.2(ii) segue che ogni permutazione è rappresentabile come prodotto
di trasposizioni (a due a due non necessariamente disgiunte). Ma tale rappresentazione non è unica.
Ad esempio il 4-ciclo σ = (1 4 2 3) ∈ S 4 si può indifferentemente scrivere nella forma (1 2)(1 3)(2 4),
ovvero (1 4)(1 2)(1 3), ovvero (1 2)(2 3)(1 3)(1 2)(2 4), ed in tanti altri modi.
C’è però una proprietà significativa da sottolineare [per la dimostrazione, che non è immediata, si rinvia ad esempio a www.mat.uniroma1.it/people/campanella, Appunti di Algebra 1,
Cap. 4.3, pag. 153]. Eccola.
Proposizione 2. Assegnata una permutazione σ ∈ S n, il numero delle trasposizioni di cui σ è
prodotto è sempre pari o sempre dispari.
Ad esempio abbiamo appena visto che la permutazione σ = (1 4 2 3) ∈ S 4 è prodotto di tre oppure
di cinque trasposizioni. La precedente proposizione ci dice che non avrebbe potuto essere prodotto di
un numero pari di trasposizioni. Si noti poi che la permutazione identica 1 X ∈ S n (n ≥ 2) è prodotto
di un numero pari di trasposizioni. Infatti ad esempio 1 X = (1 2)(1 2).
Definizione 2. Una permutazione σ ∈ S n è detta di classe pari se è esprimibile come prodotto di
un numero pari di trasposizioni. Altrimenti è detta di classe dispari. L’insieme delle permutazioni
di classe pari è denotato A n.
Osservazione 3. (i) Se una permutazione σ ∈ S n è prodotto di t cicli γ1, ... , γt , aventi lunghezze
t
(ki − 1) [infatti γi è
rispettivamente k1, ... , kt , la parità di σ è data dalla parità del numero
prodotto di ki − 1 trasposizioni (cfr. Osserv. 2(ii))].
i=1
CAP. 1.4
PERMUTAZIONI DI UN INSIEME FINITO
25
1 2
...
n
∈ S n, se ne possa
σ1 σ2 ... σn
calcolare la parità direttamente, senza cioè ricorrere alla sua scrittura come prodotto di cicli.
(ii) Ci chiediamo come, assegnata una permutazione σ =
Per ogni k = 1, ... n, si pone
I(σ, k) := σj : j > k e σj < σk .
[Tale numero è detto k-simo numero delle inversioni di σ; si tratta della cardinalità dei σj minori
di σk che seguono σk (nella seconda riga di σ)]. Ovviamente I(σ, n) = 0. Si pone poi:
I(σ) := I(σ, 1) + .... + I(σ, n − 1)
[detto numero delle inversioni di σ ]. Si potrebbe verificare che:
Ad esempio, sia σ =
σ è di classe pari ⇐⇒ I(σ) è un numero pari.
1 2 3 4 5 6
∈ S 6. Si ha:
6 1 5 3 4 2
I(σ, 1) = 5, I(σ, 2) = 0, I(σ, 3) = 3, I(σ, 4) = 1, I(σ, 5) = 1,
e quindi I(σ) = 5 + 0 + 3 + 1 + 1 = 10. Pertanto σ è di classe pari. In effetti risulta:
σ = (1 6 2)(3 5 4) = (1 6)(1 2)(3 5)(3 4).
Vogliamo ora elencare le 24 permutazioni di S 4, scrivendole direttamente come prodotto dei loro
cicli disgiunti.
È conveniente suddividerle rispetto a quella che viene chiamata struttura ciclica. Tra le permutazioni di S 4 ci potranno essere [oltre alla permutazione identica (1))] 2-cicli, 3-cicli, 4-cicli e coppie
di 2-cicli disgiunti. Si ottengono le 24 permutazioni:
(1)
[unico 1-ciclo (classe pari)];
(1 2), (1 3), (1 4), (2 3), (2 4), (3 4)
(1 2)(3 4), (1 3)(2 4), (1 4)(2 3)
(1 2 3), (1 2 4), (1 3 4), (2 3 4)
(1 3 2), (1 4 2), (1 4 3), (2 4 3)
[2-cicli (classe dispari)];
[coppie di 2-cicli disgiunti (classe pari)];
[3-cicli (classe pari)];
(1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2)
[4-cicli (classe dispari)].
[Si noti che per ottenere tutti i 4-cicli abbiamo fissato come primo elemento 1 e poi permutato gli
altri tre elementi; per elencare i 3-cicli abbiamo scritto sulla prima riga tutte le sequenze crescenti
di tre interi (da 1 a 4) e sotto, in corrispondenza di ciascun 3-ciclo, il suo inverso].
Osservazione 4. Il lettore attento avrà probabilmente osservato che in S 4 esistono 12 permutazioni
di classe pari ed altrettante di classe dispari. Si sarà quindi chiesto se tale uguaglianza è un fatto
casuale o no.
La risposta è che non si tratta di un fatto casuale. Dimostriamolo.
Se moltiplichiamo una permutazione σ per un 2-ciclo ne cambiamo la parità, cioè trasformiamo
una permutazione pari in una dispari (e viceversa). Consideriamo allora la seguente applicazione
ϕ : S n → S n tale che ϕ(σ) = (1 2) σ, ∀ σ ∈ S n.
L’applicazione
ϕ è biiettiva. Infatti ϕ ◦ ϕ è l’applicazione identica su S n [essendo (ϕ ◦ ϕ)(σ) =
(1 2) (1 2) σ = σ] e dunque ϕ ammette inversa (se stessa).
An delle
Poiché ϕ trasforma l’insieme A n delle permutazioni pari nell’insieme complementare S n −A
An| = |S
S n − A n|. Il numero delle permutazioni pari (e
permutazioni dispari (e viceversa), allora |A
26
delle dispari) è
G. CAMPANELLA
APPUNTI DI ALGEBRA PER INFORMATICA
n!
2 .
ESERCIZI PROPOSTI
1.4.1. Sia σ = (1 3 2 4)(5 6) ∈ S 6. Determinare il minimo intero k ≥ 1 tale che σ k = 1 X .
1.4.2. Stesso esercizio con σ = (1 3 2)(4 5) ∈ S 5.
1.4.3. Scrivere tutte le permutazioni di S 5 che contengono il ciclo (1 2).
1.4.4. Assegnate le permutazioni σ1 = (1 3 4 2), σ2 = (2 5)(3 4) ∈ S 5, determinare la permutazione
τ ∈ S 5 tale che σ2 = τ σ1.
1.4.5. Scrivere la ”tavola pitagorica” di S 3, cioè la tavola 6 × 6 formata da tutti i prodotti σi σj ,
al variare di σi , σj in S 3.
1.4.6. (i) Verificare che se σ ∈ S n è una permutazione di classe dispari, non esiste alcuna permu2
tazione α ∈ S n tale che α = σ.
2
(ii) Determinare α ∈ S 6 tale che α = (1 2 3)( 4 5 6).
(iii) Spiegare perché non esiste α ∈ S 6 tale che α = (1 2)(3 4 5 6).
2
1.4.7. (i) Verificare che ∀ σ ∈ S n ∃ k ∈ N , k ≥ 1 tale che σ k = 1 X .
(ii) Verificare che ∀ σ, τ ∈ S n l’equazione (di primo grado) σX = τ ammette una ed una sola
soluzione (in S n).
1.4.8. Determinare per quali σ ∈ S 4 l’equazione X = σ è risolubile.
2
1.4.9. In S 5 sono assegnati un 3-ciclo σ ed un 2-ciclo τ , disgiunti tra loro. Sia H l’insieme formato
dalle permutazioni di S 5 ottenibili come prodotti finiti di σ e di τ . Determinare le permutazioni di
H e verificare se H è un sottogruppo di S 5.
1.4.10. (i) Quanti sono i 3-cicli di S 6 ?
(ii) Quante sono le permutazioni di S 6 che sono prodotto di due 3-cicli disgiunti ?