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ụσ =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ếux 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ẻ.