Sự hoán đổi

Trong toán học, đặc biệt là trong đại số trừu tượng và các lĩnh vực liên quan, một hoán vị là một ánh xạ từ một tập hợp hữu hạn X tới chính nó.

Trong lý thuyết tổ hợp, khái niệm hoán vị cũng từng được dùng theo cách truyền thống để chỉ một tập hợp có thứ tự không trùng lặp, mặc dù hiện nay ít được áp dụng.

Khái niệm hoán vị phản ánh ý tưởng rằng các đối tượng phân biệt có thể được sắp xếp theo nhiều thứ tự khác nhau, và được định nghĩa như sau:

Cho tập hợp A gồm n phần tử (n ≥ 1). Mỗi cách sắp xếp các n phần tử của tập hợp A được gọi là một hoán vị của n phần tử đó.

Ví dụ, với tập hợp các số từ một đến sáu, mỗi cách sắp xếp khác nhau tạo ra một dãy số không trùng lặp. Một số ví dụ về hoán vị bao gồm: '1, 2, 3, 4, 5, 6', '3, 4, 6, 1, 2, 5', '2, 1, 4, 6, 5, 3', và nhiều dãy khác.

Có nhiều cách để định nghĩa chính xác khái niệm hoán vị. Một hoán vị là một dãy có thứ tự mà mỗi phần tử của tập hợp xuất hiện đúng một lần; vì thế, '1, 2, 2, 3, 4, 5, 6' và '1, 2, 4, 5, 6' không phải là hoán vị của tập '1, 2, 3, 4, 5, 6'. Sự khác biệt chính giữa một hoán vị và một tập hợp là hoán vị yêu cầu các phần tử phải được sắp xếp theo một thứ tự cụ thể.

Đếm số hoán vị

Trong phần này, chúng ta sẽ áp dụng định nghĩa truyền thống về hoán vị: một hoán vị là một dãy có thứ tự không trùng lặp, có thể thiếu một số phần tử. Việc đếm số hoán vị có kích thước r từ một tập hợp có kích thước n (với r≤n) là rất đơn giản.

Chẳng hạn, nếu chúng ta có 10 phần tử, từ 1 đến 10, một hoán vị ba phần tử của tập hợp này có thể là {5, 3, 4}. Ở đây, n=10 và r=3. Vậy có bao nhiêu cách để tạo ra một hoán vị như thế?

1. Để lựa chọn phần tử đầu tiên trong một hoán vị, chúng ta có n sự lựa chọn, vì tập hợp có n phần tử khác nhau.
2. Sau khi đã chọn một phần tử, phần tử thứ hai của hoán vị sẽ có (n − 1) lựa chọn từ phần còn lại của tập hợp.
3. Phần tử thứ ba có (n − 2) lựa chọn.
4. Quá trình này tiếp tục cho đến khi tất cả r phần tử của hoán vị được chọn. Tức là phần tử cuối cùng sẽ có (n - (r - 1)) = (n − r + 1) sự lựa chọn.

Tóm lại, số lượng hoán vị khác nhau chứa r phần tử từ n đối tượng là: n(n − 1)(n − 2)... (n − r + 1). Nếu ký hiệu số này là P(n, r) và dùng ký hiệu giai thừa, ta có thể viết như sau:

.

Trong ví dụ này, với n = 10 và r = 3, số lượng hoán vị là: P(10,3) = 720.

Các ký hiệu cổ điển khác bao gồm: P_r, P_n,r, và _nP_r.

Đại số trừu tượng

Trong đại số trừu tượng và các lĩnh vực toán học khác, khái niệm hoán vị (trong một tập hợp) thường được định nghĩa là một phép ánh xạ từ một tập hợp hữu hạn trở về chính nó. Ví dụ về hoán vị của các số từ 1 đến 10 chính là các phép ánh xạ từ tập {1, …, 10} trở về chính nó.

Ký hiệu

Ký hiệu (1 5 2) (3 4) có nghĩa là: 1 được ánh xạ đến 5, 5 đến 2, 2 trở lại 1, 3 được ánh xạ đến 4 và 4 trở lại 3.

Trong ký hiệu (1 5 2), các số 3 và 4 không bị thay đổi vị trí, mà chỉ có các số 1, 2, 5 và 4 bị hoán đổi.

Chi tiết

Có hai phương pháp chính để ký hiệu các phép hoán vị.

Trong phương pháp ký hiệu theo quan hệ, chúng ta có thể trình bày thứ tự gốc của các phần tử trên một dòng, và thứ tự mới trên dòng kế tiếp:

Có nghĩa là, phần tử đứng ở vị trí đầu tiên của tập hợp mới là phần tử đứng ở vị trí thứ hai của tập hợp ban đầu, phần tử ở vị trí thứ hai của tập hợp mới là phần tử ở vị trí thứ năm của tập hợp ban đầu, và tiếp tục theo cách đó.

