Xem mẫu
- Đế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
nguon tai.lieu . vn
