›
›

Giáo trình Toán rời rạc - Bài 13: Đếm - Trần Vĩnh Đức

Download
Đếm  
Trần Vĩnh Đức  
HUST  
1 / 48  
Tài liệu tham khảo  
▶
E.Lehman, T. Leighton, A. Meyer, Mathematics for Computer  
Science, 2015.  
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  
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}  
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.  
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  
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.  
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
2
b
c
3
8 / 48  
Ví dụ  
Quy tắc sau đây có phải ánh xạ không?  
a
1
2
3
b
c
d
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.  
10 / 48  
Ví dụ  
Ánh xạ dưới đây là đơn ánh hay toàn ánh hay song ánh?  
a
1
2
3
b
c
d
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?  
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  
Đị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|.  
14 / 48  
Định lý  
Số cây gán nhãn với n đỉnh là nn−2  
.
0
5
1
3
2
8
4
9
12  
7
Prüfer(T)  
←→  
10  
6
16  
11  
15  
14  
13  
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
1 0 0 0 0 0 0 1 0 0 1  
0 0  
|{z}  
|{z}  
|
{z  
}
|{z}  
|{z}  
sô cô la  
chanh  
có đường  
kem  
nguyên chất  
▶
|X| = |Y|  
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
0
nếu i ∈ S  
nếu i ∈/ S  
bi =  
Số dãy n-bit là 2n.  
▶
▶
Vậy X có 2n tập con.  
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”  
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|.  
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
20 / 48  
Tải về để xem bản đầy đủ
pdf 48 trang Thùy Anh 16020 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc - Bài 13: Đếm - Trần Vĩnh Đức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfgiao_trinh_toan_roi_rac_bai_13_dem_tran_vinh_duc.pdf