Chúng ta có thể biểu diễn phép hoán vị bằng cách theo dõi sự di chuyển của các phần tử qua các lần áp dụng phép hoán vị liên tiếp. Ví dụ, nếu xem xét phép hoán vị này, khi áp dụng lần đầu, phần tử ở vị trí đầu tiên sẽ chuyển đến vị trí thứ hai, sau lần áp dụng thứ hai, nó sẽ chuyển đến vị trí thứ năm, và sau lần áp dụng cuối cùng, nó trở về vị trí ban đầu. Những sự chuyển đổi này tạo thành một chu trình, và có thể được biểu diễn dưới dạng (1 2 5), (2 5 1) hoặc (5 1 2), nhưng không phải là (1 5 2). Các chu trình khác bắt đầu từ những phần tử chưa được bao gồm, cho đến khi tất cả các phần tử đều nằm trong một chu trình.

Vì vậy, chúng ta có thể ký hiệu phép hoán vị dưới dạng một tập hợp các chu trình. Trong ví dụ trên, phép hoán vị có thể được viết dưới dạng chu trình (1 2 5)(3 4). Thứ tự của các chu trình không quan trọng, nhưng thứ tự các phần tử trong mỗi chu trình có thể thay đổi theo cách sắp xếp. Do đó, phép hoán vị này cũng có thể được viết là (4 3)(2 5 1). Trong cách viết tiêu chuẩn, chúng ta sẽ đặt phần tử có chỉ số thấp nhất ở đầu mỗi chu trình và sắp xếp các chu trình theo thứ tự tăng dần của phần tử đầu tiên.

Trong ký hiệu này, các vị trí cố định, tức là các phần tử ánh xạ vào chính mình, thường bị bỏ qua. Ví dụ, (1 3)(2)(4 5) có thể được rút gọn thành (1 3)(4 5), vì chu trình chỉ chứa một phần tử không ảnh hưởng đến hoán vị.

Một phép hoán vị chỉ bao gồm một chu trình được gọi là một chu trình đơn. Độ dài của một chu trình là số lượng phần tử trong nó. Ví dụ, độ dài của (1 2 5) là ba. Những chu trình có độ dài hai được gọi là các chuyển vị, trong đó hai phần tử đổi chỗ với nhau.

Những hoán vị đặc biệt

Một hoán vị mà không thay đổi vị trí của bất kỳ phần tử nào, tức là mỗi phần tử vẫn giữ nguyên vị trí của nó, được gọi là hoán vị đồng nhất. Nói cách khác, phép hoán vị này không làm xáo trộn các phần tử.

Đối với một hoán vị P, ta có thể tìm một hoán vị P khác mà khi áp dụng liên tiếp với P sẽ trở lại trạng thái ban đầu. Đây là hoán vị mà khi thực hiện, không làm thay đổi kết quả so với việc áp dụng hoán vị đồng nhất. Hoán vị này gọi là hoán vị nghịch đảo của P.

Tích của hai hoán vị P và Q được hiểu là kết quả của việc áp dụng hoán vị P rồi đến Q. Kết quả này có thể được biểu diễn bằng một hoán vị R nào đó, và R có thể là chính P hoặc Q. Tích của P và Q chính là hoán vị R. Để tìm hiểu thêm, có thể xem xét nhóm đối xứng và nhóm hoán vị.

Một hoán vị chẵn là hoán vị có thể được viết dưới dạng tích của một số chẵn các phép chuyển vị, ví dụ như hoán vị đồng nhất (1 2)(1 2) là hoán vị chẵn. Ngược lại, một hoán vị lẻ là hoán vị có thể viết dưới dạng tích của một số lẻ các phép chuyển vị. Mỗi hoán vị chỉ có thể là chẵn hoặc lẻ, không thể vừa chẵn vừa lẻ.

Hoán vị cũng có thể được biểu diễn dưới dạng ma trận, và ma trận này được gọi là ma trận hoán vị.

Đánh số hoán vị

Số Factoradic có thể được sử dụng để chỉ định các số hiệu duy nhất cho từng hoán vị, giúp việc tra cứu hoán vị tương ứng với một số factoradic n trở nên nhanh chóng và dễ dàng.

Tài liệu tham khảo thêm

• Hoán vị vòng
• Hoán vị chẵn và lẻ
• Hoán vị Josephus
• Nhóm đối xứng
• Nhóm hoán vị

• Donald Knuth. The Art of Computer Programming, Tập 3: Sorting and Searching, Ấn bản lần thứ ba. Addison-Wesley, 1997. ISBN 0-201-89685-0. Chương 5.1: Các thuộc tính tổ hợp của hoán vị, trang 11–72.