Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc - Chương 2: Phép đếm (Phạm Thế Bảo)

Bài giảng Toán rời rạc - Chương 2: Phép đếm (Phạm Thế Bảo) có nội dung trình bày các kiến thức về nguyên lý như nguyên lý cộng, nguyên lý nhân, nguyên lý chuồng bồ câu, giải tích tổ hợp, hoán vị lặp, tổ hợp lặp, hệ thức đệ qui, . Mời các bạn cùng tham khảo chi tiết nội dung bài giảng! | LOGO2 Chương TOÁN RỜI RẠC Phạm Thế Bảo email ptbao@hcmus.edu.vn www.math.hcmus.edu.vn ptbao TRR Phép đếm Chương II PHÉP ĐẾM - Các nguyên lý - Giải tích tổ hợp - Hoán vị lặp tổ hợp lặp - Hệ thức đệ qui Phép đếm I. Các nguyên lý 1. Nguyên lý cộng Giả sử để làm công việc A có 2 phương pháp - Phương pháp 1 có n cách làm - Phương pháp 2 có m cách làm Khi đó số cách làm công việc A là n m Ví dụ. An có 3 áo tay dài 5 áo tay ngắn. Để chọn 1 cái áo thì An có mấy cách Phép đếm I. Các nguyên lý 2. Nguyên lý nhân Giả sử để làm công việc A cần thực hiện 2 bước - Bước 1 có n cách làm - Bước 2 có m cách làm Khi đó số cách làm công việc A là n.m Ví dụ A B C Có 3.2 6 con đường đi từ A đến C Phép đếm I. Các nguyên lý Ví dụ Cho tập X 1 2 3 4 5 0 Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia hết cho 2 Giải. Gọi số có 3 chữ số là abc TH1 . c 0. Khi đó c có 1 cách chọn a có 5 cách chọn a X 0 TH1 có 1.4.5 20 b có 4 cách chọn b X a 0 TH2 . c 0. Khi đó c có 2 cách chọn a có 4 cách chọn a X c 0 TH2 có 2.4.4 32 b có 4 cách chọn b X a c Vậy có 20 32 52 Phép đếm I. Các nguyên lý 3. Nguyên lý chuồng bồ câu Derichlet Gọi x là số nguyên nhỏ nhất lớn hơn hay bằng x. Giả sử có n chim bồ câu ở trong k chuồng. Khi đó tồn tại ít nhất một chuồng chứa từ n k bồ câu trở lên. Ví dụ. Có 20 chim bồ câu ở trong 7 cái chuồng. Khi đó sẽ có ít nhất 1 chuồng có 3 con bồ câu trở lên - Trong 1 nhóm có 367 người thì ít nhất có 2 người sinh cùng ngày Phép đếm I. Các nguyên lý Ví dụ. Cho tập X 1 2 3 4 5 6 7 8 9 . Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ có hai phần tử có tổng bằng 10. Giải. Ta lập các chuồng như sau 1 9 2 8 3 7 4 6 5 Do A có 6 phần tử nên trong 6 phần tử đó sẽ có 2 phần tử trong 1 chuồng. Suy ra đpcm Phép đếm I. Các nguyên lý 4. Nguyên lý bù trừ. Cho A và B là hai tập hữu hạn. Khi đó A B A B - A B A A B B Cơ sở Logic I. Các nguyên lý C A C B C A B C A B A B A B C Phép đếm I. Các nguyên lý Ví dụ. Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học Tiếng Pháp 26 học sinh học