Bài giảng Toán tổ hợp: Chương 1 - Nguyễn Anh Thi

Bài giảng "Toán tổ hợp - Chương 1: Tổ hợp cơ 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. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán tổ hợp: Chương 1 - Nguyễn Anh ThiBài giảng Toán tổ hợpĐại học Khoa học Tự nhiên, Tp HCM2017Bài giảng Toán tổ hợp20171/40Nội dung chương 1Nội dungChương 1.Tổ hợp cơ bản1. Nguyên lý đếm cơ bản2. Tổ hợp3. Tổ hợp lặp4. Khai triển lũy thừa của đa thứcBài giảng Toán tổ hợp20172/40Các nguyên lý đếm cơ bảnNội dungCác nguyên lý đếm cơ bản1Nguyên lý cộng2Nguyên lý nhân3Nguyên lý DerichletBài giảng Toán tổ hợp20173/40Các nguyên lý đếm cơ bảnNguyên lý cộngNguyên lý cộngGiả 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áchcá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ậphợ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 |.Bài giảng Toán tổ hợp20174/40Các nguyên lý đếm cơ bảnNguyên lý nhânNguyên lý nhânGiả 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ọncách thực hiện cho T1 ta có n2 cách thực hiện T2 , v.v. . . cho đến cuốicùng, sau khi chọn cách thực hiện các công việc T1 , T2 , ..., Tk−1 ta có nkcách thực hiện Tk . Vậy ta có cách để thực hiện thủ tục này là:n1 × n2 × ... × nkVí dụ.Hỏi có nhiêu cách đi từ A đến C?Đáp án. 3 × 2 = 6 cách.Bài giảng Toán tổ hợp20175/40