1
23 September 2008
Toán rời rạc (2):
BÀI TOÁN ĐẾM
Ths. Hoàng ThThanh Hà
Khoa Thng kê –Tin hc
Trưng Đi hc Kinh t
Đi hcĐà Nng
23 September 2008
N
ội
dung
1. GIỚI THIỆU CHUNG
2. CƠ SỞ CỦA PHÉP ĐẾM
3. NGUYÊN LÝ DIRICHLET
4. CÁC CẤU HÌNH TỔ HỢP
5. BÀI TOÁN LIỆT KÊ
6. HỆ THỨC TRUY HỒI
2
23 September 2008
N
ội
dung
1. GIỚI THIỆU CHUNG
2. CƠ SỞ CỦA PHÉP ĐẾM
3. NGUYÊN LÝ DIRICHLET
4. CÁC CẤU HÌNH TỔ HỢP
5. BÀI TOÁN LIỆT KÊ
6. HỆ THỨC TRUY HỒI
23 September 2008
1. GIỚI THIỆU CHUNG
Lý thuyết tổhợp là một phần quan trọng của TRR
Nghiên cứu sựphân bốcác phần tửvào các tập
hợp. Được nghiên cứu từthếkỷ17
Liệt kê, đếmcác đối tượng có tính chất nào đó ->
rất quan trọng trong lý thuyết tổhợp
Chúng ta cần phảiđếm các đối tượng để giải nhiều
bài toán khác nhau
3
23 September 2008
1. GIỚI THIỆU CHUNG
Ví dụ: Bài toán đếm:
–Cần chọn hoặc là 01 sinh viên hoặc là 01 cán bộtrong
khoa tham dựdiễnđàn “Thanh niên với NCKH” của
thành phố. Hỏi có bao nhiêu cách chọn 01 thành viên
trên (khoa có 500 sinh viên và 20 cán bộ)?
–Tính sốmật khNu cho phép truy nhập vào hệthống máy
tính…?
–Hãy chứng minh nếu có nhiều hơn 14 sinh viên thì có ít
nhất 3 bạn sinh cùng một ngày trong tuần?
–Có bao nhiêu cách chia 52 quân bài cho 4 người, mỗi
ngườiđược chia 5 quân?
–…
23 September 2008
1. GIỚI THIỆU CHUNG
Trong chương này, chúng ta sẽ đề cậpđến:
–Những nguyên tắcđếm cơbản: giải quyếtđược nhiều
dạng bài toán khác nhau, làm cơsởcho các bài toán
đếm khác
–Nguyên lý Dirichlet (nlý lồng chim bồcâu): giải bài
toán tồn tại
Chứng minh nếu có nhiều hơn 14 sinh viên, có ít nhất 3 bạn
sinh cùng một ngày trong tuần
–Tổhợp, hoán vị, chỉnh hợp: giải bài toán đếm, liệt kê
các cấu hình thỏa mãn điều kiện nào đó
Có bao nhiêu cách chia 52 quân bài cho 4 người (mỗi người 5
quân)?
–Kỹthuậtđếm mởrộng : hệthức truy hồi, quan hệchia
để trị
4
23 September 2008
N
ội
dung
1. GIỚI THIỆU CHUNG
2. CƠ SỞ CỦA PHÉP ĐẾM
3. NGUYÊN LÝ DIRICHLET
4. CÁC CẤU HÌNH TỔ HỢP
5. BÀI TOÁN LIỆT KÊ
6. HỆ THỨC TRUY HỒI
23 September 2008
2. CƠ SỞ CỦA PHÉP ĐẾM
Đặt vấnđề:
–Mật khu vào máy tính gồm 3, 4 hoặc 5 kí tự. Kí tự
đầu tiên phải là chữcái, các kí tựtiếp theo có thểsố
hoặc chữcái, nhưng trong mật khuđó phải có ít
nhất một kí tựsố. Hỏi có bao nhiêu mật khu như
thế? -> đếm sốmật khu có thể
Các nguyên lý đếm cơbản:
–Nguyên lý cộng
–Nguyên lý nhân
–Nguyên lý bù trừ
5
23 September 2008
2.
CƠ SỞ CỦA PHÉP ĐẾM:
nguyên lý
cộng
Giảsửcó k công việc T
1
, T
2
, ..., T
k
, trong đó:
–T
1
làm bằng n
1
cách,
–T
2
làm bằng n
2
cách,
–T
3
làm bằng n
3
cách,
–...,
–T
k
làm bằng n
k
cách
Giảsửkhông có hai việc nào có thểlàm đồng
thời
=> sốcách làm một trong k việcđó là
n
1
+n
2
+...+n
k
23 September 2008
2.
CƠ SỞ CỦA PHÉP ĐẾM:
nguyên lý
cộng
Ví dụ:
–Cần chọn hoặc là 01 sinh viên hoặc là 01 cán bộtrong
khoa tham dựdiễnđàn “Thanh niên với NCKH” của
thành phố. Hỏi có bao nhiêu cách chọn 01 thành viên
trên (khoa có 500 sinh viên và 20 cán bộ)?
Trảlời:
–Có 500 cách chọn 01 sinh viên và 20 cách chọn 01 cán
bộ. Hai cách chọn này độc lập nhau. Vậy theo nguyên
lý cộng : có tất cả500+20=520 cách chọn 01 vị đại
biểu nói trên