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}$
Chứng minh
Mỗi ánh xạ $p$ ta cho tương ứng với một dãy nhị phân độ dài $n+k-1$, trong đó $p(a_1)$ chữ số đầu là 0, tiếp theo là số 1, rồi $p(a_2)$ chữ số $0$,…cuối cùng là $p(a_k)$ chữ số $0$. Ví dụ bộ $VVSTT$ ứng với dãy $0010100$.
Rõ ràng đây là tương ứng 1 – 1, do đó số ánh xạ $p$ bằng số dãy nhị phân, do đó ta chỉ cần đếm số dãy nhị phân.
Ta thấy dãy có $n+k-1$ chữ số trong đó có $k-1$ chữ số $1$, do đó số dãy nhị phân chỉ là số cách chọn vị trí cho $k-1$ chữ số $1$ nên số dãy nhị phân là $C^{k-1}_{n+k-1}$.
Do đó số ánh xạ $p$ là $C^{k-1}_{n+k-1} $
Trở lại bài toán trên, ta thấy số món quà có 5 cái là một tổ hợp lặp chập 5 của sách, viết, tập, do đó số món quà có thể là $C^{2}_{5+2-1} = C^2_6 = 15$.
(Chú ý trong bài toán trên, đảm bảo số mỗi loại sản phẩm có không ít hơn 5 cái).
Bài toán 1. (Chia kẹo Euler). Cho $n$ viên kẹo giống nhau đem chia cho $k$ người, hỏi có bao nhiều cách chia.
Ta gọi $k$ người là $a_1, a_2, \cdots a_k$, với mỗi cách chia kẹo là một multiset của $A$ mà $p(a_1) + p(a_2)+\cdots +p(a_k) = n$.
Do đó số cách chia kẹo 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.
Giải
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}$.
(Phần 2)
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$.
Giải
a) $x_1 + x_2 + x_3 + x_4 + x_5 = 30$, $x_i \geq 2 \forall i = \overline{1,5}$. (1). Ta đi tìm số nghiệm của hệ (1).
Để đưa về bài toán gốc, ta đặt ẩn phụ như sau: $y_i = x_i – 1 \geq 1$ với mọi $i = \overline{1,5}$.
Khi đó ta có $y_1 +1 + y_2+1 + y_3 + 1 + y_4 + 1 + y_5 + 1 = 30 \Leftrightarrow y_1+y_2+y_3+y_4+y_5 = 25$ với $y_i \geq 1$. (2)
Một bộ nghiệm của (2) cho tương ứng một bộ nghiệm thỏa (1), mà số nghiệm của $(2)$ là $C_{24}^{4}$ (Theo bài toán chia kẹo Euler), do đó số nghiệm của (1) là $C_{24}^{4}$.
b) Tương tự câu a, đặt $y_1 = x_1 – 3, y_2 = x_2 – 3, y_3 = x_3 – 5, y_4= x_4-5, y_5 = x_5 – 5$, từ (1) ta có phương trình $y_1+y_2+y_3+y_4+y_5 = 9$ và $y_i \geq 1$. Số nghiệm là $C_8^4$.
c) Xét $x_5 = 1, 2$ và đặt ẩn phụ $y_i = x_i-3$ ta có đáp số là: $C_{16}^3 + C_{15}^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$.
Giải
Đặt $x_{11} = 2020 – (x_1+x_2+\cdots + x_{10}) $ thì $x_{11} \geq 1$.
Khi đó ta có phương trình $x_1 + \cdots + x_{11} = 2020$ và $x_i \geq 1$.
Do đó số nghiệm là $C_{2019}^{10}$.
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$.
Giải
Đặt $y_1 = x_1, y_2 = x_2 – x_1 \geq 0$, $y_2 = x_3-x_2 \geq 0$, …, $y_{11} = 2020 -x_{10} \geq 0$.
Khi đó $y_1 + y_2 + \cdots +y_{11} = 2020$ với $y_i \geq 0$. (2)
Với một bộ nghiệm của (2) sẽ tương ứng duy nhất một bộ $(x_1, x_2, …, x_{10})$ thỏa đề bài.
Số nghiệm của (2) là $C_{2030}^{10}$, đó cũng chính là số bộ $(x_1, x_2, …, x_{10})$ thỏa đề bài.
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 :
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?
Giải
Đánh số thứ tự các ghế từ trái sang phải là $1,2, \ldots, 17$.
Gọi $x_{1}$ là số chàng trai được xếp bên trái $G_{1}, x_{2}$ là số chàng trai ở giũa $G_{1}$ và $G_{2}, x_{3}$ là số chàng trai ở giữa $G_{2}$ và $G_{3}, x_{4}$ là số chàng trai ở giữa $G_{3}$ và $G_{4}, x_{5}$ là số chàng trai ở giữa $G_{4}$ và $G_{5}, x_{6}$ là số chàng trai được xếp ở bên phải $G_5$. Khi đó bộ số $\left(x_{1}, x_{2}, \ldots, x_{6}\right)$ hoàn toàn xác định vị trí các cô gái và ta có:
1) $x_{1}+x_{2}+\cdots+x_{6}=12$
2) $3 \leq x_{2}$.
3) $1 \leq x_{5} \leq 4$
Đổi biến $y_{2}=x_{2}-3$ và $y_{5}=x_{5}-1$ ta được $x_{1}+y_{2}+x_{3}+x_{4}+y_{5}+x_{6}=8$ với các $\hat{\text {ẩn}}$ không âm và có thêm điều kiện $y_{5} \leq 3$. Tiếp theo, sử dụng bài toán chia kẹo của Euler ở dạng $x_{1}+y_{2}+x_{3}+x_{4}+x_{6}=8-y_{5}$ ta được đáp số (phần phân ghế cho các cô gái) là $C_{12}^{4}+C_{11}^{4}+C_{10}^{4}+C_{9}^{4}=1161$.
Vì còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số cách xếp thỏa mãn yêu cầu bài toán là $1161 \cdot 12 !$
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$.
Giải
- Trước hết ta chứng minh $d = a+b+c$ bằng phản chứng.
- Khi dó $ 3 \leq d \leq 2015$, với mỗi $d$ thì số bộ $(a,b,c)$ là $C_{d-1}^2$.
- Do đó số bộ thỏa đề bài là $C_2^2 + C_3^2 + \cdots + C_{2014}^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 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.
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.
- Jiri-herman-radan-kucera-jaromir-simsa, Counting-and-configurations-problems-in-combinatorics-arithmetic-and-geometry
- Chuyên đề toán học 11 - Tập san của học sinh Trường Phổ thông Năng khiếu.
