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

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm

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[sửa | sửa mã nguồn]