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ẻ.