ĐẾM CÁC HOÁN VỊ TỔ HỢP

1. Chỉnh hợp lặp

Định nghĩa 1. Một chỉnh hợp lặp chập k của n phần tử là bộ có thứ tự gồm k thành phần lấy
từ n phần tử của tập đã cho.
Như vậy, một chỉnh hợp lặp chập k của n phần tử có thể xem là phần tử của tích đề các Ak
với A là tập đã cho. Theo nguyên lý nhân, số các tất cả các chỉnh hợp lặp chập k của n sẽ là nk.
2. Chỉnh hợp không lặp

Định nghĩa 2. Chỉnh hợp không lặp chập k của n phần tử là bộ có thứ tự gồm k thành phần
lấy ra từ n phần tử đã cho. Các phần tử không được lặp lại.
Để xây dựng một chỉnh hợp không lặp, ta xây dựng từ thành phần đầu tiên. Thành phần này
có n khả năng chọn. Mỗi thành phần tiếp theo những khả năng chọn giảm đi 1 (vì không được lấy
lặp lại). Tới thành phần thứ k có n-k + 1 khả năng chọn. Theo nguyên lý nhân ta có số chỉnh hợp
lặp k của tập hợp n phần tử ký hiệu là P(n, k) được tính theo công thức:
3. Hoán vị

Định nghĩa 3. Ta gọi các hoán vị của n phần tử là một cách xếp có thứ tự các phần tử đó.
Số các hoán vị của tập n phần tử có thể coi là trường hợp riêng của chỉnh hợp không lặp với k = n.
Ta cũng có thể đồng nhất một hoán vị với một song ánh từ tập n phần tử lên chính nó. Như
vậy, số hoán vị của tập gồm n phần tử là P(n, n) = n!.

4. Tổ hợp

Định nghĩa 4. Một tổ hợp chập k của n phần tử là một bộ không kể thứ tự gồm k thành
phần khác nhau lấy từ n phần tử đã cho. Nói cách khác, ta có thể coi một tổ hợp chập k của n phần
tử là một tập con k phần tử lấy trong n phần tử. Số tổ hợp chập k của n phần tử kí hiệu là C(n,k).
Ta có thể tính được trực tiếp số các tổ hợp chập k của tập n phần tử thông qua chỉnh hợp
không lặp của k phần tử.