Bài giảng "Toán học tổ hợp và cấu trúc rời rạc - Chương 1: Tổ hợp căn bản" cung cấp cho người học các kiến thức: Nguyên lý đếm cơ bản, tổ hợp, tổ hợp lặp, khai triển lũy thừa của đa thức. | TOÁN HỌC TỔ HỢP VÀ CẤU TRÚC RỜI RẠC Chương 1 TỔ HỢP CƠ BẢN lvluyen@ http cautrucroirac FB cautrucroirac Đại học Khoa Học Tự Nhiên Tp. Hồ Chí Minh https tailieudientucntt lvluyen@ Chương 1. Tổ hợp cơ bản 09 2016 1 40 Nội dung Chương 1. TỔ HỢP CƠ BẢN 1. Nguyên lý đếm cơ bản 2. Tổ hợp 3. Tổ hợp lặp 4. Khai triển lũy thừa của đa thức https tailieudientucntt lvluyen@ Chương 1. Tổ hợp cơ bản 09 2016 2 40 . Các nguyên lý đếm cơ bản 1 Nguyên lý cộng 2 Nguyên lý nhân 3 Nguyên lý Derichlet https tailieudientucntt lvluyen@ Chương 1. Tổ hợp cơ bản 09 2016 3 40 . Nguyên lý cộng Giả sử ta phải thực hiện một công việc bằng cách chọn một trong k sự chọn lựa các phương pháp khác nhau T1 T2 . Tk . Để thực hiện Ti 1 i k ta có ni cách. Vậy ta số cách thực hiện công việc trên là n1 n2 nk . Ví dụ. Một sinh viên có thể chọn một đề tài từ một trong 3 danh sách các đề tài. Số đề tài trong các danh sách đề tài lần lượt là 23 15 19. Hỏi sinh viên có bao nhiêu cách chọn một đề tài Đáp án. 23 15 19 57 cách. Nhận xét. Quy tắc cộng có thể phát biểu dưới dạng của ngôn ngữ tập hợp Nếu A1 A2 . . . Ak là các tập hợp đôi một rời nhau khi đó A1 A2 . . . Ak A1 A2 . . . Ak . https tailieudientucntt lvluyen@ Chương 1. Tổ hợp cơ bản 09 2016 4 40 . Nguyên lý nhân Giả sử một thủ tục bao gồm k công việc kế tiếp nhau T1 T2 . . . Tk . Nếu công việc T1 có thể được thực hiện theo n1 cách và sau khi chọn cách thực hiện cho T1 ta có n2 cách thực hiện T2 . . . cho đến cuối cùng sau khi chọn cách thực hiện các công việc T1 T2 . Tk 1 ta có nk cách thực hiện Tk . Vậy ta có cách để thực hiện thủ tục này là n1 n2 . nk Ví dụ. Hỏi có nhiêu cách đi từ A đến C Đáp án. 3 2 6 cách. https tailieudientucntt lvluyen@ Chương 1. Tổ hợp cơ bản 09 2016 5 40 Nhận xét. Quy tắc nhân có thể phát biểu dưới dạng của ngôn ngữ tập hợp Nếu A1 A2 . . . Ak là các tập .
