PHÂN BIỆT CÁC BÀI TOÁN CHIA ĐỒ VẬT TRONG TỔ HỢP
Bài toán nào thì dùng chia kẹo Euler, bài toán nào thì không đây là phần nhiều bạn sẽ nhầm lẫn- phải chú ý rất kĩ.
1. Bài toán chia kẹo Euler (Stars and Bars)
Đồ vật: giống nhau
Hộp: khác nhau (có nhãn)
Mô hình:
x₁ + x₂ + ... + xₖ = n
Công thức:
Không điều kiện:
C(n + k - 1, k - 1)
Mỗi hộp ≥ 1:
C(n - 1, k - 1)
Ví dụ:
Chia 10 viên kẹo cho 3 người → áp dụng Euler
2. Chia đồ vật khác nhau vào hộp giống nhau
Đồ vật: khác nhau
Hộp: giống nhau
Đặc điểm:
Không dùng công thức đơn giản
Phải loại trùng do hộp giống nhau
Cách làm:
Liệt kê
Hoặc dùng phân hoạch tập hợp (Bell number)
Ví dụ:
Chia A, B, C vào 2 nhóm giống nhau
→ {A,B} | {C} giống {C} | {A,B}
3. Chia đồ vật giống nhau vào hộp khác nhau
Đồ vật: giống nhau
Hộp: khác nhau
→ Chính là bài toán Euler
4. Chia đồ vật giống nhau vào hộp giống nhau
Đồ vật: giống nhau
Hộp: giống nhau
Bản chất:
→ Phân tích số n thành tổng k số không âm (không phân biệt thứ tự)
Ví dụ:
Chia 5 viên kẹo vào 3 hộp giống nhau
Các cách:
5 + 0 + 0
4 + 1 + 0
3 + 2 + 0
3 + 1 + 1
2 + 2 + 1
Đặc điểm:
Không có công thức tổ hợp đơn giản
Dùng lý thuyết phân hoạch số
5. Bảng so sánh nhanh
Loại bài Đồ vật Hộp Phương pháp
Euler Giống nhau Khác nhau Stars and Bars
Phân hoạch tập Khác nhau Giống nhau Bell / chia TH
Phân phối đầy đủ Khác nhau Khác nhau k^n
Phân hoạch số Giống nhau Giống nhau Liệt kê / partition
6. Cách nhận dạng nhanh
Bước 1: Xét đồ vật
Có phân biệt không?
Bước 2: Xét hộp
Có phân biệt không?
Kết luận nhanh:
Giống + khác → Euler
Khác + giống → Phân hoạch tập
Giống + giống → Phân hoạch số
Khác + khác → k^n
