TAILIEUCHUNG - Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 1 - Nguyễn Anh Thi

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ơ bản do Nguyễn Anh Thi biên soạn với các nội dung chính như: Nguyên lý đếm cơ bản, tổ hợp, tổ hợp lặp, khai triển luỹ thừa của đa thức,. | Bài giảng Toán học tổ hợp và Cấu trúc rời rạc Đại học Khoa học Tự nhiên, Tp HCM 2016 Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 1/40 Nội dung chương 1 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 Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 2/40 Các nguyên lý đếm cơ bản Nội dung 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 Bài giảng Toán học tổ hợp và Cấu trúc rời rạc 2016 3/40 Các nguyên lý đếm cơ bản Nguyên lý cộng 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 đó

• Toán học
• Bài giảng Toán học tổ hợp và cấu trúc rời rạc
• Toán học tổ hợp
• Cấu trúc rời rạc
• Tổ hợp cơ bản
• Khai triển luỹ thừa của đa thức
• Các bài toán về đường đi
• Đồ thị Hamilton
• Đồ thị Euler
• Đại cương về đồ thị
• Biểu diễn đồ thị
• Đẳng cấu đồ thị
• Một số kỹ thuật đếm
• Sử dụng sơ đồ Ven
• Nguyên lý bù trừ
• Cây khung ngắn nhất
• Cây có gốc
• Phương pháp đếm dùng hàm sinh
• Định nghĩa hàm sinh
• Hệ số hàm sinh
• Toán học rời rạc
• Tổ hợp căn bản
• Tổ hợp lặp
• Khai triển lũy thừa
• Khai triển đa thức
• Bài giảng Toán học tổ hợp
• Bài toán về đường đi
• Tìm đường đi ngắn nhất
• Hàm sinh mũ
• Kỹ thuật đếm
• Phép duyệt cây