Hoán vị
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, ...
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.
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.
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ó.
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í.
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
