Khi k = n. Một chỉnh hợp không lặp chập n của S được gọi là một hoán vị các phần tử của S. Ví dụ: một hoán vị: áA, D, C, E, B, Fñ của S = {A, B, C, D, E, F}
|
i |
1 |
2 |
3 |
4 |
5 |
6 |
|
f(i) |
A |
D |
C |
E |
B |
F |
Để ý rằng khi k = n thì số phần tử
của tập X = {1, 2, …, n} đúng bằng số phần tử của S. Do tính chất đôi một khác
nhau nên dãy f(1), f(2), …, f(n) sẽ liệt kê được hết các phần tử trong S. Như
vậy f là toàn ánh. Mặt khác do giả thiết f là chỉnh hợp không lặp nên f là đơn
ánh. Ta có tương ứng 1-1 giữa các phần tử của X và S, do đó f là song ánh. Vậy
nên ta có thể định nghĩa một hoán vị của S là một song ánh giữa {1, 2, …, n} và
S.
Số hoán vị của tập gồm n phần tử = số chỉnh hợp không lặp chập n = n!
Tags:
Algorithms