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

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

Thêm vào BST

Báo xấu

23
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: Đế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.

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: Đếm - Trần Vĩnh Đức

Đế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à luật tổng Nguyên lý bù trừ Luật BOOKEEPER Chứng minh tổ hợp CuuDuongThanCong.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 15 13 11 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt 15 / 48
Ví dụ Có bao nhiêu cách chọn 12 chiếc bánh từ 5 loại bánh sô cô la, chanh, có đường, kem, nguyên chất? ▶ X = tập mọi cách chọn 12 chiếc bánh từ 5 loại bánh. ▶ Y = tập mọi xâu 16 bit có đúng 4 số 1. ▶ Song ánh từ X đến Y 0 0 1 |{z} 1 0| 0 0{z0 0 0} 1 |{z} |{z} 00 1 00 |{z} sô cô la chanh có đường kem nguyên chất ▶ |X| = |Y| CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 48
Ví dụ ▶ Xét song ánh từ các tập con của X = {1, 2, . . . , n} tới dãy n-bit S → (b1 , . . . , bn ) với { 1 nếu i ∈ S bi = 0 nếu i ∈ /S ▶ Số dãy n-bit là 2n . ▶ Vậy X có 2n tập con. CuuDuongThanCong.com https://fb.com/tailieudientucntt 17 / 48
Ánh Xạ “k đến 1” Định nghĩa Ánh xạ f : X → Y gọi là ánh xạ “k đến 1” nếu nó ánh xạ đúng k phần tử của X tới mỗi phần tử của Y. Song ánh là ánh xạ “1 đến 1” CuuDuongThanCong.com https://fb.com/tailieudientucntt 18 / 48
Luật chia (tổng quát hóa của luật song ánh) ▶ Nếu f : X → Y là ánh xạ “k đến 1”, thì |X| = k · |Y|. ▶ Nếu f là song ánh vậy |X| = |Y|. CuuDuongThanCong.com https://fb.com/tailieudientucntt 19 / 48
Ví dụ Có bao nhiêu cách đặt hai quân cờ giống nhau lên bàn cờ 8 × 8 sao cho chúng không chung hàng và không chung cột ? ▶ Y = tập mọi cấu hình hợp lệ cho hai quân cờ. ▶ X = mọi dãy (h1 , c1 , h2 , c2 ) | {z } | {z } quân1 quân2 thỏa mãn h1 ̸= h2 và c1 ̸= c2 . ▶ Có một ánh xạ “2 đến 1” từ X lên Y. Tại sao? ▶ Vậy |X| 8×8×7×7 |Y| = = . 2 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 48