Khác biệt giữa các bản “Hoán vị”

n
robot Thay: hi:क्रमचय; sửa cách trình bày
n (robot Thay: hi:क्रमचय; sửa cách trình bày)
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 [[ánh xạ|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".
 
== Đế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:
:<math> P(n,r) = \frac{n!}{(n-r)!} </math>.
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.
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 (Toán học)|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&nbsp;2&nbsp;5)(3&nbsp;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&nbsp;3)(2&nbsp;5&nbsp;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&nbsp;3)(2)(4&nbsp;5) có thể viết thành (1&nbsp;3)(4&nbsp;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ì.
 
== Đọ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ị]]
 
== Tham khảo ==
* [[Donald Knuth|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&ndash;7211–72.
 
[[Thể loại:Hoán vị]]
[[gu:ક્રમચય]]
[[ko:순열]]
[[hi:क्रमचय]]
[[hi:क्रमपरिवर्तन]]
[[it:Permutazione]]
[[he:תמורה (מתמטיקה)]]
169.477

lần sửa đổi