Máy tính tổ hợp lặp

Tiệm kem có 8 vị kem và bạn muốn mua 3 viên kem. Có thể chọn 3 vị khác nhau, 2 viên sô-cô-la và 1 viên vị trà xanh, hoặc cả 3 viên vị vani. Thứ tự không quan trọng: ốc quế có viên sô-cô-la ở trên cùng vẫn là cùng một phần kem. Có bao nhiêu khả năng? Đó chính là bài toán tổ hợp lặp: có bao nhiêu cách chọn k món từ n loại, khi các loại được phép lặp lại.

Nếu các loại không được lặp lại thì đó là tổ hợp thông thường, và chỉ cần dùng máy tính số tổ hợp.

Cách tính

Số tổ hợp lặp chập k của n phần tử tính theo công thức

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

Hình dung 3 viên kem từ 8 vị như một hàng gồm 3 hình tròn và 7 vách ngăn phân chia các vị. Các hình tròn trước vách ngăn thứ nhất là vị vani, giữa vách thứ nhất và thứ hai là sô-cô-la, và cứ thế tiếp tục. Mỗi cách chọn kem ứng với đúng một cách sắp xếp như vậy, nên chỉ cần đếm số cách chọn 3 vị trí cho các hình tròn trong 10 vị trí:

$${\mathrm{C}}_{8+3-1}^3={\mathrm{C}}_{10}^3=\frac{10\cdot 9\cdot 8}{3\cdot 2\cdot 1}=120$$

Có 120 cách chọn 3 viên kem từ 8 vị. Cách suy ra công thức chi tiết, với một ví dụ khác, có trong bài Tổ hợp lặp.