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}$.
Trong phần trước ta đã biết, số nghiệm nguyên không âm của phương trình $x_1 +x_2+\cdots + x_k = n$ là $C_{n+k-1}^{k-1}$, và số nghiệm nguyên dương là $C^{k-1}_{n-1}$.
Từ bài toán này ta có thể giải các bài toán sau:
Ví dụ 1. Tìm số nghiệm nguyên của phương trình $x_1 + x_2 + x_3 + x_4 + x_5 = 30$ nếu:
a) $x_i \geq 2 \forall i = \overline{1,5}$.
b) $ 3 < x_1, x_2 $ và $x_3, x_4, x_5 > 5$.
c) $x_1, x_2, x_3, x_4 \geq 4$ và $ 0 < x_5 < 3$.
Ví dụ 2. Có bao nhiêu bộ $(x_1, x_2, ..., x_{10})$ các số nguyên dương thỏa $x_1 + x_2 + \cdots x_{10} < 2020$.
Ví dụ 3. Có bao nhiêu bộ $(x_1, x_2, ..., x_{10})$ các số tự nhiên thỏa $x_1 \leq x_2 \leq x_3 \leq \cdots \leq x_{10} \leq 2020$. Ví dụ 4. (VMO 2012) Cho một nhóm gồm 5 cô gái, kí hiệu là $G_1, G_2, G_3, G_4, G_5$ và 12 chàng trai. Có 17 chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm người đã cho vào các chiếc ghế sao đó sao cho các điều kiện sau được đồng thời thỏa mãn : Ví dụ 5. Có bao nhiêu bộ số nguyên dương $(a, b, c, d)$ thỏa $d = max\{a,b,c,d\}, d \leq 2015$ và $(ad+bc)(bd+ac)(cd+ab) = (d-a)^2(d-b)^2(d-c)^2$. Trên đây là một số bài toán liên quan đến bài toán chia kẹo Euler, các bạn hãy đọc và tìm hiểu thêm trong các tài liệu khác. Bài tập rèn luyện. Bài 1. Tìm số nghiệm nguyên dương của phương trình: $x_1 + x_2 + ...+ x_5 = 100$ Bài 7. Để bảo vệ máy tính của minh khỏi su tấn công của hacker, một lâp trinh viên muốn thiết lập một mât khẩu cho máy tính của mình. Mât khẩu này bao gồm tất cả các chữ cái trong bảng chữ cái tiêng Anh, mỗi chữ cái một lần xuất hiện và các chữ nguyên âm không đứng cạnh nhau. Hỏi lâp trình viên đó có bao nhiêu cách cài đăt mât khẩu? Bài 8. Bốn anh em An, Bình, Cừng, Danh rất thích ăn keo. Nhân dip Tết, me của các câu đực thửng rất nhiều quà, trong đó có một phần quà là một bịch keo bao gồm 125 viên keo. Vì quá thich ăn kẹo nên bốn anh em đã xin mẹ thêm một vài bịch keo khác giống nhu vậy nữa, nhưng me nhất quyết không cho vì sơ ăn nhiều keo sẽ bi sâu răng, do đó mẹ chỉ cho các câu ăn số kẹo trong bịch kia thôi. Thế là họ ngay lâp tức chia nhau số keo nói trên. Hỏi họ có tông công bao nhiêu cách chia keo ? (cho rằng 125 viên keo là giống hệt nhau, và anh em họ có quyền không ăn môt số viên keo trong số 125 viên keo ban đầu, đồng thời cũng có thể xảy ra trường họ có một nguròi không durọc chia viên keo nào). Tài liệu tham khảo.
1) Mỗi chiếc ghế có đúng một người ngồi;
2) Thứ tự ngồi của các cô gái, xét từ trái qua phải, là $G_1, G_2, G_3, G_4, G_5$ ;
3) Giữa $G_1$ và $G_2$ có ít nhất 3 chàng trai;
4) Giữa $G_4$ và $G_5$ có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai.
Hỏi có tất cả bao nhiêu cách xếp như vậy?
Bài 2. Tìm số nghiệm không âm của phương trình $x_1 + x_2 + x_3 + x_4 = 20$.
Bài 3. Có bao nhiêu số tự nhiên có 3 chữ số mà tổng các chữ số bằng 11 ?
Bài 4. Tìm số nghiệm nguyên của phương trình $x_1 + x_2 + x_3 + x_4 = 30$ nếu:
a) $x_i \geq 0 \forall i$.
b) $2 \leq x_1 \leq 7$, $x_i \geq 0, i = 2, 3, 4$.
c) $x_1 \geq -3, x_2 \geq -1, x_3, x_4 \geq 1$.
Bài 5. Tìm số nghiệm nguyên dương của phương trình $4x_1 + x_2 + x_3 +x_4 = 15$.
Bài 6. Có 4 viên bi vàng và 10 viên bi xanh. Hỏi có bao nhiêu cách sắp xếp các viên bi thỏa:
a) Không có bi vàng nào kề nhau.
b) Giữa hai bi vàng có ít nhất 2 bi xanh.