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 đến 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ự chưa lặp
Khái niệm hoán vị miêu tả ý tưởng sáng tạo rằng những đối tượng người tiêu dùng phân biệt hoàn toàn có thể được sắp xếp theo những 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 kết quả của sự sắp xếp thứ tự n phần tử của tập hợp A được gọi chính là một hoán vị của n phần tử đó.
Bạn đang đọc: Hoán vị – Wikipedia tiếng Việt
Hoán vị – Wikipedia tiếng Việt
Ví dụ, với tập hợp gồm những số đến từ một đến sáu, mỗi cách sắp thứ tự cũng sẽ tạo thành một dãy những số không lặp lại. Một số những hoán vị như thế là : ” 1, 2, 3, 4, 5, 6 “, ” 3, 4, 6, 1, 2, 5 “, ” 2, 1, 4, 6, 5, 3 “, v .. v .
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” , “1, 2, 4, 5, 6” đều chưa 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 số hoán vị
Trong đề mục này mọi người cũng sẽ dùng định nghĩa truyền thống của hoán vị: một hoán vị chính là một bộ có thứ tự chưa 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 chính 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ì mọi người đã 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 chỉ 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 chính là phần tử cuối cùng của hoán vị cũng sẽ có (n – (r – 1)) = (n − r + 1) cách chọn.
Tóm lại, mọi người 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, mọi người có thể viết:
P. ( n, r ) = n ! ( n − r ) ! \ displaystyle P. ( n, r ) = \ frac n ! ( n-r ) ! 
Trong thí 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, , nPr.
Đạ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ó.
Phép ký hiệu vòng ( 1 5 2 ) ( 3 4 ) mang ý nghĩa chính 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 đổi khác vị trí .
Có hai cách ký hiệu chính cho những phép hoán vị.
LGBTQI+ có nghĩa chính là gì?
Trong cách ký hiệu quan hệ, hoàn toàn có thể viết thứ tự ” tự nhiên ” của những thành phần trên một dòng, và thứ tự mới ở trên một dòng khác :
[ 1 2 3 4 5 2 5 4 3 1 ] \ displaystyle \ begin bmatrix 1 và 2 , 3 , và 4 và 5 \ \ 2 và 5 và 4 , và 3 và 1 \ end bmatrix 
Nghĩa chính là ở vị trí thứ nhất sẽ được đặt thành phần thứ hai của tập hợp, ở vị trí thứ hai cũng sẽ đã được đặt thành phần thứ năm của tập hợp, …Chúng ta cũng hoàn toàn có thể màn biểu diễn phép hoán vị theo sự biến hóa của những thành phần khi phép hoán vị được vận dụng thường xuyên nhau. Nếu tất cả mọi người nhìn vào phép hoán vị ở trên đây, khi vận dụng phép hoán vị, vị trí thứ nhất giờ đây cũng sẽ là thành phần thứ hai, vận dụng phép hoán vị một lần nữa vị trí thứ số 1 cũng sẽ là thành phần thứ năm, và vận dụng phép hoán vị một lần nữa, vị trí này lại trở thành thành phần bắt đầu. Sự đổi khác của những thành phần tạo thành một quy trình, , và tất cả mọi người hoàn toàn có thể viết dưới dạng ( 1 2 5 ), hoặc ( 2 5 1 ) hay ( 5 1 2 ), nhưng chưa phải chính là ( 1 5 2 ). Chu trình tiếp theo khởi đầu bằng một thành phần nào đó không Open, cho đến khi mọi thành phần đều Open trong một quá 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 chưa 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é số 1 ở đầu mỗi chu trình, , 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ỏ lỡ những vị trí cố định , thắt chặt, nghĩa là, thành phần ánh xạ vào chính nó ; như vậy ( 1 3 ) ( 2 ) ( 4 5 ) hoàn toàn có thể viết thành ( 1 3 ) ( 4 5 ), chính do một quá trình chỉ có một thành phần sẽ chưa gây ra tác động ảnh hưởng gì .
Một phép hoán vị chỉ bao gồm một chu trình được gọi ngay chính là một chu trình. Số phần tử trong một chu trình đã được gọi chính là độ dài. Ví dụ, độ dài của (1 2 5) chính là ba. Các chu trình có độ dài hai đã được gọi chính là những chuyển vị, hai phần tử thay đổi vị trí cho nhau.
Những hoán vị đặc biệt quan trọng
Một hoán vị “đổi chỗ” phần tử thứ số 1 với phần tử thứ nhất, phần tử thứ hai với phần tử thứ hai,…, nghĩa chính 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, mọi người 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 quả của việc áp dụng P rồi đến Q cũng sẽ giống như việc áp dụng một hoán vị R nào đó. Lưu ý rằng R có thể 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 số 1 chính 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ể triệu 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.
” How Are You Nghĩa Là Gì ? Cách Dùng Trong Tiếng Anh How Are You Doing Là Gì
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 quả được gọi chính là ma trận hoán vị.
Đánh số những hoán vị
Các số Factoradic hoàn toàn có thể dùng để gán những số hiệu duy số 1 cho những hoán vị, sao cho với một số ít factoradic n, ta hoàn toàn có thể nhanh gọn tìm hoán vị tương ứng .
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.