Máy Tính Tổ Hợp Có Lặp (CR)
Tính CR(n,r) = C(n+r−1,r) — số cách chọn r phần tử từ n loại, được lặp lại, không quan tâm thứ tự — bằng phương pháp sao và vạch, kèm lời giải từng bước.
Cách dùng công cụ
Nhập n (số loại có sẵn) và r (số phần tử cần chọn). Công cụ trả về CR(n, r) — số cách chọn không thứ tự khi được phép lặp lại — kèm phép quy đổi sao-và-vạch về tổ hợp thường và lời giải từng bước.
Được lặp lại — điểm khác biệt cốt lõi so với nCr
Tổ hợp thường giả định mỗi phần tử chỉ được chọn tối đa một lần, nên không bao giờ vượt quá . Tổ hợp có lặp bỏ quy tắc đó: bạn có thể chọn cùng một loại nhiều lần, và thứ tự vẫn không quan trọng. Đó chính xác là cách gọi kem — không ai cấm bạn gọi hai viên cùng một vị.
Ví dụ đầy đủ — CR(5,3)
Có 35 cách khác nhau để chọn 3 viên kem từ 5 vị khi được phép trùng vị và thứ tự chọn không quan trọng.
Sao và vạch: vì sao CR(n,r) = C(n+r−1,r)
Hãy hình dung r phần tử cần chọn là r ngôi sao giống hệt nhau, dùng n − 1 vạch để chia thành n nhóm — mỗi nhóm ứng với một loại. Với CR(5,3), đó là 3 sao và 4 vạch xếp thành một hàng, ví dụ ★★|★||| nghĩa là "2 phần tử loại 1, 1 phần tử loại 2, 0 ở các loại còn lại." Mỗi cách sắp xếp khác nhau của 7 ký hiệu (3 sao + 4 vạch) tương ứng đúng một cách chọn — và việc chọn 3 trong 7 vị trí nào là sao chính là một tổ hợp thường: . Đó là toàn bộ mẹo: cho phép lặp biến bài toán đếm thành "có bao nhiêu cách đặt vạch giữa các sao" — một tổ hợp tiêu chuẩn.
Bốn cách lấy mẫu r phần tử từ n
Thứ tự có quan trọng không và có được lặp lại không — hai câu hỏi này quyết định công thức đếm. Có đúng bốn trường hợp:
| Thứ tự quan trọng | Không quan trọng | |
|---|---|---|
| Không lặp | Chỉnh hợp: | Tổ hợp: |
| Có lặp |
Công cụ này xử lý ô dưới-phải — thứ tự không quan trọng và được lặp lại. Đây là một trong hai trường hợp (cùng với chỉnh hợp có lặp) mà r được phép lớn hơn n, vì bạn không bao giờ cạn loại để dùng lại.
Các ví dụ thường gặp
- 3 viên kem từ 5 vị, được trùng vị: .
- 3 loại trái cây từ 4 loại ở chợ, được trùng loại: .
- 2 loại topping từ 3 loại, được chọn gấp đôi: .
Cả ba ví dụ đều cùng một dạng: một cách chọn không thứ tự mà một loại có thể được chọn nhiều lần, quy đổi về tổ hợp thường bằng phương pháp sao và vạch.
Câu hỏi thường gặp
- CR(5,3) bằng bao nhiêu và vì sao bằng C(7,3)?
- CR(5,3) đếm số cách chọn không thứ tự 3 phần tử từ 5 loại, được lặp lại. Phương pháp sao và vạch quy đổi bài toán này về một tổ hợp thường: , nên .
- 'Tổ hợp có lặp' nghĩa là gì?
- Nghĩa là bạn chọn r phần tử từ n loại, thứ tự không quan trọng, và cùng một loại có thể được chọn nhiều lần — như chọn 3 viên kem từ 5 vị, được phép chọn trùng vị.
- Tổ hợp có lặp khác tổ hợp thường (nCr) ở điểm nào?
- Tổ hợp thường giả định mỗi phần tử chỉ được chọn tối đa một lần, nên không bao giờ vượt quá . Tổ hợp có lặp bỏ giới hạn đó: một loại có thể lặp lại, nên có thể lớn hơn — chọn 10 viên kem chỉ từ 3 vị vẫn là một cách chọn hợp lệ.
- Phương pháp 'sao và vạch' (stars and bars) là gì?
- Sao và vạch biểu diễn một cách chọn bằng r ngôi sao giống hệt nhau (các phần tử), ngăn cách bởi n − 1 vạch thành n nhóm (các loại). Mỗi cách sắp xếp trong n + r − 1 ký hiệu, chọn r vị trí nào là sao, tương ứng đúng một cách chọn có lặp — đó là lý do .
- Vì sao CR(n,r) bằng C(n+r−1,r)?
- Vì cách sắp xếp sao-và-vạch có tổng cộng n + r − 1 vị trí ký hiệu, và việc chọn r vị trí nào trong số đó là sao (thay vì vạch) xác định trọn vẹn cách chọn — đó chính là một phép chọn không thứ tự r vị trí từ n + r − 1, tức .
- Ví dụ thực tế nào dùng tổ hợp có lặp?
- Chọn r viên kem từ n vị (được trùng vị), chọn r loại trái cây từ n loại ở chợ (được trùng loại), hoặc chọn r loại topping từ n loại mà vẫn được chọn gấp đôi một loại — tất cả đều tính bằng .
- CR(n,0) bằng bao nhiêu?
- Chọn 0 phần tử chỉ có đúng một kết quả — cách chọn rỗng — nên với mọi . Khớp với công thức: .