Hoán vị chẵn và lẻ

Hoán vị chẵn và lẻ. 
Ta cũng có thể biểu diễn mỗi hoán vị dưới dạng một hàm song ánh như sau. Cho X là tập gồm n phần tử. Một hoán vị của X là
một hàm song ánh σ: X → X. Ví dụ
 (a b c d e)
σ =
 (c d a e b)

Ký hiệu X = {x1, x2,..., xn } và Sn là tập tất cả các hoán vị của X.
Tập Sn chứa các hoán vị được biểu diễn dưới dạng các dãy:
σ = <σ(x 1), σ(x 2),..., σ(x n)>
Chú ý rằng ∀ i, j: i 6= j ⇔ x i != x j. Như vậy |Sn| = n!.
Với mỗi hoán vị σ, ta gọi cặp (x i, x j) là một nghịch thế của σ nếu
x i < x j nhưng σ (x i) > σ (x j).
Mỗi hoán vị đều nằm ở một trong hai lớp kích thước bằng nhau là lớp các hoán vị chẵn và lớp các hoán vị lẻ.
Tính chẵn lẻ của ột hoán vị σ của X là tính chẵn lẻ của số nghịch thế của σ:
Nếu số cặp (xi, xj) trong đó xi < xj và σ (xi) > σ (xj) là một số
chẵn thì σ là hoán vị chẵn;
Ngược lại σ là hoán vị lẻ.

Tham khảo