Bài giảng Đếm - Toán rời rạc thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

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. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

Đế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, y, ánh xạ
Luật ánh xạ
Luật tích luật tổng
Nguyên trừ
Luật BOOKEEPER
Chứng minh tổ hợp
y tập
y: thứ tự, các phần tử 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 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} 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ử
n! = n(n 1) · · · 1
6 / 48
Định nghĩa
Một ánh xạ
f : X Y
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
dụ
Quy tắc tương ứng f : {a, b, c} {1, 2, 3} định nghĩa dưới đây
phải ánh xạ không?
a
b
c
1
2
3
8 / 48
dụ
Quy tắc sau đây phải ánh xạ không?
a
b
c
d
1
2
3
9 / 48
Định nghĩa
Ánh xạ f : X Y
toàn ánh nếu mỗi phần tử của Y đều í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 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 chính xác một phần
tử tương ứng từ X.
10 / 48
dụ
Ánh xạ dưới đây đơn ánh hay toàn ánh hay song ánh?
a
b
c
d
1
2
3
11 / 48
dụ
Xét hoán vị (a
1
, a
2
, · · · , a
n
) của tập S = {a
1
, a
2
, · · · , a
n
}. Ánh xạ
π : {a
1
, a
2
, . . . , a
n
} {1, 2, . . . , n}
định nghĩa bởi
π(a
i
) = i
song ánh. Tại sao?
12 / 48
Nội dung
Tập, y, ánh xạ
Luật ánh xạ
Luật tích luật tổng
Nguyên trừ
Luật BOOKEEPER
Chứng minh tổ hợp
Định
Nếu ánh xạ f : X Y
toàn ánh thì |X| |Y|.
đơn ánh thì |X| |Y|.
song ánh thì |X| = |Y|.
14 / 48
Định
Số y gán nhãn với n đỉnh n
n2
.
Prüfer(T)
0
5
3
2
1
4
12
8 9
7
10 6
15
16
13
14
11
15 / 48
dụ
bao nhiêu cách chọn 12 chiếc bánh từ 5 loại bánh la,
chanh, đườ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 đúng 4 số 1.
Song ánh từ X đến Y
0 0

la
1

chanh
1 0 0 0 0 0 0

đường
1 0 0

kem
1 0 0

nguyên chất
|X| = |Y|
16 / 48
dụ
Xét song ánh từ các tập con của X = {1, 2, . . . , n} tới dãy
n-bit
S (b
1
, . . . , b
n
)
với
b
i
=
1 nếu i S
0 nếu i / S
Số y n-bit 2
n
.
Vy X 2
n
tập con.
17 / 48
Ánh Xạ k đến 1
Định nghĩa
Ánh xạ f : X Y gọi ánh xạ k đến 1 nếu ánh xạ đúng k
phần tử của X tới mỗi phần tử của Y.
Song ánh á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
ánh xạ
k
đến
1
”, thì
|X| = k · |Y|.
Nếu f song ánh vậy |X| = |Y|.
19 / 48
dụ
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 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 y
(h
1
, c
1

quân1
, h
2
, c
2

quân2
)
thỏa mãn h
1
= h
2
c
1
= c
2
.
một ánh xạ 2 đến 1 từ X lên Y. Tại sao?
Vy
|Y| =
|X|
2
=
8 × 8 × 7 × 7
2
.
20 / 48
| 1/48

Preview text:

Đế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 b 2 c 3 8 / 48 Ví dụ
Quy tắc sau đây có phải ánh xạ không? a 1 b 2 c 3 d 9 / 48 Định nghĩa
Ánh xạ f : X → Y
▶ 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 b 2 c 3 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
▶ 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 3 2 4 12 1 Prüfer(T) ←→ 8 9 7 10 6 16 15 13 11 14 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 |{z} 1 |{z} 1 0 0 0 0 0 0 | {z } 1 0 0 |{z} 1 0 0 |{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 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. 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 | {z }, h2, c2 | {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