Tổ hợp lặp là gì?
Tổ hợp lặp đếm số cách chọn r phần tử từ n loại khác nhau khi bạn được phép chọn cùng một loại nhiều lần và thứ tự lấy ra không quan trọng. Đại lượng này thường được ký hiệu là nHr và còn gọi là hệ số đa tập (multiset coefficient). Nó trả lời những câu hỏi kiểu như: "Nếu có 4 vị kem và tôi lấy 2 viên với điều kiện cho phép trùng vị, thì có bao nhiêu cách kết hợp khác nhau?"
Cách dùng máy tính này
Nhập số loại khác nhau n (tối thiểu bằng 1) và số phần tử bạn muốn chọn r (bằng 0 trở lên). Nhấn tính toán và công cụ sẽ trả về nHr, chính là số đa tập (multiset) khác nhau. Cả hai ô nhập đều là số nguyên không âm thông thường; không có đơn vị nào cần quy đổi.
Giải thích công thức
Đẳng thức cốt lõi là $$\overline{C}(n,r) = \binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r! \cdot (n - 1)!}$$ Mẹo ở đây: xếp \(r\) phần tử được chọn cùng với \((n - 1)\) vách ngăn giữa các loại sẽ cho ta \(n + r - 1\) vị trí, và ta chỉ cần chọn xem đặt các phần tử (hoặc vách ngăn) vào đâu. Để tránh phải tính những giai thừa khổng lồ, máy tính này tính hệ số nhị thức bằng một vòng lặp nhân ổn định: nhân với \((m - k + i)\) rồi chia cho \(i\) với \(i = 1..k\), trong đó \(m = n + r - 1\) và \(k = \min(r, n - 1)\).
Ví dụ minh họa
Với giá trị mặc định \(n = 4\), \(r = 2\): $$\overline{C}(4,2) = \binom{4 + 2 - 1}{2} = \binom{5}{2} = \frac{5 \cdot 4}{2 \cdot 1} = 10$$ Mười tổ hợp từ các loại {a, b, c, d} là: aa, ab, ac, ad, bb, bc, bd, cc, cd, dd.
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, nên mỗi phần tử chỉ được chọn tối đa một lần; còn ở đây cho phép lặp lại, nên số lượng sẽ lớn hơn.
Nếu \(r = 0\) thì sao? Khi đó có đúng một tổ hợp: chính là tập rỗng (không chọn gì cả), nên \(nHr = 1\).
Nếu \(n = 1\) thì sao? Khi chỉ có một loại, bạn buộc phải chọn nó \(r\) lần, nên chỉ có đúng một đa tập và \(nHr = 1\) với mọi giá trị \(r\).
