Bài giảng Toán rời rạc - Chương 2: Phương pháp đếm - Vũ Đình Long

Chương 2
PHƯƠNG PHÁP ĐẾM
Tập hợp
Phép toán trên tập hợp
Ánh xạ
Ánh xạ (tt)
Ánh xạ (tt)
Phép đếm
Phép đếm (tt)
Nguyên lý cộng
Nguyên lý nhân
Giải tích tổ hợp

 Đếm số ánh xạ:
Giải tích tổ hợp (tt)

 Đếm số đơn ánh:
Giải tích tổ hợp (tt)
Giải tích tổ hợp (tt)

 T
 hp lp: Xét bài toán tìm nghiệm 
nguyên không âm (*) của phương trình

 x1 + x2 + ... + xk = n (**)

 Rõ ràng mỗi nghiệm (x1,x2,...,xk) thỏa 
điều kiện (*) của pt (**) có thể biểu diễn 
bằng dãy:
Tổng số cột của bảng trên = k-1
Giải tích tổ hợp (tt)

 Nhận xét:
- Số các dãy dấu ‘+’ được phân thành (k-1) 
nhóm.
- Tổng số dấu ‘+’ là: (n+k-1)
- Do vậy, số nghiệm của (**) bằng số cách phân 
(n+k-1) dấu ‘+’ thành (k-1) nhóm, tức là bằng:
C(k-1,n+k-1)=C(n,n+k-1) (***)
Giá trị (***) được gọi là tổ hợp lặp chập k của n 
phần tử.
Giải tích tổ hợp (tt)

 Chỉnh hợp lặp: Xét bài toán đếm số xâu bit độ dài n.

 Trong đó xi, i=(1,n) nhận giá trị trong tập {0,1}.

 Vậy mọi thành phần xi đều có số cách chọn là 2. Tức là
số xâu bit = 2n

 Trong trường hợp tổng quát: một chỉnh hợp lặp chập k 
của n phần tử là một cách chọn k phần tử (có thể lặp lại) 
trong n phần tử (cho trước).

 Số chỉnh hợp lặp chập k của n phần tử bằng kn
Nguyên lý Dirichlet
Nguyên lý Dirichlet (tt)

 Ví dụ: Nếu trong lớp học có 50 sinh viên 
thì tồn tại một tháng trong năm có ít nhất 
5 sinh viên cùng tổ chức sinh nhật.