Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng Toán rời rạc: Chương 4 Đếm các phần tử cung cấp cho người học những kiến thức như: Cơ sở của phép đếm; Nguyên lý chuồng chim bồ câu; Chỉnh hợp và tổ hợp; Các hệ số nhị thức; Chỉnh hợp và tổ hợp suy rộng; Sinh các hoán vị và tổ hợp. Mời các bạn cùng tham khảo để nắm chi tiết nội dung của bài giảng! | CHƯƠNG 4 ĐẾM CÁC PHẦN TỬ Nguyễn Quỳnh Diệp diepnq@tlu.edu.vn File Bài giảng goo.gl Y3cpLF hoặc goo.gl TYxXQD 1 Nguyễn Quỳnh Diệp NỘI DUNG Cơ sở của phép đếm Nguyên lý chuồng chim bồ câu Chỉnh hợp và tổ hợp Các hệ số nhị thức Chỉnh hợp và tổ hợp suy rộng Sinh các hoán vị và tổ hợp Toán rời rạc Nguyễn Quỳnh Diệp 2 4.1. CƠ SỞ CỦA PHÉP ĐẾM Toán rời rạc Nguyễn Quỳnh Diệp 3 CƠ SỞ CỦA PHÉP ĐẾM Giả định rằng ta có một tập các đối tượng cùng với thuộc tính của nó Phép đếm là xác định số lượng các đối tượng đó Các nguyên lí đếm cơ bản Quy tắc nhân Quy tắc cộng Toán rời rạc Nguyễn Quỳnh Diệp 4 CƠ SỞ CỦA PHÉP ĐẾM QUY TẮC NHÂN Giả sử một thủ tục nào đó được tách ra thành một dãy hai nhiệm vụ. Nếu có n1 để làm nhiệm vụ thứ nhất và n2 cách để làm nhiệm vụ thứ hai sau khi nhiệm vụ thứ nhất đã được hoàn thành thì sẽ có n1.n2 cách thực hiện thủ tục này Ví dụ 1 Có bao nhiêu xâu nhị phân có độ dài 7 Ví dụ 2 Có nhiều nhất bao nhiêu biển đăng kí ô tô nếu mỗi biển chứa một dãy ba chữ cái và tiếp sau là ba chữ số Toán rời rạc Nguyễn Quỳnh Diệp 5 CƠ SỞ CỦA PHÉP ĐẾM QUY TẮC CỘNG Giả sử có hai nhiệm vụ. Nhiệm vụ thứ nhất có thể được thực hiện bằng n1 cách nhiệm vụ thứ hai có thể thực hiện bằng n2 cách và nếu hai việc này không thể làm đồng thời thì sẽ có n1 n2 cách làm một trong hai nhiệm vụ đó. Ví dụ 1 Để đi từ thành phố A đến thành phố B có thể đi bằng tàu xe ô tô hoặc đi máy bay. Có 12 chuyến máy bay từ A tới B có 5 chuyến tàu và 10 chuyến ô tô. Hỏi có bao nhiêu lựa chọn để đi từ A đến B Toán rời rạc Nguyễn Quỳnh Diệp 6 NHỮNG BÀI TOÁN PHỨC TẠP HƠN Những bài toán phức tạp có thể giải được nếu sử dụng kết hợp cả hai quy tắc nhân và quy tắc cộng Ví dụ 1 Mật khẩu để đăng nhập máy tính Dài từ 6 đến 8 kí tự Mỗi kí tự là 1 chữ cái Hỏi có thể có bao nhiêu mật khẩu Toán rời rạc Nguyễn Quỳnh Diệp 7 NGUYÊN LÝ BÙ TRỪ Nguyên lý bù trừ Khi hai nhiệm vụ làm đồng thời Cộng số cách làm từng nhiệm vụ Trừ đi số cách làm đồng thời cả hai nhiệm vụ Theo ngôn ngữ tập hợp Cho A1 A2 là các tập hợp khi đó 1 2 1 2
