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

Chia sẻ: Elysale Elysale | Ngày: | Loại File: PDF | Số trang:39

Thêm vào BST

Báo xấu

27
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ọ
Support 2  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 DUNG 3  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ợp 4  “Đá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 - ĐHSPHN
5 Cơ sở của phép đếm Toán Rời Rạc - ĐHSPHN
Cơ sở của phép đếm 6  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 Đêcac 7  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 Đêcac 8  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 - ĐHSPHN
9 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 - ĐHSPHN
12 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òn 15  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òn 16  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 trên một đường tròn?  Định lý: Số các hoán vị tròn khác nhau của tập hợp A có n phần tử là Qn = (n – 1)! Toán Rời Rạc - ĐHSPHN
Chỉnh hợp 17  Bài toán: Cho tập A có n phần tử và số k≤n (kN). Mỗi dãy độ dài k được xếp bởi các phần tử của tập A trong đó mỗi phần tử có mặt không quá một lần được gọi là một dãy k phần tử không lặp của A.  Tính số các dãy đó? Toán Rời Rạc - ĐHSPHN
Chỉnh hợp 18  Định lý: Cho trước tập A có n phần tử và một số tự nhiên k ≤ n. Số các dãy k phần tử không lặp của A là:  Ví dụ: có bao nhiêu số có 4 chữ số mà trong biểu diễn thập phân của nó không có 2 chữ số nào giống nhau và không có mặt chữ số chẵn? Toán Rời Rạc - ĐHSPHN
Chỉnh hợp lặp 19  Cho tập A có n phần tử. Khi đó số dãy gồm k phần tử có lặp thuộc tập A là nk và được gọi là chỉnh hợp lặp chập k của n phần tử.  Ví dụ: có bao nhiêu số tự nhiên có 9 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,1,2,3,4,5}? Toán Rời Rạc - ĐHSPHN
Chỉnh hợp với tần số lặp cho trước 20  Định lý: Cho trước một tập hợp A có n phần tử. Số các dãy k phần tử có lặp (k1+k2+…+kn) và (k=k1+…+kn) là: k! P(k1 , k2 ,..., kn )  k1 !k2 !...kn !  Ví dụ: Tính các số tự nhiên có 7 chữ số, trong đó có 3 chữ số 1, 2 chữ số 2 và 2 chữ số 3. Toán Rời Rạc - ĐHSPHN