Bài giảng Toán tổ hợp: Chương 3 - Nguyễn Anh Thi

Bài giảng "Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác" cung cấp cho người học các kiến thức: Sử dụng sơ đồ ven, nguyên lý bù trừ, đa thức quân xe,... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán tổ hợp: Chương 3 - Nguyễn Anh ThiBài giảng Toán tổ hợpĐại học Khoa học Tự nhiên, Tp HCMBài giảng Toán tổ hợp1/34Nội dung chương 3Nội dungChương 3.MỘT SỐ KỸ THUẬT ĐẾM KHÁC1. Sử dụng sơ đồ Ven2. Nguyên lý bù trừ3. Đa thức quân xeBài giảng Toán tổ hợp2/343.1. Sử dụng sơ đồ Ven3.1.Sử dụng sơ đồ VenXé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)Bài giảng Toán tổ hợp(1)3/343.1. Sử dụng sơ đồ VenVí 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 = 30Bài giảng Toán tổ hợp4/343.1. Sử dụng sơ đồ VenVí 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).Ta 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!) = 2338560Bài giảng Toán tổ hợp5/34