Trong các bài toán đếm ta gặp bài toán sau: Một người vào cửa hang mua dụng cụ học tập để làm thành một món quà gồm viết, sách và tập, người đó chỉ mua tổng cộng 5 món đồ. Biết rằng trong cửa hàng có 5 cây viết giống nhau, 6 sách giống nhau và 10 cuốn tập giống nhau, hỏi có bao nhiêu cách chọn viết, sách tập để làm quà?
Ta thấy rằng số lượng các viết sách và tập đều lớn hơn số cần mua, do đó bài toán chỉ quay lại việc đếm là có bao nhiêu bộ sách viết tập mà tổng số là 5 cái, trong đó mỗi cái có hoặc không có.
Có ba đối tượng là viết, sách và tập, tạ kí hiệu là $A = { V, S, T }$. Một món quà gồm 5 cái, do đó quà có thể là $X = { V, V, V, S, T }$, gồm 3 cây viết và 1 sách, 1 tập, hoặc là tập $Y = { V, V, S, T, T }$, ta thấy các đối tượng $V, T$ là lập lại. Khi đó ta nói tổ hợp $X, Y$ là tổ hợp lặp.
Để định nghĩa rõ hơn ta có định nghĩa sau:
Định nghĩa. Cho tập $A = { a_1, a_2, \cdots, a_k }$. Một ánh xạ từ $p: A \mapsto \mathbb{N} $, khi đó $P$ được gọi là một multiset của A.
Ví dụ 1. Cho $A = { a, b, c }$. Ánh xạ $p: A \mapsto \mathbb{N}$ như sau: $p(a) = 2, p(b) = 1, p(c) = 1$. Khi đó ta có thể kí hiệu $p$ là $(aabc)$, hay $(baac)$,.., không tính đến thứ tự của các phần tử $a, b, c$.
Đặt $n = p(a_1) + p(a_2)+\cdots +p(a_k)$, bài toán đặt ra là có bao nhiêu ánh xạ $p: A \mapsto \mathbb{N}$ mà $n = p(a_1) + p(a_2)+\cdots +p(a_k)$.
Tiếp theo ví dụ trên, nếu $ p(a) + p(b) + p(c) = 2$ thì có các multiset sau: $(ab), (ac), (bc), (aa), (bb), (cc)$, 6 multiset.
Tính chất. Cho tập $A = { a_1, a_2, \cdots, a_k }$, số ánh xạ $p: A \mapsto \mathbb{N}$ thỏa $p(a_1) + \cdots + p(a_k) = n$ là $C^n_{n+k-1}$
Bài toán 2. Giải bài toán trên với cách chia sao cho mỗi người có ít nhất một viên.
Trước hết phát cho mỗi người một viên, thì còn $n-k$ viên kẹo, tiếp tục áp dụng bài toán trên với $n-k$. Khi đó số cách chia là
$C^{k-1}_{n-1}$
Ta có thể giải bài toán trên mà không cần sử dụng bài toán 1 bằng cách xây dựng dãy nhị phân thỏa: $a_1$ chữ số đầu là 0, tiếp theo là số 1, tiếp là $a_2$ chữ số 0, …., cuối cùng là $a_k$ chữ số 0. Dãy này có $k-1$ chữ số 1 đứng giữa $n$ chữ số 0 và không có hai chữ số $1$ nào đứng kề nhau. Khi đó số dãy nhị phân là: $C^{k-1}_{n-1}$.
Phần kế tiếp ta cùng tìm hiểu và giải một số bài toán có thể đưa về bài toán tổ hợp lặp hay bài toán chia kẹo Euler. Các bạn chờ nhé.
Bài toán 1 và 2 có thể phát biểu dưới dạng sau.
Bài toán 3. Cho phương trình $x_1 + x_2 + \cdots + x_k = n$ trong đó $k, n$ là các số nguyên dương.
a. Tìm số nghiệm tự nhiên của phương trình.
b. Tìm số nghiệm nguyên dương của phương trình.
Như bài toán trên ta đã biết, số nghiệm tự nhiên của phương trình là $C^{k-1}_{n+k-1}$.
Số nghiệm nguyên dương của phương trình là $C^{k-1}_{n-1}$.