Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 3

Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 3 Một số kỹ thuật đếm khác trình bày 2 nội dung chính như: Sử dụng sơ đồ Vennguyên lý bù trừ,...Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán học tổ hợp và cấu trúc rời rạc: Chương 3TOÁN HỌC TỔ HỢP VÀ CẤU TRÚC RỜI RẠCChương 3MỘT SỐ KỸ THUẬT ĐẾMKHÁCĐại học Khoa Học Tự Nhiên Tp. Hồ Chí MinhĐH KHTN Tp. HCMChương 3. Một số kỷ thuât đếm khác09/20161/16Nội dungChương 2.MỘT SỐ KỸ THUẬT ĐẾM KHÁC1. Sử dụng sơ đồ Ven2. Nguyên lý bù trừĐH KHTN Tp. HCMChương 3. Một số kỷ thuât đếm khác09/20162/163.1. Sử dụng sơ đồ VenNhận xét. Xét sơ đồ VenTa ký hiệuU là tập vũ trụA là phần bù của A trong UN (A) là số phần tử của A.N = N (U)Khi đóN (A ∩ B) = N − N (A) − N (B) + N (A ∩ B)ĐH KHTN Tp. HCMChương 3. Một số kỷ thuât đếm khác(1)09/20163/16Ví dụ. Một trường học có 100 sinh viên, trong đó có 50 sinh viên họctiếng Anh, 40 sinh viên học tiếng Pháp và 20 sinh viên học cả tiếngAnh và tiếng Pháp. Hỏi có bao nhiêu sinh viên không học tiếng Anhlẫn không học tiếng Pháp?Giải. Gọi là U là tập hợp sinh viên của trường. Gọi A là tập hợp sinhviên học tiếng Anh và P là tập hợp sinh viên học tiếng Pháp. Ta cóN = N (U) = 100, N (A) = 50, N (P ) = 40 và N (A ∩ P ) = 20.Theo yêu cầu bài toán chúng ta cần tính N (A ∩ P ). Ta cóN (A ∩ P ) = N − N (A) − N (P ) + N (A ∩ P )= 100 − 50 − 40 + 20 = 30Ví dụ. Có bao nhiêu hoán vị các chữ số 0, 1, 2, . . . , 9 sao cho chữ sốđầu lớn hơn 1 và chữ số cuối nhỏ hơn 8?Giải. Gọi U là tập tất cả các hoán vị của 0, 1, 2, ..., 9; A là tập tất cảcác hoán vị với chữ số đầu là 0 hoặc 1 và B là tập tất cả các hoán vị vớichữ số cuối là 8 hoặc 9. Khi đó yêu cầu của bài toán là tính N (A ∩ B).ĐH KHTN Tp. HCMChương 3. Một số kỷ thuât đếm khác09/20164/16Ta có N = 10!, N (A) = 2 × 9!, N (B) = 2 × 9!, N (A ∩ P ) = 2 × 2 × 8!.Áp dụng công thức (1) ta đượcN (A ∩ B)= N − N (A) − N (B) + N (A ∩ B)= 10! − (2 × 9!) − (2 × 9!) + (2 × 2 × 8!) = 2338560Câu hỏi. Nếu ta mở rộng công thức (1) cho trường hợp 3 tập hợp thìnhư thế nào?Đáp án. Khi đó công thức làN (A ∩ B ∩ C) =N − N (A) − N (B) − N (C)+ N (A ∩ B) + N (A ∩ C) + N (B ∩ C)− N (A ∩ B ∩ C)ĐH KHTN Tp. HCMChương 3. Một số kỷ thuât đếm khác(2)09/20165/16