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

Tóm tắt 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ọ

pdf18 trang | Chia sẻ: havih72 | Lượt xem: 263 | Lượt tải: 0download
Nội dung tài liệu Bài giảng Toán rời rạc - Chương 2: Phương pháp đếm - Vũ Đình Long, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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.

File đính kèm:

  • pdfbai_giang_toan_roi_rac_chuong_2_phuong_phap_dem_vu_dinh_long.pdf
Ebook liên quan