Máy Tính Tổ Hợp Lặp

Máy Tính Tổ Hợp Lặp

Phổ biến AI Skill PRO

Nhập phép tính

Công thức

CR(n,r)=(n+r−1)!r!(n−1)!C^{R}(n,r) = \frac{(\text{n} + \text{r} - 1)!}{\text{r}!\,(\text{n} - 1)!}
Thống kê sử dụng

Quảng cáo

Kết quả

Số tổ hợp có lặp
70
Tổng số loại phần tử (n) 5
Số phần tử cần chọn (r) 4

Báo lỗi nội dung trang này

Công Cụ Này Làm Gì

Máy Tính Tổ Hợp Lặp giúp bạn đếm 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ự lựa chọn. Đây là một công thức nền tảng trong tổ hợp và xác suất, thường được gọi là bài toán "chia kẹo Euler" hay phương pháp "ngôi sao và vách ngăn" (stars and bars). Vì mỗi loại có thể được chọn nhiều lần nên kết quả luôn lớn hơn so với tổ hợp thông thường không lặp.

Chọn phần tử từ ba loại với lặp lại được phép, tạo thành một đa tập
Tổ hợp có lặp cho phép chọn cùng một loại phần tử nhiều hơn một lần.

Các Giá Trị Bạn Cần Nhập

  • Tổng số loại phần tử (n): số nhóm khác nhau mà bạn có thể chọn — ví dụ 3 vị kem.
  • Số phần tử cần chọn (r): tổng số lần bạn chọn, trong đó cùng một loại có thể được chọn lặp lại nhiều lần.

Hãy nhập cả hai giá trị dưới dạng số nguyên, và máy tính sẽ lập tức trả về một kết quả duy nhất: số bội tổ hợp (multiset) khác nhau — tức các cách chọn không xét thứ tự nhưng cho phép lặp.

Công Thức

Công cụ áp dụng công thức tổ hợp lặp chuẩn:

$$C^{R}(n,r) = \frac{(\text{n} + \text{r} - 1)!}{\text{r}!\,(\text{n} - 1)!}$$

Bên trong, máy tính tính ba giai thừa — \((n + r - 1)!\), \(r!\) và \((n - 1)!\) — rồi chia theo công thức trên. Vì sử dụng giai thừa chính xác với phép tính trên số nguyên, kết quả là một số nguyên chính xác chứ không phải giá trị xấp xỉ.

Quảng cáo
Cách sắp xếp sao và vạch biểu diễn tổ hợp có lặp
Phương pháp sao và vạch giải thích vì sao số lượng bằng \(C(n+r-1, r)\).

Ví Dụ Minh Họa

Giả sử một quán kem có n = 3 vị và bạn muốn một ly gồm r = 2 viên kem, trong đó được phép chọn trùng vị. Thay n = 3 và r = 2 vào công thức:

  • \(n + r - 1 = 3 + 2 - 1 = 4\)
  • $$C(4, 2) = \frac{4!}{2! \cdot 2!} = \frac{24}{2 \cdot 2} = \mathbf{6}$$

Vậy có 6 cách tạo ly kem hai viên: AA, BB, CC, AB, AC và BC. Máy tính trả về 6 ngay lập tức.

Thêm các ví dụ đã được xử lý

Mỗi ví dụ dưới đây sử dụng cùng một định danh, \(C^{R}(n,r) = \binom{n+r-1}{r} = \frac{(n+r-1)!}{r!\,(n-1)!}\), trong đó \(n\) là số loại vật phẩm riêng biệt có sẵn và \(r\) là số vật phẩm được chọn. Thứ tự không quan trọng và mỗi loại có thể được sử dụng lại, vì vậy mỗi kết quả là một tập hợp đa tập.

Ví dụ 1 — Ba xúc xắc giống hệt nhau (n = 6, r = 3)

Bạn lăn ba xúc xắc sáu mặt không phân biệt được và chỉ ghi lại tập hợp các mặt hiển thị (vì vậy 1-3-6 và 6-3-1 được tính là cùng một kết quả). Có \(n = 6\) loại mặt và \(r = 3\) lần lựa chọn, với lặp lại được phép vì hai xúc xắc có thể hiển thị cùng một mặt.

