tailieunhanh - BÀI TOÁN ĐẾM – PHẦN 2

Một cách sắp xếp có thứ tự k phần tử có thể lặp lại của một tập n phần tử được gọi là một chỉnh hợp lặp chập k từ tập n phần tử. Nếu A là tập gồm n phần tử đó thì mỗi chỉnh hợp như thế là một phần tử của tập Ak. Ngoài ra, mỗi chỉnh hợp lặp chập k từ tập n phần tử là một hàm từ tập k phần tử vào tập n phần tử. Vì vậy số chỉnh hợp lặp chập k từ tập n phần tử là nk. . | BÀI TOÁN ĐẾM - PHẦN 2 CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG. . Chỉnh hợp có lặp. Một cách sắp xếp có thứ tự k phần tử có thể lặp lại của một tập n phần tử được gọi là một chỉnh hợp lặp chập k từ tập n phần tử. Nếu A là tập gồm n phần tử đó thì mỗi chỉnh hợp như thế là một phần tử của tập Ak. Ngoài ra mỗi chỉnh hợp lặp chập k từ tập n phần tử là một hàm từ tập k phần tử vào tập n phần tử. Vì vậy số chỉnh hợp lặp chập k từ tập n phần tử là nk. . Tổ hợp lặp. Một tổ hợp lặp chập k của một tập hợp là một cách chọn không có thứ tự k phần tử có thể lặp lại của tập đã cho. Như vậy một tổ hợp lặp kiểu này là một dãy không kể thứ tự gồm k thành phần lấy từ tập n phần tử. Do đó có thể là k n. Mệnh đề 1 Số tổ hợp lặp chập k từ tập n phần tử bằng C k-1. Chứng minh. Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một dãy n-1 thanh đứng và k ngôi sao. Ta dùng n - 1 thanh đứng để phân cách các ngăn. Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần tử thứ i của tập xuất hiện trong tổ hợp. Chẳng hạn tổ hợp lặp chập 6 của 4 phần tử được biểu thị bởi mô tả tổ hợp chứa đúng 2 phần tử thứ nhất 1 phần tử thứ hai không có phần tử thứ 3 và 3 phần tử thứ tư của tập hợp. Mỗi dãy n - 1 thanh và k ngôi sao ứng với một xâu nhị phân độ dài n k -1 với k số 1. Do đó số các dãy n - 1 thanh đứng và k ngôi sao chính là số tổ hợp chập k từ tập n k - 1 phần tử. Đó là điều cần chứng minh. Thi dụ 8 1 Có bao nhiêu cách chọn 5 tờ giấy bạc từ một két đựng tiền gồm những tờ 1000đ 2000đ 5000đ . Giả sử thứ tự mà các tờ tiền được chọn là không quan trọng các tờ tiền cùng loại là không phân biệt và mỗi loại có ít nhất 5 tờ. Vì ta không kể tới thứ tự chọn tờ tiền và vì ta chọn đúng 5 lần mỗi lần lấy một từ 1 trong 7 loại tiền nên mỗi cách chọn 5 tờ giấy bạc này chính là một tổ hợp lặp chập 5 từ 7 phần tử. Do đó số cần tìm là C5 5-1 462. 2 Phương trình x1 x2 x3 15 có bao nhiêu nghiệm nguyên không âm Chúng ta nhận thấy mỗi nghiệm của phương trình ứng với một cách chọn