Hoán vị
Bách khoa toàn thư mở Wikipedia
Trong toán học, đặc biệt là trong đại số trừu tượng và các lĩnh vực có liên quan, một hoán vị là một song ánh từ một tập hợp hữu hạn X vào chính nó.
Trong lý thuyết tổ hợp, khái niệm hoán vị cũng mang một ý nghĩa truyền thống mà nay ít còn được dùng, đó là mô tả một bộ có thứ tự không lặp, và không nhất thiết phải chứa đầy đủ số phần tử.
Khái niệm hoán vị diễn tả ý tưởng rằng những đối tượng phân biệt có thể được sắp xếp theo những thứ tự khác nhau. Ví dụ, với các số từ một đến sáu, mỗi cách sắp thứ tự sẽ tạo thành một dãy các số không lặp lại. Một hoán vị như thế là: "3, 4, 6, 1, 2, 5".
Có nhiều cách định nghĩa khái niệm hoán vị một cách chính quy hơn. Một hoán vị là một dãy có thứ tự chứa mỗi phần tử của một tập hợp một và đúng một lần; như vậy "1, 2, 2, 3, 4, 5, 6" và "1, 2, 4, 5, 6" đều không phải là hoán vị của tập "1, 2, 3, 4, 5, 6". Do đó, điểm khác nhau cơ bản giữa một hoán vị và một tập hợp là: những phần tử của một hoán vị được sắp xếp theo một thứ tự xác định.
Mục lục |
[sửa] Đếm số hoán vị
Trong đề mục này chúng ta sẽ dùng định nghĩa truyền thống của hoán vị: một hoán vị là một bộ có thứ tự không lặp, có thể thiếu một số phần tử. Có thể dễ dàng đếm được số hoán vị có kích thước r khi chọn từ một tập hợp có kích thước n (với r≤n).
Ví dụ, nếu chúng ta có 10 phần tử, các số nguyên {1, 2, ..., 10}, một hoán vị của ba phần tử từ tập hợp này là {5, 3, 4}. Trong trường hợp này, n=10 và r=3. Vậy có bao nhiêu cách để thành lập một hoán vị như vậy?
- Để chọn phần tử đầu tiên của một hoán vị, chúng ta có n cách, bởi vì có n phần tử phân biệt của tập hợp.
- Tiếp theo, vì chúng ta đã dùng một trong n phần tử, phần tử thứ hai của hoán vị sẽ có (n − 1) cách để chọn từ tập hợp còn lại.
- Phần tử thứ ba có thể được chọn bằng (n − 2) cách.
- Công việc này lặp lại cho đến khi có đủ r phần tử của hoán vị. Nghĩa là phần tử cuối cùng của hoán vị sẽ có (n - (r - 1) ) = (n − r + 1) cách chọn.
Tóm lại, chúng ta có:n(n − 1)(n − 2) ... (n − r + 1) hoán vị khác nhau chứa r phần tử chọn từ n đối tượng. Nếu chúng ta ký hiệu số này là P(n, r) và dùng ký hiệu giai thừa, chúng ta có thể viết:
.
Trong ví dụ trên, chúng ta có n = 10 và r = 3, vậy số hoán vị là: P(10,3) = 720.
Những cách ký hiệu cũ bao gồm: nPr, Pn,r, or nPr.
[sửa] Đại số trừu tượng
Như đã mô tả trong một đề mục trước, trong đại số trừu tượng và những lĩnh vực toán học khác, khái niệm hoán vị (của một tập hợp) được hiểu là một song ánh từ một tập hợp hữu hạn vào chính nó. Ví dụ trên đây về những hoán vị của các số từ 1 đến 10, sẽ được diễn tả như một phép song ánh từ tập {1, …, 10} vào chính nó.
[sửa] Ký hiệu
Phép ký hiệu vòng (1 5 2) (3 4) mang ý nghĩa là 1 được ánh xạ đến 5, 5 đến 2, 2 đến 1, 3 đến 4, và 4 đến 3.
Ký hiệu (1 5 2) được hiểu ngầm rằng 3 và 4 không thay đổi vị trí.
[sửa] Chi tiết
Có hai cách ký hiệu chính cho những phép hoán vị.
Trong cách ký hiệu quan hệ, có thể viết thứ tự "tự nhiên" của các phần tử trên một dòng, và thứ tự mới trên một dòng khác:
Nghĩa là ở vị trí thứ nhất sẽ được đặt phần tử thứ hai của tập hợp, ở vị trí thứ hai sẽ được đặt phần tử thứ năm của tập hợp,...
Chúng ta cũng có thể biểu diễn phép hoán vị theo sự thay đổi của các phần tử khi phép hoán vị được áp dụng liên tiếp nhau. Nếu chúng ta nhìn vào phép hoán vị trên đây, khi áp dụng phép hoán vị, vị trí thứ nhất bây giờ sẽ là phần tử thứ hai, áp dụng phép hoán vị một lần nữa vị trí thứ nhất sẽ là phần tử thứ năm, và áp dụng phép hoán vị một lần nữa, vị trí này lại trở thành phần tử ban đầu. Sự thay đổi của các phần tử tạo thành một chu trình, và chúng ta có thể viết dưới dạng (1 2 5), hoặc (2 5 1) hay (5 1 2), nhưng không phải là (1 5 2). Chu trình tiếp theo bắt đầu bằng một phần tử nào đó chưa xuất hiện, cho đến khi mọi phần tử đều xuất hiện trong một chu trình.
Như vậy, chúng ta có thể ký hiệu phép hoán vị như là một tập hợp các chu trình. Hoán vị trên đây có dạng chu trình là (1 2 5)(3 4). Thứ tự của các chu trình không quan trọng, còn thứ tự của các phần tử trong một chu trình thì có thể thay đổi theo phép xoay vòng chu trình. Do đó, cùng một hoán vị trên có thể viết là (4 3)(2 5 1). Trong cách viết "tiêu chuẩn" cho một phép hoán vị, ta đặt vị trí có số hiệu bé nhất ở đầu mỗi chu trình, và sắp xếp các chu trình theo thứ tự tăng của phần tử đầu tiên.
Ký hiệu này thường bỏ qua các vị trí cố định, nghĩa là, phần tử ánh xạ vào chính nó; như vậy (1 3)(2)(4 5) có thể viết thành (1 3)(4 5), bởi vì một chu trình chỉ có một phần tử sẽ không gây ra tác động gì.
Một phép hoán vị chỉ bao gồm một chu trình được gọi ngay là một chu trình. Số phần tử trong một chu trình được gọi là độ dài. Ví dụ, độ dài của (1 2 5) là ba. Những chu trình có độ dài hai được gọi là những chuyển vị, hai phần tử thay đổi vị trí cho nhau.
[sửa] Những hoán vị đặc biệt
Một hoán vị "đổi chỗ" phần tử thứ nhất với phần tử thứ nhất, phần tử thứ hai với phần tử thứ hai,..., nghĩa là trên thực tế không đổi chỗ các phần tử, được gọi là phép hoán vị đồng nhất.
Nếu có một hoán vị P, chúng ta có thể mô tả một hoán vị P−1, làm mất tác dụng của việc áp dụng phép P. Nghĩa là, áp dụng phép P rồi đến P−1 cho kết quả giống như áp dụng phép hoán vị đồng nhất. Chúng ta luôn có một hoán vị như vậy vì một hoán vị là một phép song ánh. Hoán vị như vậy được gọi là hoán vị nghịch đảo.
Chúng ta có thể định nghĩa tích của hai hoán vị. Nếu chúng ta có hai hoán vị, P và Q, kết qủa của việc áp dụng P rồi đến Q sẽ giống như việc áp dụng một hoán vị R nào đó. Lưu ý rằng R có thể chính là P hoặc Q. Tích của P và Q được định nghĩa bằng hoán vị R. Chi tiết hơn, có thể đọc nhóm đối xứng và nhóm hoán vị.
Một hoán vị chẵn là một hoán vị có thể biểu diễn dưới dạng tích của một số chẵn các phép chuyển vị, như vậy hoán vị đồng nhất là một hoán vị chẵn bởi vì nó bằng (1 2)(1 2). Một hoán vị lẻ là một hoán vị có thể biểu diễn dưới dạng tích của một số lẻ các phép chuyển vị. Có thể chứng tỏ rằng mỗi hoán vị hoặc là chẵn, hoặc là lẻ và không thể có cả hai tính chất này.
Chúng ta cũng có thể biểu diễn hoán vị dưới dạng ma trận - ma trận kết qủa được gọi là ma trận hoán vị.
[sửa] Đánh số các hoán vị
Các số Factoradic có thể dùng để gán các số hiệu duy nhất cho các hoán vị, sao cho với một số factoradic n, ta có thể nhanh chóng tìm hoán vị tương ứng.
[sửa] Đọc 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ị
[sửa] Tham khảo
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.1: Combinatorial Properties of Permutations, pp.11–72.
