Đếm
HUST
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
1 / 48
Trần Vĩnh Đức
Tài liệu tham khảo
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
2 / 48
▶ E.Lehman, T. Leighton, A. Meyer, Mathematics for Computer Science, 2015.
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
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
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
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
4 / 48
fa; b; cg = fb; a; cg
Đị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 fa; b; cg có 6 hoán vị:
f (a; b; c); (b; c; a); (c; a; b); (c; b; a); (b; a; c); (a; c; b) g
▶ Số hoán vị của tập n phần tử là
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
6 / 48
n! = n(n (cid:0) 1) (cid:1) (cid:1) (cid:1) 1
Định nghĩa Một ánh xạ
f : X ! Y
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
7 / 48
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.
Ví dụ Quy tắc tương ứng f : fa; b; cg ! f1; 2; 3g định nghĩa dưới đây có phải ánh xạ không?
a 1
2 b
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
8 / 48
c 3
Ví dụ Quy tắc sau đây có phải ánh xạ không?
a 1
2 b
c 3
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
9 / 48
d
Đị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.
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
10 / 48
▶ 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.
Ví dụ
Ánh xạ dưới đây là đơn ánh hay toàn ánh hay song ánh?
a 1
2 b
c 3
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
11 / 48
d
Ví dụ Xét hoán vị (a1; a2; (cid:1) (cid:1) (cid:1) ; an) của tập S = fa1; a2; (cid:1) (cid:1) (cid:1) ; ang. Ánh xạ
(cid:25) : fa1; a2; : : : ; ang ! f1; 2; : : : ; ng
định nghĩa bởi (cid:25)(ai) = i
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
12 / 48
là song ánh. Tại sao?
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
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
Chứng minh tổ hợp
Định lý Nếu ánh xạ f : X ! Y là
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
14 / 48
▶ toàn ánh thì jXj (cid:21) jYj. ▶ đơn ánh thì jXj (cid:20) jYj. ▶ song ánh thì jXj = jYj.
Định lý Số cây gán nhãn với n đỉnh là nn(cid:0)2.
0
5 3
4 2 12 1
7 8 9
!
Prüfer(T)
6 10 16 15 13
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
15 / 48
11 14
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
1 | 1 0 0 0 0 0 0 } 1 |{z} chanh {z có đường 1 0 0|{z} kem 0 0|{z} sô cô la 0 0|{z} nguyên chất
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
16 / 48
▶ jXj = jYj
Ví dụ
▶ Xét song ánh từ các tập con của X = f1; 2; : : : ; ng tới dãy n-bit S ! (b1; : : : ; bn)
{ với
bi = 1 nếu i 2 S 0 nếu i /2 S
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
17 / 48
▶ Số dãy n-bit là 2n. ▶ Vậy X có 2n tập con.
Á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.
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
18 / 48
Song ánh là ánh xạ “1 đến 1”
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ì
jXj = k (cid:1) jYj:
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
19 / 48
▶ Nếu f là song ánh vậy jXj = jYj.
Ví dụ Có bao nhiêu cách đặt hai quân cờ giống nhau lên bàn cờ 8 (cid:2) 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
)
; h2; c2 | {z } quân2
(h1; c1 | {z } quân1 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
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
20 / 48
jYj = = : jXj 2 8 (cid:2) 8 (cid:2) 7 (cid:2) 7 2
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
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
Chứng minh tổ hợp
Luật tích
Định nghĩa
A1 (cid:2) A2 (cid:2) (cid:1) (cid:1) (cid:1) (cid:2) An = f(a1; (cid:1) (cid:1) (cid:1) ; an) j ai 2 Aig
Định lý Nếu A1; : : : ; An là các tập hữu hạn, vậy thì
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
22 / 48
jA1 (cid:2) A2 (cid:2) (cid:1) (cid:1) (cid:1) (cid:2) Anj = jA1j (cid:2) jA2j (cid:2) (cid:1) (cid:1) (cid:1) (cid:2) jAnj:
Luật tổng
Định lý Nếu A1; A2; : : : ; An là các tập rời nhau, vậy
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
23 / 48
jA1 [ A2 [ (cid:1) (cid:1) (cid:1) [ Anj = jA1j + jA2j + (cid:1) (cid:1) (cid:1) + jAnj:
Bài toán Có bao nhiêu cách chọn trong nhóm n người một ủy ban ba người trong đó một người làm chủ tịch, một người làm thư ký, và một người làm tư vấn?
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
24 / 48
Lời giải
▶ Mỗi cách chọn một ủy ban
( ; ; ) x|{z} chủ tịch x|{z} tư vấn y|{z} thư ký
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
25 / 48
▶ với n người có thể làm chủ tịch, ▶ còn lại n (cid:0) 1 người có thể làm thư ký (trừ x), ▶ còn lại n (cid:0) 2 người có thể làm tư vấn (trừ x và y). ▶ Vậy có n(n (cid:0) 1)(n (cid:0) 2) cách chọn.
Bài toán
▶ Số seri của các tờ tiền có dạng
MQ 09 19 99 99
▶ Tờ tiền khuyết số nếu có một chữ số xuất hiện hơn một lần trong số seri gồm 8 chữ số.
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
26 / 48
▶ Tờ tiền khuyết số có phổ biến không?
Bài toán Đếm xem có bao nhiêu mật khẩu thỏa mãn 4 yêu cầu sau đây:
1. Dài từ 6 đến 8 ký hiệu;
2. Phải bắt đầu bằng một chữ cái;
3. Chỉ gồm 26 chữ cái thường hoặc 26 chữ cái hoa hoặc các số 0 đến 9;
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
27 / 48
4. Có phân biệt chữ hoa chữ thường.
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
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
Chứng minh tổ hợp
A \ B
B A
Theo luật tổng ta có:
jAj = jA n Bj + jA \ Bj jBj = jB n Aj + jA \ Bj
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
29 / 48
jA [ Bj = jA n Bj + jA \ Bj + jB n Aj
Nguyên lý bù trừ cho hai tập
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
30 / 48
jA [ Bj = jAj + jBj (cid:0) jA \ Bj:
Nguyên lý bù trừ cho ba tập
jA [ B [ Cj = jAj + jBj + jCj
(cid:0) jA \ Bj (cid:0) jB \ Cj (cid:0) jA \ Cj + jA \ B \ Cj:
B
CuuDuongThanCong.com
https://fb.com/tailieudientucntt
31 / 48
C A
Nguyên lý bù trừ
n∑
jS1 [ S2 [ (cid:1) (cid:1) (cid:1) [ Snj =
i=1 (cid:0)
1(cid:20)i jSij
∑ jSi \ Sjj 1(cid:20)i i=1 Sij: CuuDuongThanCong.com https://fb.com/tailieudientucntt 32 / 48 + jSi \ Sj \ Skj + (cid:1) (cid:1) (cid:1) i2I ∅̸=I(cid:18)f1;2;:::;ng CuuDuongThanCong.com https://fb.com/tailieudientucntt 33 / 48 ∑ ∩ ((cid:0)1)jIj(cid:0)1 jS1 [ S2 [ (cid:1) (cid:1) (cid:1) [ Snj = Si (cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12) (cid:12)
(cid:12)
(cid:12)
(cid:12)
(cid:12) ▶ Có bao nhiêu hoán vị của tập f0; 1; : : : ; 9g có chứa (liền nhau) 42; 04 hoặc 60? ▶ Ví dụ, hoán vị sau đây chứa 60 và 04. CuuDuongThanCong.com https://fb.com/tailieudientucntt 34 / 48 (7; 2; 5; 6; 0; 4; 3; 5; 1; 9) CuuDuongThanCong.com https://fb.com/tailieudientucntt 35 / 48 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chứng minh tổ hợp ▶ Xét k chữ phân biệt c1; c2; : : : ; ck.
▶ Số dãy gồm n1 chữ c1, n2 chữ c2, : : : , và nk chữ ck là ( ) CuuDuongThanCong.com https://fb.com/tailieudientucntt 37 / 48 = n1 + n2 + (cid:1) (cid:1) (cid:1) + nk
n1; n2; (cid:1) (cid:1) (cid:1) ; nk (n1 + n2 + (cid:1) (cid:1) (cid:1) + nk)!
n1!n2! (cid:1) (cid:1) (cid:1) nk! ( ) ( ) CuuDuongThanCong.com https://fb.com/tailieudientucntt 38 / 48 = = n!
k!(n (cid:0) k)! n
k; n (cid:0) k n
k ( ) = : 16
4 16!
4!12! CuuDuongThanCong.com https://fb.com/tailieudientucntt 39 / 48 Đây chính là số cách chọn tập con 4 phần tử từ tập 16 phần tử. ( ) CuuDuongThanCong.com https://fb.com/tailieudientucntt 40 / 48 : n
k n∑ ( ) k=0 (a + b)n = an(cid:0)kbk: n
k ▶ (a + b)2 = aa + ab + ba + bb = a2 + 2ab + b2
▶ (a + b)3 = aaa + aab + aba + baa + abb + bab + bba + bbb = a3 + 3a2b + 3b2a + b3 n
k CuuDuongThanCong.com https://fb.com/tailieudientucntt 41 / 48 ( ) ▶ Số dãy độ dài n chứa k chữ a và (n (cid:0) k) chữ b là : 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt Chứng minh tổ hợp ( ) .
( . )
n
n(cid:0)k ▶ Có n chiếc áo phân biệt,
▶ Số cách giữ lại k chiếc áo là
n
k
▶ Số cách bỏ đi n (cid:0) k chiếc áo là
▶ Vậy ta có ( ) ( ) CuuDuongThanCong.com https://fb.com/tailieudientucntt 43 / 48 = = n
k n
n (cid:0) k n!
k!(n (cid:0) k)! ( )
n(cid:0)1
k(cid:0)1 ( . )
n(cid:0)1
k ▶ Chọn một đội gồm k sinh viên trong số n sinh viên.
▶ Số đội có Bob là
.
▶ Số đội không có Bob là
▶ Vậy ta có (đẳng thức Pascal)
( ) ) ( ( ) CuuDuongThanCong.com https://fb.com/tailieudientucntt 44 / 48 + = : n (cid:0) 1
k (cid:0) 1 n (cid:0) 1
k n
k CuuDuongThanCong.com https://fb.com/tailieudientucntt 45 / 48 1. Định nghĩa S.
2. Chứng minh jSj = n (một cách đếm).
3. Chứng minh jSj = m (một cách đếm khác).
4. Kết luận m = n. n∑ ( ) ( ) ( ) r=0 CuuDuongThanCong.com https://fb.com/tailieudientucntt 46 / 48 (cid:1) = : n
r 2n
n (cid:0) r 3n
n ▶ S = các bộ bài gồm n quân chọn từ n quân đỏ và 2n quân đen trên bàn. ▶ Vậy ( ) CuuDuongThanCong.com https://fb.com/tailieudientucntt 47 / 48 jSj = : 3n
n ▶ Số bộ bài với đúng r quân đỏ là
)( ( ) n
r 2n
n (cid:0) r n∑ ▶ Số quân đỏ có thể từ 0 đến n nên ta có ( )( ) r=0 CuuDuongThanCong.com https://fb.com/tailieudientucntt 48 / 48 jSj = : 2n
n (cid:0) r n
rNguyên lý bù trừ (cách viết khác)
Bài toán
Bài toán (François Édouard Anatole Lucas, 1894)
Cho một cái bàn tròn và m cặp vợ chồng, có bao nhiêu cách để
xếp họ ngồi nam nữ xem kẽ sao cho không cặp vợ chồng nào ngồi
kề nhau?
Nội dung
Định lý (Luật BOOKEEPER)
Định lý (Công thức nhị thức)
Ví dụ
Số dãy 16-bit chứa đúng 4 bit 1 là
Ví dụ (Luật tập con)
Số tập con k phần tử của tập n phần tử là
Định lý (Hệ số nhị thức)
Với mọi n (cid:21) 0 ta có
Nội dung
Ví dụ
Ví dụ
Đếm bằng hai cách
Định lý
Chứng minh
Chứng minh 2
