Tổ hợp lặp là gì?
Tổ hợp lặp, trong tiếng Anh thường gọi là "multichoose", là số cách chọn r phần tử từ n loại khác nhau khi thứ tự chọn không quan trọng và bạn được phép chọn cùng một loại nhiều lần. Mỗi kết quả là một bội tập (multiset). Ví dụ, khi chọn 2 viên kem từ 3 hương vị mà được phép trùng nhau, ta có những cách chọn như {vani, vani} hay {vani, sô-cô-la}.
Cách dùng công cụ
Nhập n là số loại (hoặc đối tượng) khác nhau để chọn, và r là số phần tử bạn muốn lấy ra. Cả hai phải là số nguyên không âm. Nhấn "Tính toán", công cụ sẽ trả về \(C^R(n,r)\), tức số bội tập khác nhau có kích thước \(r\).
Giải thích công thức
Kết quả bằng hệ số nhị thức \(C(n + r - 1, r)\), khai triển thành $$C^R(n, r) = \binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$ Đây chính là kết quả kinh điển theo phương pháp "sao và vách ngăn" (stars and bars): phân phối \(r\) ngôi sao giống nhau vào \(n\) ngăn được tách bởi \(n - 1\) vách. Để tránh tràn số khi tính giai thừa, công cụ nhân dần tích đang có với \((n - 1 + i)\) rồi chia cho \(i\), với \(i\) chạy từ 1 đến \(r\): $$C^R(n,r) = \prod_{i=1}^{r} \frac{n - 1 + i}{i}$$
Ví dụ minh họa
Với \(n = 10\) và \(r = 3\): $$C^R(10,3) = C(12,3) = \frac{12 \times 11 \times 10}{3 \times 2 \times 1} = \frac{1320}{6} = 220$$ Vậy có 220 cách chọn 3 phần tử từ 10 loại khi được phép lặp lại.
Câu hỏi thường gặp
Khác gì so với tổ hợp thông thường? Tổ hợp thông thường \(C(n,r)\) không cho phép lặp lại; còn tổ hợp lặp cho phép chọn cùng một phần tử nhiều lần, nên kết quả thường lớn hơn.
Nếu r = 0 thì sao? Chỉ có đúng một cách để "không chọn gì cả", nên \(C^R(n,0) = 1\) với mọi \(n \geq 1\).
Nếu n = 0 thì sao? Khi không có loại nào và \(r > 0\), kết quả là 0; riêng trường hợp rỗng \(n = 0, r = 0\) được quy ước bằng 1.
