Giáo trình Toán rời rạc - Chương 2 Phép đếm

Tài liệu tham khảo dành cho giáo viên, sinh viên chuyên ngành công nghệ thông tin - Giáo trình, bài tập toán rời rạc. Mời các bạn tham khảo để biết thêm nhiều kiến thức về toán rời rạc, các nguyên lý toán thống kê. Chúc các bạn học tốt.
Nội dung trích xuất từ tài liệu:
Giáo trình Toán rời rạc - Chương 2 Phép đếm LOGO Chương 2Lê Văn Luyệnemail: lvluyen@yahoo.comTOÁN RỜI RẠC www.math.hcmus.edu.vn/~lvluyen/trr Phép đếmChươ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 đếmI. Các nguyên lý1. Nguyên lý cộngGiả 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àmKhi đó số cách làm công việc A là n+mVí 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 đếmI. Các nguyên lý2. Nguyên lý nhânGiả 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àmKhi đó số cách làm công việc A là n.mVí 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 2Giải. Gọi số có 3 chữ số là abcTH1 . 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 TH2 có 2.4.4 =32 a có 4 cách chọn ( aX{c, 0} ) 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 ítnhấ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 đếmI. 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 concủ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 đếmI. 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 B A B Cơ sở LogicI. Các nguyên lý C BC A C A B  C A B A B |A  B  C|=? Phép đếmI. Các nguyên lýVí dụ. Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS họcTiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh họcTiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu ngườiGiải.Gọi A là những học sinh học Tiếng Pháp B là những học sinh học Tiếng AnhKhi đó. Số học sinh của lớp là |A  B |. Theo nguyên lýbù trừ ta có |A  B|= |A|+|B| - |A  B|=24+26-15=35 Phép đếmII. Giải tích tổ hợp1. Hoán vịĐịnh nghĩa. Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử. Số các hoán vị của n phần tử ký hiệu là P n Pn = n! = n.(n-1).(n-2)…1 Quy ước 0! =1Ví dụ. Cho A ={a,b,c}. Khi đó A có các hoán vị sau abc,acb, bac,bca, cab,cba Phép đếmVí dụ. Nếu A là tập hợp n phần tử thì số song ánh từ A vàoA là n! Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm5 chữ số khác nhau được tạo từ tập X  5! Phép đếm II. Giải tích tổ hợp2. Chỉnh hợp.Định nghĩa. Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm kphần tử (1 k n) sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử. AnkSố các chỉnh hợp chập k của n ký hiệu là- Công thức n! A k  n  k ! n Ví dụ. Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb. Phép đếm II. Giải tích tổ hợp Ví dụ. Có bao nhiêu số tự nhiên gồm 3 chữ số được tạothành từ 1,2,3,4,5,6. Kết quả: A6 3 ...