Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác
Ví dụ. Một trường học có 100 sinh viên, trong đó có 50 sinh viên học tiếng Anh, 40 sinh viên học tiếng Pháp và 20 sinh viên học cả tiếng Anh và tiếng Pháp. Hỏi có bao nhiêu sinh viên không học tiếng Anh lẫ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 sinh viê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 = 30
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 1 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 1](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-1_PguG5hq89Z.jpg)
Trang 1
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 2 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 2](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-2_Vr2Emif0PK.jpg)
Trang 2
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 3 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 3](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-3_TfCpUldj63.jpg)
Trang 3
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 4 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 4](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-4_mNrecB0n9N.jpg)
Trang 4
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 5 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 5](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-5_JNGwd9W1AA.jpg)
Trang 5
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 6 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 6](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-6_pytvS7O4oS.jpg)
Trang 6
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 7 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 7](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-7_agr31n1qsP.jpg)
Trang 7
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 8 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 8](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-8_rkm0bPhTe5.jpg)
Trang 8
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 9 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 9](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-9_PV4Sx1As5B.jpg)
Trang 9
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 10 Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác trang 10](https://s1.ebooks.com.vn/yetwygzggocsqsc5/image/2024/02/07/5667/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac-trang-10_XwMoRwXh8J.jpg)
Trang 10
Tải về để xem bản đầy đủ
Bạn đang xem 10 trang mẫu của tài liệu "Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác
![Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác Bài giảng Toán tổ hợp - Chương 3: Một số kỹ thuật đếm khác](https://s1.ebooks.com.vn/yetwygzggocsqsc5/thumb/2024/01/13/bai-giang-toan-to-hop-chuong-3-mot-so-ky-thuat-dem-khac_qROosnhb6j.jpg)
Bài giảng Toán tổ hợp Đại học Khoa học Tự nhiên, Tp HCM Bài giảng Toán tổ hợp 1/34 Nội dung chương 3 Nội dung Chương 3. MỘT SỐ KỸ THUẬT ĐẾM KHÁC 1. Sử dụng sơ đồ Ven 2. Nguyên lý bù trừ 3. Đa thức quân xe Bài giảng Toán tổ hợp 2/34 3.1. Sử dụng sơ đồ Ven 3.1.Sử dụng sơ đồ Ven Xét sơ đồ Ven Ta ký hiệu U là tập vũ trụ A là phần bù của A trong U N(A) là số phần tử của A. N = N(U) Khi đó N(A ∩B) = N −N(A)−N(B) +N(A ∩B) (1) Bài giảng Toán tổ hợp 3/34 3.1. Sử dụng sơ đồ Ven Ví dụ. Một trường học có 100 sinh viên, trong đó có 50 sinh viên học tiếng Anh, 40 sinh viên học tiếng Pháp và 20 sinh viên học cả tiếng Anh và tiếng Pháp. Hỏi có bao nhiêu sinh viên không học tiếng Anh lẫ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 sinh viê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 = 30 Bài giảng Toán tổ hợp 4/34 3.1. Sử dụng sơ đồ Ven Ví 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ới chữ 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 được N(A ∩B)= N −N(A)−N(B) +N(A ∩B) = 10!− (2× 9!)− (2× 9!) + (2× 2× 8!) = 2338560 Bài giảng Toán tổ hợp 5/34 3.1. Sử dụng sơ đồ Ven Câ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) (2) Bài giảng Toán tổ hợp 6/34 3.1. Sử dụng sơ đồ Ven Đối với trường hợp 3 tập hợp là A1, A2, A3, ta có thể viết công thức (2) như sau: N(A1 ∩A2 ∩A3) = N − ∑ i N(Ai)+) ∑ i 6=j N(Ai ∩Aj)−N(A1 ∩A2 ∩A3) Ví dụ. Một trường có 100 sinh viên trong đó có 40 sinh viên học tiếng Anh, 40 sinh viên học tiếng Pháp, 40 sinh viên học tiếng Đức, mỗi cặp ngôn ngữ có 20 sinh viên học và có 10 sinh viên học cả 3 ngôn ngữ. Hỏi có bao nhiêu sinh viên không học cả 3 tiếng Anh, Pháp và Đức? Giải. Ta có N = 100, N(A) = N(P ) = N(D) = 40, N(A ∩ P ) = N(P ∩D) = N(A ∩D) = 20, và N(A ∩ P ∩D) = 10. Theo công thức (2) ta được N(A ∩ P ∩D) = 100− (40 + 40 + 40) + (20 + 20 + 20)− 10 = 30. Ví dụ. Có bao nhiêu số nguyên dương ≤ 70 mà nguyên tố cùng nhau với 70? Bài giảng Toán tổ hợp 7/34 3.1. Sử dụng sơ đồ Ven Nhận xét. Số các số nguyên dương ≤ n mà chia hết cho k là phần nguyên n/k. Giải. Gọi U là tập hợp các số nguyên dương ≤ 70. Ta có ước nguyên tố của 70 là 2, 5 và 7. Do đó muốn đếm các số nguyên tố cùng nhau với 70 ta cần đếm những số không chia hết cho 2, 5 hoặc 7. Gọi A1, A2 và A3 lần lượt là tập các số nguyên trong U chia hết cho 2, 5 và 7. Khi đó đáp án cần tìm của bài toán là N(A1 ∩A2 ∩A3). Ta có N = 70, N(A1) = 70/2 = 35, N(A2) = 70/5 = 14, N(A3) = 70/7 = 10 Ta có một số chia hết cho 2 và 5 khi và chỉ khi số đó chia hết cho 10. Do đó N(A1 ∩A2) = 70/10 = 7. Tương tự ta có, N(A2 ∩A3) = 70 5× 7 = 2, N(A1 ∩A3) = 70 2× 7 = 5. Bài giảng Toán tổ hợp 8/34 3.1. Sử dụng sơ đồ Ven N(A1 ∩A2 ∩A3) = 70 2× 5× 7 = 1. Áp dụng công thức (2) ta có N(A1 ∩A2 ∩A3) = 70− (35 + 14 + 10) + (7 + 2 + 5)− 1 = 24. Ví dụ. Có bao nhiêu số nguyên dương ≤ 1000 mà nguyên tố cùng nhau với a) 50 b) 210 Bài giảng Toán tổ hợp 9/34 3.2. Nguyên lý bù trừ 3.2. Nguyên lý bù trừ Trong phần này chúng ta sẽ mở rộng công thức ở phần 1 cho trường hợp n tập hợp A1, A2, . . . , An. Để đơn giản về mặt ký hiệu chúng ta viết “ ∩ ” như là phép nhân. Ví dụ A1 ∩A2 ∩A3 sẽ được viết thành A1A2A3. Bằng việc sử dụng ký hiệu này, ta có số lượng phần tử không thuộc tất cả các tập A1, A2, . . . , An sẽ được viết là N(A1A2 . . . An). Định lý. Cho tập vũ trụ U có N phần tử và A1, A2, . . . , An là n tập hợp con của U. Ta đặt Sk là tổng số phần tử của tất cả tập giao của đúng k tập hợp từ các {Ai}i=1,...,n, cụ thể S1 = ∑ i N(Ai), S2 = ∑ i 6=j N(AiAj), . . . , Sn = N(A1A2 . . . An). Khi đó N(A1A2 . . . An) = N + ∑ k (−1)kSk = N − S1 + S2 − . . .+ (−1)kSk + . . .+ (−1)nSn Bài giảng Toán tổ hợp 10/34 3.2. Nguyên lý bù trừ Hệ quả. Cho A1, A2, . . . , An là n tập hợp con của tập vũ trụ U. Khi đó N(A1 ∪ . . . ∪An) = ∑ k≥1 (−1)k−1Sk = S1 − S2 + . . .+ (−1)k−1Sk + . . .+ (−1)n−1Sn Chứng minh. Từ Định lý trên ta có N(A1 . . . An) = N − S1 + S2 − . . .+ (−1)kSk + . . .+ (−1)nSn = N − ( S1 − S2 + . . .+ (−1)k−1Sk + . . .+ (−1)n−1Sn ) . Mặt khác N(A1 ∪ . . . ∪An) = N −N(A1 . . . An). Do đó ta có điều phải chứng mình Ví dụ. Tìm số nghiệm nguyên không âm của phương trình x1 + x2 + x3 + x4 = 18 (∗) thỏa điều kiện xi ≤ 7, ∀i = 1, . . . , 4. Bài giảng Toán tổ hợp 11/34 3.2. Nguyên lý bù trừ Giải. Gọi U là
File đính kèm:
bai_giang_toan_to_hop_chuong_3_mot_so_ky_thuat_dem_khac.pdf