Bài giảng Toán rời rạc: Đếm - Trần Vĩnh Đức

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Đếm - Trần Vĩnh Đức Đếm Trần Vĩnh Đức HUSTCuuDuongThanCong.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ợpCuuDuongThanCong.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) · · · 1CuuDuongThanCong.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 3CuuDuongThanCong.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 dCuuDuongThanCong.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 dCuuDuongThanCong.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à luật tổng Nguyên lý bù trừ Luật BOOKEEPER Chứng minh tổ hợpCuuDuongThanCong.com https://fb.com/tailieudientucntt Định lý Nếu ánh xạ f : X → Y là ▶ toàn ánh thì |X| ≥ |Y|. ▶ đơn ánh thì |X| ≤ |Y|. ▶ song ánh thì |X| = |Y|.CuuDuongThanCong.com https://fb.com/tailieudientucntt 14 / 48 Định lý Số cây gán nhãn với n đỉnh là nn−2 . 0 5 3 2 4 12 1 Prüfer(T) ←→ 8 9 7 10 6 16 ...