1
Toán rời rạc
Phần thứ nhất
LÝ THUYẾT TỔ HỢP
Combinatorial Theory
Fall 2009
2
Toán rời rạc
Nội dung
Chương 0. Mở đầu
Chương 1. Bài toán đếm
Chương 2. Bài toán tồn tại
Chương 3. Bài toán liệt kê tổ hợp
Chương 4. Bài toán tối ưu tổ hợp
3
Toán rời rạc
Chương 1. BÀI TOÁN ĐẾM
1. Nguyên lý cộng và nguyên lý nhân
2. Các cấu hình tổ hợp cơ bản
3. Nguyên lý bù trừ
4. Công thức đệ qui
5. Hàm sinh
4
Toán rời rạc
1. Nguyên lý cộng và Nguyên lý nhân
Đây là hai nguyên lý cơ bản của tổ hợp,
được vận dụng rộng rãi vào việc giải
quyết các bài toán đếm
Còn gọi là Qui tắc cộng và Qui tắc nhân
(Sum Rule và Product Rule)
5
Toán rời rạc
1.1. Nguyên lý cộng
(The sum rule)
NÕu A vµ B lµ hai tËp hîp rêi nhau th×
N(AB)= N(A)+ N(B).
Nguyªn lý céng ®îc më réng cho nhiÒu tËp con rêi nhau:
NÕu A1, A2, ..., Ak lµ mét ph©n ho¹ch cña tËp hîp X th×
N(X)= N(A1)+ N(A2)+ ... + N(Ak).
Mét trêng hîp riªng hay dïng cña nguyªn lý céng:
NÕu A lµ mét tÝnh chÊt cho trªn tËp X th×
N(A)= N(X)- N(Ac).
( ) ( ) ( )
N A N X N A