Bài giảng Toán học tổ hợp - Chương 4: Tổ hợp cơ bản cung cấp cho người học những kiến thức như: Các nguyên lý đếm cơ bản; Tổ hợp; Tổ hợp lặp. Mời các bạn cùng tham khảo! | TOÁN HỌC TỔ HỢP Chương 4 TỔ HỢP CƠ BẢN Đại học Khoa Học Tự nhiên Tp. Hồ Chí Minh Chương 4. Tổ hợp cơ bản O LVL c 2020 1 39 Nội dung Chương 4. TỔ HỢP CƠ BẢN 4. Các nguyên lý đếm cơ bản 4. Tổ hợp 4. Tổ hợp lặp Chương 4. Tổ hợp cơ bản O LVL c 2020 2 39 . 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ý Dirichlet Chương 4. Tổ hợp cơ bản O LVL c 2020 3 39 . Nguyên lý cộng Giả sử ta muốn thực hiện việc X bằng cách chọn một trong k phương pháp T1 T2 . . . Tk khác nhau. Với mỗi phương pháp Ti 1 i k ta có ni cách thực hiện việc X. Như vậy số cách thực hiện việc X là n1 n2 nk . Ví dụ. Một sinh viên 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 lần lượt là 23 15 và 19. Hỏi sinh viên có bao nhiêu cách chọn đề 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ữu hạn đôi một rời nhau thì A1 A2 . . . Ak A1 A2 . . . Ak . Chương 4. Tổ hợp cơ bản O LVL c 2020 4 39 . Nguyên lý nhân Giả sử muốn thực hiện thủ tục X ta phải thực hiện k việc X1 X2 . . . Xk liên tiếp nhau. Nếu mỗi việc Xi 1 i k có ni cách thực hiện thì số cách thực hiện thủ tục X 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. Chương 4. Tổ hợp cơ bản O LVL c 2020 5 39 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 hữu hạn thì A1 A2 . . . Ak A1 A2 . . . Ak . Ví dụ. Có bao nhiêu chuỗi bit có độ dài 8 Giải. Mỗi bit có 2 cách chọn 0 hoặc 1. Để tạo ra một chuỗi bit có độ dài 8 ta lần lượt chọn giá trị cho 8 bit. Theo nguyên lý nhân ta có số chuỗi bit có độ dài 8 là 28 256. Ví dụ. Cho tập A gồm 6 phần tử và tập B gồm 10 phần tử. Hỏi a Có bao nhiêu ánh xạ từ A vào B b Có bao nhiêu đơn ánh từ A vào B Giải. a Với mỗi phần tử x của A ta có 10 cách chọn ảnh vì B có 10 phần tử . Để tạo ra một ánh xạ từ A vào B ta lần lượt chọn ảnh của 6 phần tử của A. Theo nguyên lý nhân ta có 106 ánh xạ từ A vào B. .
