Tổ hợp lặp

Tổ hợp lặp giống tổ hợp thông thường, chỉ khác là ta cho phép các phần tử của tập hợp cơ sở M được lặp lại.

Định nghĩa và công thức

Ta bắt đầu bằng một ví dụ dễ hình dung: bạn vào cửa hàng và muốn mua 12 chai nước để mang đi dã ngoại. Trên kệ có tất cả 4 loại nước khác nhau: nước cam, nước chanh, trà xanh và nước dừa. Có nhiều cách mua: chẳng hạn có thể mua 5 chai nước cam, 2 chai nước chanh, 1 chai trà xanh và 4 chai nước dừa, hoặc mua mỗi loại đúng 3 chai. Có tất cả bao nhiêu cách mua khác nhau để có đúng 12 chai?

Như vậy ta có tập hợp cơ sở M = {cam; chanh; trà; dừa} và hỏi: có bao nhiêu bộ k phần tử, với k = 12, gồm các phần tử của tập hợp M và không quan tâm đến thứ tự?

Xây dựng công thức ở đây phức tạp hơn so với các bài toán tổ hợp khác. Trước hết ta biểu diễn lần mua hàng thành một dãy các chữ số 0 và 1: số chữ số 1 bằng số chai đã mua của một loại, còn chữ số 0 dùng để ngăn cách các loại. Chẳng hạn dãy 111011101111101 cho biết ta đã mua 3 chai nước cam (3 chữ số 1 đầu tiên), rồi 3 chai nước chanh (0 là dấu ngăn cách, tiếp theo là 3 chữ số 1), rồi 5 chai trà xanh (0 ngăn cách, rồi 5 chữ số 1) và cuối cùng 1 chai nước dừa. Toàn bộ nguyên tắc được minh hoạ như sau:

$$\underset{\text{cam}}{\underbrace{111}}0\underset{\text{chanh}}{\underbrace{111}}0\underset{\text{trà}}{\underbrace{11111}}0\underset{\text{dừa}}{\underbrace{1}}$$

Nếu muốn mua 6 chai nước cam, 4 chai nước chanh, 2 chai nước dừa và không mua trà xanh thì dãy có dạng:

$$\underset{\text{cam}}{\underbrace{111111}}0\underset{\text{chanh}}{\underbrace{1111}}00\underset{\text{dừa}}{\underbrace{11}}$$

Để ý rằng độ dài của dãy này luôn bằng 15: phải có 12 chữ số 1 để mua tất cả 12 chai, và phải có 3 dấu ngăn cách để tách 4 loại nước khác nhau. Còn lại cần tính xem có tất cả bao nhiêu dãy độ dài 15 như vậy chứa đúng 3 chữ số 0.

Chỉ cần đếm số cách đặt các chữ số 0: mỗi khi đặt 3 chữ số 0 xen giữa 12 chữ số 1, ta được một cách mua hợp lệ. Nói cách khác: có tất cả 15 ô, và ta phải đặt chữ số 0 vào 3 ô trong đó. Các ô còn lại tự động được điền chữ số 1.

Đây đã là bài toán đơn giản về tổ hợp không lặp. Đánh số 15 ô bằng các số {1; …; 15}, rồi mỗi lần chọn từ tập hợp này một bộ 3 số, ta được 3 vị trí để đặt chữ số 0. Chẳng hạn với tổ hợp {2; 4; 7} ta được dãy: 101011011111111. Ở các vị trí thứ 2, thứ 4 và thứ 7 là chữ số 0, còn lại là chữ số 1. Như vậy có tất cả

$${\mathrm{C}}_{15}^3=455$$

cách khác nhau để đặt các chữ số 0 vào 15 ô, và do đó cũng có 455 cách khác nhau để mua 12 chai nước khi có 4 loại nước.

Có thể tổng quát hoá lập luận trên. Nếu có tập hợp M gồm n phần tử và ta chọn từ đó các bộ k phần tử, trong đó các phần tử có thể lặp lại, thì ta lập một dãy các chữ số 0 và 1 có độ dài n + k − 1 (k chữ số 1 và n − 1 chữ số 0) và tìm số cách đặt n − 1 chữ số 0. Vậy số tổ hợp lặp chập k của n phần tử bằng

$${\mathrm{C}}_{n+k-1}^{n-1}={\mathrm{C}}_{n+k-1}^k.$$

Phép biến đổi cuối cùng là nhờ các hệ thức cơ bản giữa các số tổ hợp.

Ví dụ có lời giải

1. Có bao nhiêu cách chia 20 vé mời xem buổi công chiếu một bộ phim cho 10 bà cụ? Đây là bài toán về tổ hợp lặp, vì một bà cụ có thể nhận nhiều vé, thậm chí tất cả các vé. Chỉ cần xác định đúng đâu là n, đâu là k. Thực chất ta chọn các tổ hợp chập 20 từ 10 bà cụ, nói cách khác ta lập một dãy các chữ số 0 và 1 có độ dài 29, gồm 20 chữ số 1 và 9 chữ số 0. Vậy n = 10, k = 20. Số tổ hợp lặp chập 20 của 10 phần tử là:

$${\mathrm{C}}_{10+20-1}^{20}=10.015.005.$$