Đ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: Đếm cung cấp cho người học những nội dung kiến thức như: Tập, dãy, và ánh xạ; luật ánh xạ; luật tích và luật tổng; nguyên lý bù trừ; Luật BOOKEEPER; chứng minh tổ hợp. Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết. | Đếm Trần Vĩnh Đức HUST CuuDuongThanCong.com https fb.com tailieudientucntt 1 48 Tài liệu tham khảo E.Lehman T. Leighton A. Meyer Mathematics for Computer Science 2015. CuuDuongThanCong.com https fb.com tailieudientucntt 2 48 Nội dung Tập dãy và ánh xạ Luật ánh xạ Luật tích và luật tổng Nguyên lý bù trừ Luật BOOKEEPER Chứng minh tổ hợp CuuDuongThanCong.com https fb.com tailieudientucntt Dãy và tập Dãy có thứ tự các phần tử có thể trùng nhau a b a ̸ b a a Tập không thứ tự các phần tử không trùng nhau a b c b a c CuuDuongThanCong.com https fb.com tailieudientucntt 4 48 Định nghĩa Một hoán vị của một tập S là một dãy chứa mỗi phần tử của S đúng một lần. CuuDuongThanCong.com https fb.com tailieudientucntt 5 48 Số hoán vị của một tập Tập a b c có 6 hoán vị a b c b c a c a b c b a b a c a c b Số hoán vị của tập n phần tử là n n n 1 1 CuuDuongThanCong.com https fb.com tailieudientucntt 6 48 Định nghĩa Một ánh xạ f X Y là một quy tắc cho tương ứng mỗi phần tử của X với đúng một phần tử của Y. CuuDuongThanCong.com https fb.com tailieudientucntt 7 48 Ví dụ Quy tắc tương ứng f a b c 1 2 3 định nghĩa dưới đây có phải ánh xạ không a 1 b 2 c 3 CuuDuongThanCong.com https fb.com tailieudientucntt 8 48 Ví dụ Quy tắc sau đây có phải ánh xạ không a 1 b 2 c 3 d CuuDuongThanCong.com https fb.com tailieudientucntt 9 48 Định nghĩa Ánh xạ f X Y là toàn ánh nếu mỗi phần tử của Y đều có ít nhất một phần tử tương ứng từ X. đơn ánh nếu mỗi phần tử của Y đều có nhiều nhất một phần tử tương ứng từ X. song ánh nếu mỗi phần tử của Y đều có chính xác một phần tử tương ứng từ X. CuuDuongThanCong.com https fb.com tailieudientucntt 10 48 Ví dụ Ánh xạ dưới đây là đơn ánh hay toàn ánh hay song ánh a 1 b 2 c 3 d CuuDuongThanCong.com https fb.com tailieudientucntt 11 48 Ví dụ Xét hoán vị a1 a2 an của tập S a1 a2 an . Ánh xạ π a1 a2 . . . an 1 2 . . . n định nghĩa bởi π ai i là song ánh. Tại sao CuuDuongThanCong.com https fb.com tailieudientucntt 12 48 Nội dung Tập dãy và ánh xạ Luật ánh xạ Luật tích và .
