Teorema 19 Ogni permutazione di , , è prodotto di cicli a due a due disgiunti

Teorema 21 Ogni permutazione di , , è prodotto di cicli a due a due disgiunti. La rappresentazione di come prodotto di cicli a due a due disgiunti è unica a meno dell’ordine.

Dimostrazione Siano le orbite di con più di un elemento (ne esiste almeno una essendo ).

Per ogni orbita , definiamo il ciclo

In questo modo si costruiscono cicli a due a due disgiunti essendo le corrispondenti orbite a due a due disgiunte (osservazione 16).

Osserviamo inoltre che ogni agisce sugli elementi che vi compaiono allo stesso modo di . Allora essendo tali cicli a due a due disgiunti il prodotto ha sugli elementi di lo stesso effetto di (gli elementi che non compaiono in nessun ciclo sono lasciati fissi da entrambe le permutazioni e ).

Abbiamo così provato che

Per provare l’unicità della fattorizzazione, a meno dell’ordine, dobbiamo mostrare che se

dove e sono cicli a due a due disgiunti, allora e, riordinando eventualmente i , si ha .

Dimostriamo innanzitutto che se con cicli a due a due disgiunti, esiste una corrispondenza biunivoca tra e le orbite di con più di un elemento.

Sia . Se non compare in nessuno dei allora e l’orbita di è .

Supponiamo ora che compaia in uno dei cicli (questo è unico essendo i cicli disgiunti); tale ciclo sia e sia (non si perde la generalità del ragionamento).

Ogni , con , lascia fisso e quindi si ha:

Questo prova che l’orbita di è .

Riprendiamo ora la doppia rappresentazione di : da quanto appena provato segue che i cicli , come i cicli , sono in corrispondenza biunivoca con le orbite di , e quindi .

Eventualmente permutando i cicli , si può supporre che e corrispondono alla stessa orbita: se e , si ha da cui segue subito . Inoltre se supponiamo, ad esempio, che , si ha