Bài toán chia kẹo hỏi: có bao nhiêu cách chia n viên kẹo giống nhau cho k em bé, nếu em nào cũng có thể không được viên nào? Đáp số là tổ hợp chập k − 1 của n + k − 1, viết C(n + k − 1, k − 1). Chia 10 viên cho 3 em có C(12, 2) = 66 cách. Cùng công thức đó đếm số nghiệm nguyên không âm của phương trình x1 + x2 + … + xk = n, và số cách chọn n món từ k loại khi được chọn lặp, gọi là tổ hợp lặp.
Phép chứng minh đẹp nhất dùng hình sao và vạch, tiếng Anh gọi là stars and bars, ở đây gọi là phương pháp vách ngăn. Bài giải thích phương pháp, cách xử lý ràng buộc “mỗi em ít nhất một viên” và “không em nào quá mấy viên”, đặt tổ hợp lặp cạnh ba kiểu đếm quen thuộc, và chỉ ra những chỗ AI hay đếm sai.
Phương pháp vách ngăn: biến phép chia thành việc chọn chỗ
Xếp 10 viên kẹo thành một hàng, mỗi viên là một ngôi sao. Để chia cho 3 em, đặt 2 vách ngăn vào hàng: phần trước vách thứ nhất là của em thứ nhất, phần giữa hai vách là của em thứ hai, phần sau vách thứ hai là của em thứ ba. Chuỗi ★★★|★★★★★|★★ nghĩa là chia 3, 5, 2. Chuỗi |★★★★★★★★★★|, với hai vách đứng ở đầu và cuối, nghĩa là em giữa nhận cả 10 viên, hai em kia không có viên nào.
Mỗi cách chia ứng với đúng một chuỗi gồm 10 sao và 2 vách, và ngược lại mỗi chuỗi như vậy cho đúng một cách chia. Đây là một song ánh, nên số cách chia bằng số chuỗi. Chuỗi dài 12 ký hiệu, chỉ cần chọn 2 vị trí làm vách, các vị trí còn lại tự động là sao. Số cách chọn 2 vị trí trong 12 là C(12, 2) = 12 nhân 11 chia 2 = 66.
Tổng quát với n viên và k em: chuỗi có n sao và k − 1 vách, dài n + k − 1, chọn k − 1 vị trí làm vách, được C(n + k − 1, k − 1). Do tính đối xứng của tổ hợp, con số này cũng bằng C(n + k − 1, n), tức chọn vị trí cho các ngôi sao. Hai cách viết cho cùng kết quả; giáo trình dùng cách nào cũng được, miễn bạn nhớ tổng số ký hiệu là n + k − 1, không phải n + k. Lệch một đơn vị ở chỗ này là lỗi hay gặp nhất của dạng bài.
Ràng buộc “mỗi em ít nhất một viên”: dịch biến trước khi đếm
Khi đề yêu cầu em nào cũng có kẹo, đừng áp công thức ngay mà biến đổi bài về dạng không ràng buộc. Quy trình bốn bước, dùng tiếp ví dụ 10 viên cho 3 em:
- Đặt yi = xi − 1 cho mỗi em, tức phát trước cho mỗi em một viên. Khi đó yi nhận giá trị từ 0 trở lên.
- Tính số kẹo còn lại: 10 − 3 = 7 viên, phương trình mới là y1 + y2 + y3 = 7 với các yi không âm.
- Áp công thức vách ngăn: C(7 + 2, 2) = C(9, 2) = 36 cách.
- Kiểm bằng cách nhìn thứ hai: đặt 2 vách vào 9 khe giữa 10 ngôi sao, mỗi khe nhiều nhất một vách, thì không phần nào rỗng. Số cách chọn 2 khe trong 9 là C(9, 2) = 36, khớp kết quả trên.
Công thức tổng quát cho trường hợp mỗi người ít nhất một là C(n − 1, k − 1). Mẹo dịch biến dùng được cho mọi cận dưới: nếu em thứ nhất phải có ít nhất 3 viên, phát trước cho em ấy 3 viên rồi chia phần còn lại không ràng buộc. Với n = 10, k = 3 và x1 ≥ 3, còn 7 viên chia cho 3 em, được C(9, 2) = 36 cách.
Con số trùng với kết quả bên trên là tình cờ, hai bài khác nhau: một bài phát trước 3 viên cho ba em, bài kia phát trước 3 viên cho một em. Đừng để sự trùng số làm bạn tưởng hai đề là một; đây cũng là kiểu chỗ AI hay nhầm, vì nó thấy con số quen rồi ghép sai bài.
Ràng buộc chặn trên: khi nào cần nguyên lý bù trừ
Cận trên khó hơn cận dưới, vì không dịch biến được. Bài mẫu: chia 10 viên cho 3 em, em thứ nhất nhiều nhất 3 viên. Cách làm là đếm phần bù: lấy tất cả các cách chia trừ đi những cách vi phạm, tức em thứ nhất có từ 4 viên trở lên. Tổng số cách không ràng buộc là 66. Số cách vi phạm: phát trước 4 viên cho em thứ nhất, còn 6 viên chia tự do, được C(8, 2) = 28. Kết quả 66 − 28 = 38.
Kiểm lại bằng đếm trực tiếp, đáng làm một lần để tin phương pháp: nếu em thứ nhất nhận 0 viên, hai em còn lại chia 10 viên có 11 cách; nhận 1 viên, còn 9 viên có 10 cách; nhận 2 viên có 9 cách; nhận 3 viên có 8 cách. Tổng 11 + 10 + 9 + 8 = 38, khớp.
Khi nhiều em cùng bị chặn trên, các trường hợp vi phạm chồng lên nhau và phép trừ đơn giản sẽ trừ hai lần. Lúc đó cần nguyên lý bù trừ: trừ các trường hợp vi phạm từng điều kiện, cộng lại các trường hợp vi phạm đồng thời hai điều kiện, và cứ thế xen kẽ. Ví dụ: chia 10 viên cho 3 em, em nào cũng nhiều nhất 4 viên. Số cách để một em cụ thể nhận từ 5 viên trở lên là C(7, 2) = 21; để hai em cụ thể cùng nhận từ 5 viên trở lên thì hết sạch kẹo, chỉ 1 cách. Kết quả 66 − 3 nhân 21 + 3 nhân 1 = 6. Kiểm nhanh: ba số từ 0 đến 4 có tổng 10 là các hoán vị của (4, 4, 2) và (4, 3, 3), mỗi bộ 3 hoán vị, đúng 6 cách.
Bốn kiểu đếm: có thứ tự hay không, có lặp hay không
Tổ hợp lặp là ô thứ tư của một bảng mà sinh viên hay chỉ thuộc ba ô. Câu hỏi phân loại luôn gồm hai câu: thứ tự có quan trọng không, và một món có được chọn nhiều lần không. Ví dụ dùng chung: chọn 2 lần từ 3 vị trà A, B, C.
| Kiểu đếm | Thứ tự | Lặp | Công thức chọn k từ n | Với n = 3, k = 2 |
|---|---|---|---|---|
| Chỉnh hợp lặp | Có | Có | n mũ k | 9: AA, AB, AC, BA, BB, BC, CA, CB, CC |
| Chỉnh hợp | Có | Không | n! / (n − k)! | 6: AB, AC, BA, BC, CA, CB |
| Tổ hợp | Không | Không | C(n, k) = n! / (k! (n − k)!) | 3: AB, AC, BC |
| Tổ hợp lặp | Không | Có | C(n + k − 1, k) | 6: AA, BB, CC, AB, AC, BC |
Chú ý cách đặt tên biến: trong bảng, n là số loại và k là số lần chọn, nên công thức tổ hợp lặp viết C(n + k − 1, k). Trong bài chia kẹo ở đầu, vai trò đảo lại: kẹo là thứ được phân, em bé là loại. Lẫn vai trò hai biến là lỗi số một của dạng bài này. Cách tránh: luôn viết ra “cái gì là sao, cái gì là vách” trước khi thay số.
Ví dụ giả định để luyện phân loại: một quán bán 5 vị trà, nhóm bạn gọi 4 ly và chỉ quan tâm mỗi vị bao nhiêu ly. Thứ tự không quan trọng, một vị được gọi nhiều ly, nên là tổ hợp lặp: C(5 + 4 − 1, 4) = C(8, 4) = 70 cách gọi.
Những bài trông khác nhưng cùng một khuôn
Sức mạnh của phương pháp vách ngăn là nhận ra cùng một cấu trúc trong nhiều đề bề ngoài rất khác. Các dạng dưới đều quy về đếm nghiệm nguyên của một phương trình tổng.
- Đếm số hạng của khai triển. Khai triển (a + b + c) mũ 4 có bao nhiêu số hạng khác nhau sau khi rút gọn? Mỗi số hạng có dạng a mũ i nhân b mũ j nhân c mũ l với i + j + l = 4, nên có C(6, 2) = 15 số hạng.
- Số có tổng chữ số cho trước. Có bao nhiêu số tự nhiên từ 0 đến 999 có tổng chữ số bằng 5? Viết mỗi số thành ba chữ số, thêm số 0 ở đầu nếu cần, rồi đếm nghiệm của d1 + d2 + d3 = 5 với mỗi chữ số từ 0 đến 9. Vì 5 nhỏ hơn 10 nên ràng buộc chữ số không bao giờ bị vi phạm, đáp số C(7, 2) = 21. Với tổng bằng 12 thì phải dùng bù trừ, vì khi đó một chữ số có thể vượt 9.
- Dãy không giảm. Số dãy không giảm độ dài k gồm các số lấy từ 1 đến n bằng số tổ hợp lặp chập k của n, vì một dãy không giảm được xác định hoàn toàn bởi số lần xuất hiện của mỗi giá trị.
- Phân phối tài nguyên. Chia 8 ca trực giống nhau cho 4 người trong tuần, ví dụ giả định, mỗi người ít nhất một ca: C(7, 3) = 35 cách, xét theo số ca của mỗi người.
Điểm chung của các dạng trên: các đơn vị được chia giống hệt nhau. Nếu các viên kẹo khác nhau, hoặc các ca trực khác ngày khác giờ, bài toán đổi hẳn sang dạng đếm hàm từ tập kẹo tới tập em bé, đáp số là k mũ n chứ không còn là tổ hợp lặp. Câu hỏi “các đơn vị có phân biệt không” vì vậy phải được trả lời trước tiên.
Dùng AI kiểm bài đếm: ba lớp kiểm độc lập
Bài đếm là nơi chatbot sai nhiều và sai khó thấy: lời giải trôi chảy, công thức đúng tên, chỉ lệch một đơn vị ở chỗ n + k − 1 hoặc quên rằng kẹo giống nhau. Đừng tin một nguồn duy nhất; kiểm theo ba lớp.
- Lớp một, tự phân loại trước khi hỏi: viết ra các đơn vị có giống nhau không, người nhận có phân biệt không, có cận dưới hay cận trên không. Câu lệnh mẫu: “Đây là cách mình phân loại bài đếm này và công thức mình định dùng. Chỉ nhận xét phân loại đúng hay sai, chưa tính.”
- Lớp hai, thu nhỏ bài toán: thay 10 viên bằng 3 viên, liệt kê tay hết các cách, so với công thức. Bài nhỏ đúng thì mới tin bài lớn.
- Lớp ba, đếm bằng máy: nhờ AI viết một đoạn chương trình ngắn duyệt mọi bộ số và đếm, chạy trên máy của bạn, đối chiếu với đáp số công thức. Đọc đoạn chương trình trước khi chạy để chắc nó duyệt đúng miền giá trị.
- Khi hai kết quả lệch nhau, hỏi AI giải thích độ lệch thay vì hỏi đáp án đúng. Thường độ lệch chỉ ra đúng trường hợp bị đếm hai lần hoặc bị bỏ sót.
Ba lớp kiểm tốn chừng mười phút cho một bài, nhưng đó là mười phút luyện đúng kỹ năng mà bài đếm muốn kiểm tra: nhìn ra cấu trúc. Với bài nộp lấy điểm, trình bày lời giải bằng lập luận của bạn, chương trình chỉ để tự kiểm.
Câu hỏi thường gặp
Vì sao gọi là tổ hợp lặp mà không phải chỉnh hợp lặp?
Vì thứ tự không quan trọng: gọi hai ly vị A và một ly vị B là một cách, dù ghi A trước hay B trước. Chỉnh hợp lặp thì phân biệt thứ tự, ví dụ mật khẩu ba ký tự AAB khác ABA. Phân biệt hai khái niệm bằng một câu hỏi: đổi chỗ các lựa chọn có ra một kết quả mới không.
Công thức chia kẹo có dùng được khi số kẹo ít hơn số em bé không?
Có, khi cho phép em bé không nhận viên nào. Chia 2 viên cho 4 em có C(5, 3) = 10 cách: hoặc một em nhận cả 2 viên, có 4 cách, hoặc hai em mỗi em một viên, có 6 cách. Nếu đòi mỗi em ít nhất một viên thì không có cách nào, và công thức C(n − 1, k − 1) cũng cho kết quả 0.
Phương pháp vách ngăn có dùng được khi các em bé không phân biệt không?
Không trực tiếp. Khi người nhận cũng giống nhau, các cách chia 3, 5, 2 và 5, 2, 3 bị coi là một, và bài toán trở thành đếm số cách phân hoạch một số nguyên thành tổng các số hạng. Đây là bài toán khó hơn nhiều, không có công thức tổ hợp đơn giản, thường giải bằng hệ thức truy hồi hoặc hàm sinh.
Có cách nào nhớ công thức C(n + k − 1, k − 1) mà không học vẹt?
Nhớ hình ảnh chứ đừng nhớ công thức: n ngôi sao và k − 1 vách xếp thành một hàng, tổng cộng n + k − 1 ký hiệu, chọn chỗ cho các vách. Mỗi lần cần, vẽ một hàng sao nhỏ là tự suy ra công thức trong vài giây, kể cả khi đề đổi tên biến.
Tổ hợp lặp có liên quan gì tới xác suất không?
Có, nhưng cần cẩn thận. Các cách chia trong bài chia kẹo không đồng khả năng nếu kẹo được phát ngẫu nhiên từng viên: cách chia 10, 0, 0 hiếm hơn nhiều so với 4, 3, 3. Muốn tính xác suất trong trường hợp đó phải coi các viên kẹo là phân biệt. Đây là chỗ sai kinh điển khi chuyển từ đếm sang xác suất.