Chỉ số trên: \(n + r - 1 = 6 + 3 - 1 = 8\).

$$C^{R}(6,3) = \binom{8}{3} = \frac{8!}{3!\,5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56$$

Vì vậy có 56 kết hợp mặt không có thứ tự riêng biệt. Lưu ý rằng con số này ít hơn nhiều so với \(6^3 = 216\) lần lăn có thứ tự — 216 kết quả có thứ tự sụp đổ thành 56 tập hợp đa tập, nhưng không đều đặn (một bộ ba như 4-4-4 có một thứ tự, trong khi 1-3-6 có sáu), đó chính xác là lý do tại sao xác suất tổng xúc xắc phải được tính từ 216 lần lăn có thứ tự chứ không phải từ 56 tập hợp đa tập.

Ví dụ 2 — Nhiều muỗng hơn hương vị (n = 3, r = 5)

Một cửa hàng kem cung cấp 3 hương vị và bạn đặt một hộp 5 muỗng; các muỗng cùng hương vị được phép và thứ tự chúng được đóng gói không quan trọng. Ở đây \(r = 5\) lớn hơn \(n = 3\), điều này là không thể cho các kết hợp mà không có sự thay thế nhưng hoàn toàn ổn ở đây.

Chỉ số trên: \(n + r - 1 = 3 + 5 - 1 = 7\).

$$C^{R}(3,5) = \binom{7}{5} = \frac{7!}{5!\,2!} = \frac{7 \times 6}{2 \times 1} = \frac{42}{2} = 21$$

Có 21 hộp có thể. Hủy \(5!\) thay vì \(2!\) là phím tắt ở đây: vì \(\binom{7}{5} = \binom{7}{2}\), chỉ có hai thừa số tử số sống sót. Theo thuật ngữ ngôi sao và thanh, bạn đang đặt 5 ngôi sao (muỗng) và \(n - 1 = 2\) thanh (các chia nhỏ hương vị) trong 7 khe — ví dụ \(\star\star\,|\,\star\,|\,\star\star\) có nghĩa là 2 vani, 1 sôcôla, 2 dâu.

Ví dụ 3 — Hai trường hợp biên (r = 1 và n = 1)

Chọn một vật phẩm (n = 4, r = 1). Bạn chọn một thức uống duy nhất từ 4 kích thước. Chỉ có một lần chọn, sự lặp lại không bao giờ xảy ra, vì vậy câu trả lời phải đơn giản là số loại:

$$C^{R}(4,1) = \binom{4+1-1}{1} = \binom{4}{1} = \frac{4!}{1!\,3!} = \frac{4}{1} = 4$$

điều này cho 4 kết quả — cột \(r = 1\) của bất kỳ bảng nào như vậy luôn chỉ là \(n\).

Chỉ một loại (n = 1, r = 7). Một máy bán hàng tự động cung cấp một sản phẩm duy nhất và bạn mua 7 đơn vị:

$$C^{R}(1,7) = \binom{1+7-1}{7} = \binom{7}{7} = \frac{7!}{7!\,0!} = \frac{5040}{5040 \times 1} = 1$$

Có chính xác một tập hợp đa tập — "bảy của điều duy nhất có sẵn" — vì chỉ có một loại, không còn lựa chọn nào để đưa ra. Chính thức \(n - 1 = 0\) thanh được yêu cầu, tất cả 7 vị trí phải là ngôi sao, và \(\binom{7}{7} = 1\). Cùng một logic làm cho \(C^{R}(n,0) = 1\) cho bất kỳ \(n\): chọn không là một lựa chọn hợp lệ (trống rỗng), đó là lý do tại sao \(0! = 1\) là quy ước giữ cho công thức nhất quán.

Bảng tham khảo kết hợp với thay thế

Giá trị chính xác của \(C^{R}(n,r) = \binom{n+r-1}{r}\) cho 1–8 loại vật phẩm được chọn 1–6 lần. Đọc xuống số loại \(n\) của bạn, sau đó sang số lần chọn \(r\).

Số lượng lựa chọn không có thứ tự với sự lặp lại được phép
n (loại) r = 1 r = 2 r = 3 r = 4 r = 5 r = 6
1 1 1 1 1 1 1
2 2 3 4 5 6 7
3 3 6 10 15 21 28
4 4 10 20 35 56 84
5 5 15 35 70 126 210
6 6 21 56 126 252 462
7 7 28 84 210 462 924
8 8 36 120 330 792 1716

Cách đọc các mẫu

  • Mỗi hàng là một đường chéo của tam giác Pascal. Hàng \(n = 1\) là dãy hằng của 1, hàng \(n = 2\) là các số tự nhiên \(2, 3, 4, \dots\), hàng \(n = 3\) là các số tam giác \(3, 6, 10, 15, 21, 28\), và hàng \(n = 4\) là các số tứ diện \(4, 10, 20, 35, 56, 84\). Đây đơn giản là \(\binom{n+r-1}{r}\) được truy tìm dọc theo \(n\) cố định.
  • Bảng đối xứng dưới sự dịch chuyển. Vì \(\binom{n+r-1}{r} = \binom{n+r-1}{n-1}\), chúng ta nhận được \(C^{R}(n,r) = C^{R}(r+1,\,n-1)\). Ví dụ \(C^{R}(6,3) = 56 = C^{R}(4,5)\), và \(C^{R}(8,3) = 120 = C^{R}(4,7)\). Hoán đổi vai trò của "loại" và "lựa chọn" theo cách này thường biến một phép nhân dài thành một phép nhân ngắn.
  • Tăng trưởng là đa thức trong r, bậc n − 1. Giữ \(n\) cố định, \(C^{R}(n,r) = \frac{(r+1)(r+2)\cdots(r+n-1)}{(n-1)!}\), một đa thức bậc \(n-1\) — tuyến tính cho \(n = 2\), bậc hai cho \(n = 3\), bậc ba cho \(n = 4\). Giữ \(r\) cố định và tăng \(n\) hoạt động theo cách tương tự với các vai trò bị đảo ngược (bậc \(r\) trong \(n\)). Dù bằng cách nào, các số lượng vẫn nằm xa dưới số lượng \(n^{r}\) của các lựa chọn có thứ tự với sự lặp lại.
  • Mỗi mục là tổng của mục phía trên nó và mục ở bên trái nó (nơi cả hai tồn tại): \(C^{R}(n,r) = C^{R}(n-1,r) + C^{R}(n,r-1)\). Kiểm tra \(126 = 70 + 56\) trong ô \(n = 6\), \(r = 4\). Sự tái phát đó là một cách nhanh để mở rộng bảng bằng tay.
Quảng cáo

Cách tính toán nó bằng tay

Hình ảnh ngôi sao và thanh

Trước khi tính toán, sẽ giúp ích nếu xem tại sao công thức có hình dạng đó. Biểu diễn một lựa chọn dưới dạng \(r\) ngôi sao giống hệt nhau (các vật phẩm bạn lấy) được tách thành \(n\) nhóm bằng \(n-1\) thanh (các chia nhỏ giữa các loại vật phẩm liên tiếp). Số ngôi sao trong nhóm \(i\) là số bản sao của loại \(i\) bạn đã chọn. Mỗi sắp xếp của \(r\) ngôi sao và \(n-1\) thanh tương ứng với chính xác một lựa chọn hợp lệ, và có \(r + (n-1) = n + r - 1\) vị trí trong hàng. Tính số lượng lựa chọn do đó có nghĩa là chọn \(r\) vị trí trong \(n+r-1\) vị trí đó giữ ngôi sao:

$$C^{R}(n,r) = \binom{n+r-1}{r} = \binom{n+r-1}{n-1}$$

Ví dụ với \(n = 4\) loại và \(r = 5\) lần chọn, hàng \(\star\,|\,|\,\star\star\star\,|\,\star\) có 8 vị trí và có nghĩa là 1 loại A, không có loại B, 3 loại C, 1 loại D.

Thủ tục từng bước

  1. Kiểm tra các đầu vào. Xác nhận rằng \(n\) và \(r\) là các số nguyên với \(n \ge 1\) và \(r \ge 0\). Không giống như các kết hợp mà không có sự thay thế, \(r\) có thể vượt quá \(n\) — sự lặp lại được phép, vì vậy không có giới hạn trên cho \(r\).
  2. Tính chỉ số trên. Tính toán \(N = n + r - 1\). Đây là tổng số vị trí ngôi sao và thanh.
  3. Viết nhị thức. \(C^{R}(n,r) = \dbinom{N}{r} = \dfrac{N!}{r!\,(n-1)!}\). Không bao giờ khai triển các giai thừa này đầy đủ — \(N!\) phát nổ nhanh chóng và tất cả các số lớn đều bị hủy bỏ.
  4. Hủy \((n-1)!\) chống lại \(N!\). Vì \(N - r = n - 1\), thương số \(N!/(n-1)!\) để lại chính xác \(r\) thừa số giảm dần trong tử số:
$$C^{R}(n,r) = \frac{(n+r-1)(n+r-2)\cdots(n)}{r!}$$
  1. Nhân các số hạng tử số \(r\), sau đó chia cho \(r!\). Nếu \(r\) lớn hơn \(n-1\), trước tiên sử dụng tính đối xứng \(\binom{N}{r} = \binom{N}{n-1}\) để bạn nhân số thừa số nhỏ hơn thay thế.
  2. Kiểm tra sự hợp lý rằng kết quả là một số nguyên. Một hệ số nhị thức luôn là một số nguyên, vì vậy bất kỳ phân số còn lại hoặc dư lượng nào có nghĩa là một sai số trong phép tính. Hai kiểm tra nhanh hơn: \(r = 1\) phải cho chính xác \(n\), và \(n = 1\) phải cho chính xác 1.

Chạy qua công việc (n = 5, r = 4)

Bốn muỗng sữa chua đông lạnh từ 5 lớp phủ, cho phép lặp lại, thứ tự không liên quan.

  • Bước 2: \(N = 5 + 4 - 1 = 8\).
  • Bước 3: \(C^{R}(5,4) = \dfrac{8!}{4!\,4!}\).
  • Bước 4: hủy \((n-1)! = 4!\), để lại \(r = 4\) thừa số giảm dần từ 8 xuống \(n = 5\): \(\dfrac{8 \times 7 \times 6 \times 5}{4!}\).
  • Bước 5: \(\dfrac{1680}{24} = 70\).
  • Bước 6: 70 là một số nguyên, và nó khớp với ô \(n = 5\), \(r = 4\) của bảng tham khảo ở trên.

Câu trả lời là 70 kết hợp lớp phủ riên biệt. Một sự tương phản hữu ích: các đầu vào tương tự cho \(5^4 = 625\) nếu thứ tự quan trọng, và chỉ \(\binom{5}{4} = 5\) nếu lặp lại bị cấm — vì vậy hãy luôn quyết định xem thứ tự và lặp lại có áp dụng hay không trước khi chọn công thức.

Câu Hỏi Thường Gặp

Cách này khác gì so với tổ hợp thông thường? Tổ hợp thường, \(C(n, r)\), không cho phép lặp — mỗi phần tử chỉ được chọn tối đa một lần. Tổ hợp lặp cho phép chọn cùng một loại nhiều lần, vì vậy ta chuyển sang công thức \(C(n + r - 1, r)\).

Thứ tự có quan trọng không? Không. AB và BA được tính là cùng một cách chọn. Nếu thứ tự có ý nghĩa, bạn sẽ phải dùng chỉnh hợp (hoán vị) thay vì tổ hợp.

r có thể lớn hơn n không? Có. Vì được phép lặp lại nên bạn hoàn toàn có thể chọn nhiều phần tử hơn số loại hiện có — ví dụ chọn 5 viên kem từ 3 vị là hợp lệ và cho ra kết quả lớn hơn.

Cập nhật lần cuối:

Phổ biến nhất trong Toán học và Thống kê

Xem tất cả máy tính Toán học và Thống kê