Mỗi
ánh xạ f: X ® S. Cho tương ứng với mỗi i Î X, một và chỉ một phần tử f(i) Î S.
Được
gọi là một chỉnh hợp lặp chập k của S.
Nhưng do X là tập hữu hạn (k phần tử) nên ánh xạ f có thể
xác định qua bảng các giá trị f(1), f(2), …, f(k).
Ví
dụ: S = {A, B, C, D, E, F}; k = 3. Một ánh xạ f có thể cho như sau:
|
i |
1 |
2 |
3 |
|
f(i) |
E |
C |
E |
Vậy có thể đồng nhất f với dãy giá trị (f(1), f(2), …,
f(k)) và coi dãy giá trị này cũng là một chỉnh hợp lặp chập k của S. Như ví dụ
trên (E, C, E) là một chỉnh hợp lặp chập 3 của S. Dễ dàng chứng minh được kết
quả sau bằng quy nạp hoặc bằng phương pháp đánh giá khả năng lựa chọn:
Số
chỉnh hợp lặp chập k của tập gồm n phần tử là nk
Tags:
Algorithms