Tổ hợp lặp (có hoàn lại) là gì?
Tổ hợp lặp — còn gọi là tổ hợp multiset — cho biết số cách chọn r phần tử từ n loại khác nhau khi được phép lặp lại và không quan tâm đến thứ tự chọn. Khác với tổ hợp thông thường, ở đây cùng một phần tử có thể được chọn nhiều lần. Máy tính này tính số đó bằng công thức multiset \(C(n+r-1, r)\).
Cách sử dụng máy tính
Bạn nhập số loại phần tử khác nhau n (ví dụ: 5 vị kem) và số phần tử muốn chọn r (ví dụ: múc 3 viên kem). Công cụ sẽ trả về số multiset khác nhau — tức các lựa chọn chỉ khác nhau ở chỗ có những loại nào và mỗi loại xuất hiện bao nhiêu lần, bỏ qua thứ tự.
Giải thích công thức
Kết quả được tính theo
$$\overline{C}(n,r) = \binom{n+r-1}{r} = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$Cách hiểu trực quan là mô hình "sao và vạch" (stars and bars): đặt \(r\) ngôi sao giống hệt nhau vào \(n\) ô được ngăn cách bởi \(n-1\) vạch; mỗi cách sắp xếp tương ứng với một lựa chọn. Để tránh tràn số khi tính giai thừa, máy tính này tính hệ số nhị thức theo phương pháp nhân liên tiếp.
Ví dụ minh họa
Giả sử một tiệm kem có \(n = 5\) vị và bạn muốn một bát gồm \(r = 3\) viên, được phép lặp lại. Khi đó
$$C(5+3-1, 3) = C(7, 3) = \frac{7!}{3!\cdot 4!} = 35$$Vậy có tới 35 bát kem khác nhau mà bạn có thể tạo ra.
Câu hỏi thường gặp
Điều này 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 ở đây cùng một loại có thể được chọn nhiều lần.
r có thể lớn hơn n không? Có. Vì được phép lặp lại nên \(r\) có thể lớn hơn \(n\) — chẳng hạn chọn 10 viên kem từ 3 vị là hoàn toàn hợp lệ.
Nếu r bằng 0 thì sao? Không chọn gì sẽ có đúng 1 cách (multiset rỗng), nên kết quả là 1.
