Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2009 Toán rời rạc 1 Nội dung Chương 0. Mở đầu Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp Toán rời rạc 2 Chương 1. BÀI TOÁN ĐẾM 1. 2. 3. 4. 5. Nguyên lý cộng và nguyên lý nhân Các cấu hình tổ hợp cơ bản Nguyên lý bù trừ Công thức đệ qui Hàm sinh Toán rời rạc 3 1. Nguyên lý cộng và Nguyên lý nhân ⚫ Đây là hai nguyên lý cơ bản của tổ hợp, được vận dụng rộng rãi vào việc giải quyết các bài toán đếm ⚫ Còn gọi là Qui tắc cộng và Qui tắc nhân (Sum Rule và Product Rule) Toán rời rạc 4 1.1. Nguyên lý cộng (The sum rule) ⚫ NÕu A vµ B lµ hai tËp hîp rêi nhau th× N(A  B) = N(A) + N(B). ⚫ Nguyªn lý céng ®îc më réng cho nhiÒu tËp con rêi nhau: NÕu A1, A2, ..., Ak lµ mét ph©n ho¹ch cña tËp hîp X th× N(X) = N(A1) + N(A2) + ... + N(Ak). ⚫ Mét trêng hîp riªng hay dïng cña nguyªn lý céng: NÕu A lµ mét tÝnh chÊt cho trªn tËp X th× N(A) = N(X) - N(Ac). N ( A) = N ( X) − N ( A) Toán rời rạc 5 Nguyên lý cộng: Ví dụ ⚫ Ví dụ 1. Một đoàn vận động viên gồm 2 môn bắn súng và bơi được cử đi thi đấu ở nước ngoài. Nam có 10 người. Số vận động viên thi bắn súng (kể cả nam và nữ) là 14. Số nữ vận động viên thi bơi bằng số nam vận động viên thi bắn súng. Hỏi toàn đoàn có bao nhiêu người? ⚫ Giải: Chia đoàn thành 2 lớp: nam và nữ. Lớp nữ lại được chia 2: thi bắn súng và thi bơi. Thay số nữ thi bơi bằng số nam thi bắn súng (2 số này bằng nhau theo đầu bài), ta được số nữ bằng tổng số đấu thủ thi bắn súng. Từ đó, theo nguyên lý cộng, toàn đoàn có 10 + 14 = 24 người. Toán rời rạc 6 Nguyên lý cộng: Ví dụ ⚫ Ví dụ 2. Trong một đợt phổ biến đề tài tốt nghiệp, Ban chủ nhiệm Khoa công bố danh sách các đề tài bao gồm 80 đề tài về chủ đề "xây dựng hệ thông tin quản lý", 10 đề tài về chủ đề "thiết kế phần mềm dạy học" và 10 đề tài về chủ đề "Hệ chuyên gia". Hỏi một sinh viên có bao nhiêu khả năng lựa chọn đề tài? ⚫ Giải: Sinh viên có thể lựa