🍭 Câu 3 · 1 điểm
Tổ hợp lặp
Bài toán chia kẹo
Trọng tâm là phương trình nghiệm nguyên không âm. Nắm 1 công thức + kỹ thuật đặt ẩn phụ là giải được mọi biến thể.
Công thức cốt lõi
Tổ hợp lặp chập k từ n phần tử
$$\bar{C}_n^k = C_{n+k-1}^k = \frac{(n+k-1)!}{k!\,(n-1)!}$$
$n$ = số loại phần tử (= số biến) | $k$ = tổng số lần chọn (= tổng tổng)
Ý nghĩa thực tế
Bài toán "Chia kẹo cho trẻ em"
Số cách phân $k$ vật (không phân biệt, nhận lặp) vào $n$ hộp (phân biệt) = $\bar{C}_n^k$.
Tương đương số nghiệm nguyên không âm của $x_1 + x_2 + \cdots + x_n = k$.
Kỹ thuật đặt ẩn phụ — Xử lý điều kiện biên
Điều kiện $x_i \geq a_i$
1
Đặt $y_i = x_i - a_i \geq 0$ (ẩn phụ)
2
Phương trình mới: $y_1 + \cdots + y_n = k - \sum a_i$
3
Áp dụng công thức $\bar{C}_n^{k'}$ với $k' = k - \sum a_i$
Điều kiện $x_i \leq b_i$
1
Dùng Bổ sung: $N_{\text{thỏa}} = N_{\text{tổng}} - N_{\text{vi phạm}}$
2
$N_{\text{vi phạm}}$: $x_i \geq b_i+1$, đặt $y_i = x_i - (b_i+1)$
3
Trừ đi số nghiệm vi phạm từng điều kiện (Inclusion-Exclusion nếu nhiều điều kiện)
⚡ Thứ tự giải quyết bài tổ hợp lặp
1️⃣ Viết lại bài dưới dạng phương trình $x_1 + x_2 + \cdots + x_n = k$
2️⃣ Chuyển mọi điều kiện về dạng $y_i \geq 0$ bằng đặt ẩn phụ
3️⃣ Tính $k'$ sau khi trừ phần shift
4️⃣ Áp công thức $C_{n+k'-1}^{k'}$ (hoặc $C_{n+k'-1}^{n-1}$, hai cái bằng nhau)
5️⃣ Nếu có điều kiện chặn trên → dùng bổ sung.
2️⃣ Chuyển mọi điều kiện về dạng $y_i \geq 0$ bằng đặt ẩn phụ
3️⃣ Tính $k'$ sau khi trừ phần shift
4️⃣ Áp công thức $C_{n+k'-1}^{k'}$ (hoặc $C_{n+k'-1}^{n-1}$, hai cái bằng nhau)
5️⃣ Nếu có điều kiện chặn trên → dùng bổ sung.
✏️ Ví dụ mẫu
Đề bài
Tìm số nghiệm nguyên không âm của phương trình $x_1 + x_2 + x_3 = 10$.
Bài giải
$n = 3$ biến, $k = 10$Xác định n, k
Số nghiệm = $\bar{C}_3^{10} = C_{3+10-1}^{10} = C_{12}^{10}$Công thức tổ hợp lặp
$= C_{12}^{2} = \dfrac{12!}{2! \cdot 10!} = \dfrac{12 \times 11}{2} = 66$$C_{12}^{10} = C_{12}^{2}$
→ Có 66 nghiệm nguyên không âm. □
Đề bài
Tìm số nghiệm nguyên của $x_1 + x_2 + x_3 = 10$ với $x_1 \geq 2,\, x_2 \geq 3,\, x_3 \geq 0$.
Bài giải — Kỹ thuật đặt ẩn phụ
Đặt: $y_1 = x_1 - 2 \geq 0$, $y_2 = x_2 - 3 \geq 0$, $y_3 = x_3 \geq 0$Đặt ẩn phụ
Phương trình mới: $(y_1+2)+(y_2+3)+y_3 = 10$Thế vào
$\Rightarrow y_1 + y_2 + y_3 = 10 - 2 - 3 = 5$Thu gọn
Số nghiệm $= \bar{C}_3^5 = C_{3+5-1}^5 = C_7^5 = C_7^2$Công thức tổ hợp lặp
$= \dfrac{7 \times 6}{2} = 21$Kết quả
→ Có 21 nghiệm. □
Đề bài
Tìm số nghiệm nguyên không âm của $x_1 + x_2 + x_3 = 10$ với $x_1 \leq 4$.
Bài giải — Kỹ thuật bổ sung
$N$ = Tổng số nghiệm không có ràng buộc $= C_{12}^{10} = 66$Không điều kiện
$A$ = tập nghiệm vi phạm $x_1 \geq 5$Xác định vi phạm
Đặt $y_1 = x_1 - 5$: $y_1 + x_2 + x_3 = 5$ → $|A| = C_7^5 = 21$Đặt ẩn phụ
Số nghiệm thỏa = $N - |A| = 66 - 21$Bổ sung
$= 45$Kết quả
→ Có 45 nghiệm. □