Bài giảng Toán rời rạc: Chương 3 - TS. Đặng Xuân Thọ

Bài giảng Toán rời rạc: Chương 3 Một số công thức tổ hợp cung cấp cho người học những kiến thức như: Đánh giá số điện thoại nhiều nhất có thể có trong Hà Nội; Xác định số mật khẩu, mỗi mật khẩu gồm sáu, bảy, hoặc tám ký tự; mỗi ký tự có thể chữ hoặc số; mỗi mật khẩu chứa ít nhất một chữ; Một số công thức tổ hợp;...Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Chương 3 - TS. Đặng Xuân Thọ TOÁN RỜI RẠC(DISCRETE MATHEMATICS) Bùi Thị Thủy Đặng Xuân Thọ Support2  Full name: Đặng Xuân Thọ  Mobile: 091.2629.383  Email: thodx@hnue.edu.vn  Website: http://cs.fit.hnue.edu.vn/~tho/ Toán Rời Rạc - ĐHSPHN NỘI DUNG3  Chương 1. Logic mệnh đề  Chương 2. Lý thuyết tập hợp  Chương 3. Một số công thức tổ hợp  Chương 4. Suy luận và kiểm chứng chương trình  Chương 5. Đại số Boole và cấu trúc mạch logic  Chương 6. Thuật toán  Chương 7. Lý thuyết đồ thị Toán Rời Rạc - ĐHSPHN Chương 3. Một số công thức tổ hợp4  “Đánh giá số điện thoại nhiều nhất có thể có trong Hà Nội.”  “Xác định số mật khẩu, mỗi mật khẩu gồm sáu, bảy, hoặc tám ký tự; mỗi ký tự có thể chữ hoặc số; mỗi mật khẩu chứa ít nhất một chữ.”  Một số công thức tổ hợp  Chỉnh hợp  Hoán vị  Hoán vị trên đường tròn … Toán Rời Rạc - ĐHSPHN5 Cơ sở của phép đếm Toán Rời Rạc - ĐHSPHN Cơ sở của phép đếm6  Phần này chúng ta chỉ giải quyết xác định lực lượng của tập hợp hữu hạn.  Nếu tập hợp A là tập hợp hữu hạn, thì lực lượng của nó là số lượng phần tử của nó, ký hiệu là ? .  Định lý: Nếu Ai (i=1,2,..n) là một phân hoạch của tập hợp A thì ta có ??=1 ?? = ? . Toán Rời Rạc - ĐHSPHN Số phần tử của tích Đêcac7  Ví dụ: Cho tập hợp A={a,b}. Tìm tất cả các dãy ký tự có ba phần tử được tạo thành từ A?  aaa, aab, bbb, bba, abb, baa, aba, bab  Định lý: cho trước các tập hợp hữu hạn Ai (i=1,..,k) trong đó tập hợp Ai có đúng ni phần tử. Khi đó tích Đêcac A1 x A2 x … x Ak có đúng n1n2…nk phần tử. Nghĩa là: ?1 × ?2 × ⋯ × ?? = ?1 × ?2 × ??  Đặc biệt ta có: ?? = ? ? Toán Rời Rạc - ĐHSPHN Số phần tử của tích Đêcac8  Ví dụ: Có bao nhiêu số tự nhiên có chín chữ số mà trong biểu diễn thập phân của nó không có mặt chữ số nào trong tập hợp {0,3,7,9}?  Mỗi số tự nhiên có chín chữ số không được viết bởi các chữ số {0,3,7,9} là một dãy chín kí tự có lặp của tập hợp {1,2,4,5,6,8}.  69 Toán Rời Rạc - ĐHSPHN9 Hai nguyên lý cơ bản Toán Rời Rạc - ĐHSPHN Cơ sở của phép đếm (1/2)10  Nguyên lý cộng  Giả sử có các công đoạn E1, E2,…, Ek. Để thực hiện E ta chỉ cần thực hiện một trong những Ei (i = 1..k) trong đó số cách thực hiện Ei là ni. Khi đó số cách thực hiện E là n1 + n2 + …+ nk.  Ví dụ: 3 hãng hàng không 2 hãng tàu thủy Hà Nội TP. HCM 15 hãng giao thông đường bộ Có 3 + 2 + 15 = 20 cách Cơ sở của phép đếm (2/2)11  Nguyên lý nhân  Giả sử có công đoạn E được thực hiện lần lượt qua các công đoạn E1, E2, …, Ek trong đó số cách thực hiện Ei là ni (i = 1, k). Khi đó số cách thực hiện E là n1 x n2 x … x nk  Ví dụ: 8 cách 4 cách TP. HCM Hà Nội Đà Nẵng Có 8 * 4 = 32 cách Toán Rời Rạc - ĐHSPHN12 Một Số Công Thức Tổ Hợp Toán Rời Rạc - ĐHSPHN Hoán vị13  Khái niệm. Hoán vị của một tập các đối tượng khác nhau là một cách sắp xếp có thứ tự các đối tượng này.  Bài toán. Cho tập A có n phần tử. Hãy tính số các hoán vị khác nhau của tập A.  Ví dụ: cho A={a,b,c,d} tìm tất cả các hoán vị có thể có của tập hợp A?  Định lý. Số các hoán vị khác nhau của một tập n phần tử là Pn = n! Toán Rời Rạc - ĐHSPHN Hoán vị14  Ví dụ: Hãy tính số các số sau:  Có năm chữ số được viết bởi đúng 5 chữ số 1, 2, 3, 4 và 5?  Có năm chữ số được viết bởi đúng 5 chữ số 1, 2, 3, 4 và 5 trong đó ba chữ số đầu là ba chữ số lẻ, hai chữ số sau là hai chữ số chẵn? Toán Rời Rạc - ĐHSPHN Hoán vị trên đường tròn15  Ví dụ: Cho tập hợp A = {a,b,c,d}. Tìm tất cả các hoán vị khác nhau của các phần tử của A trên đường tròn? Toán Rời Rạc - ĐHSPHN Hoán vị trên đường tròn16  Bài toán: Tính số các hoán vị khác nhau của một tập hợp A gồm n phần tử nằm ...