Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc: Bài 4 - Vũ Thương Huyền

Bài giảng Toán rời rạc: Bài 4 - Vũ Thương Huyền cung cấp cho học viên các kiến thức về đếm các phần tử; cơ sở của phép đếm; nguyên lý chuồng chim bồ câu; nguyên lí Dirichlet tổng quát; 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 chi tiết nội dung bài giảng! | BÀI 4 ĐẾM CÁC PHẦN TỬ Vũ Thương Huyền huyenvt@tlu.edu.vn 1 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 huyenvt@tlu.edu.vn 2 4.1 CƠ SỞ CỦA PHÉP ĐẾM Toán rời rạc huyenvt@tlu.edu.vn 3 4.1 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 huyenvt@tlu.edu.vn 4 4.1 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 số 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 huyenvt@tlu.edu.vn 5 4.1 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 huyenvt@tlu.edu.vn 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à chữ cái hoa hoặc số Mỗi mật khẩu chứa ít nhất một chữ số Hỏi có thể có bao nhiêu mật khẩu Toán rời rạc huyenvt@tlu.edu.vn 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 1 2 Ví