Thảo luận:Toán học tổ hợp
Bách khoa toàn thư mở Wikipedia
[sửa] Liệt kê các tổ hợp chập k của tập n phần tử
Một tổ hợp chập kcủa tập hợp n phần tử Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): A=\{a_1,a_2,...,a_n\}
chỉ cần biểu diễn bằng tập hợp k chỉ số của các phần tử được chọn.Chẳng hạn với tập Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): A=\{a_1,a_2,a_3,a_4,a_5,a_6\}
, tập con ba phần tử, tức là một tổhợp chập 3 của 6 phần tử ấy Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): \{a_2,a_4,a_5\}
có thể xác định qua các chỉ số (2,4,5). Hơn nữa ta có thể luôn xếp các tập con đó theo thứ tự tăng đần.
Như vậy mỗi tập con k phần tử của A có thể biểu diễn bới các chỉ số (Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): i_1,i_2,...,i_k)
với Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): i_1<i_2<...<i_k
. Các chỉ số ngày nằm từ 1 đến n nên ta có Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): i_k \le n ,i_{k-1}\le n-1,...i_j \le n-(k-j),..., i_1 \le n-(k-1) . Như vậy giá trị tối đa mà Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): i_j
đạt được là Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): n-(k-j)
Chẳng hạn với n=7, k=4,chỉ số tối đa Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): i_4
là 7, Lỗi toán (Không tạo mới hay viết vào thư mục kết quả được): i_3 là 6, i2 là 5 và i1 là 4.
toi cat tam vao day vi phai di lam viec khác . 10:36, 12 tháng 9 2006 (UTC)