Các phép toán tập hợpPhần bù: của A trong X ký hiệu A là các phần tử của X không thuộc vào A. Hợp: A và B ký hiệu A B là các phần tử hoặc thuộc vào A hoặc thuộc vào B hoặc thuộc vào cả A và B | Toán Rời Rạc Giảng viên: Ths. Trần Xuân Sang E-mail: transang1981dhv@ Chương I: Lý thuyết tổ hợp Nội dung Một số nguyên lý cơ bản Bài toán đếm Bài toán tồn tại Bài toán liệt kê Công thức truy hồi Một số nguyên lý cơ bản Nội dung Các phép toán tập hợp Nguyên lý nhân Nguyên lý cộng Nguyên lý bù trừ Nguyên lý quy nạp Bài tập Phần bù: của A trong X ký hiệu A là các phần tử của X không thuộc vào A. Hợp: A và B ký hiệu A B là các phần tử hoặc thuộc vào A hoặc thuộc vào B hoặc thuộc vào cả A và B Giao: của A và B, ký hiệu A B là các phần tử đồng thời thuộc vào cả A và B Tích Đêcac: A x B = {(a,b)|a A, b B} Các phép toán tập hợp Nguyên lý nhân Nếu mỗi thành phần ai của bộ có thứ tự k thành phần (a1,a2,.ak) có ni khả năng chọn thì số bộ được tạo ra là tích số của các khả năng này n1n2nk Vd1: Đi qua các chăng đường Vd2: Chương trình vòng for lồng nhau Vd3: Có bao nhiêu tên biến trong Pascal độ dài 10 chỉ chứa hai chữ cái A,B bắt đầu bởi AAA hoặc ABA (KQ 256) Nguyên lý cộng Nếu A và B là hai tập hợp rời nhau thì N(A B) = N(A)+N(B) Có thể mở rộng ra cho n tập Vd1: Chương trình pascal các vòng for ko lồng nhau Vd2: Có 90 đề tài toán, 10 đề tài tin học. Mỗi sinh viên được chọn 1 đề tài. Hỏi 1 sinh viên có bao nhiêu khả năng lựa chọn đề tài. Nguyên lý bù trừ Có bao nhiêu phần tử trong hợp của hai tập hợp hữu hạn N(A B) = N(A)+N(B)- N(A B ) Vd1: Trong trường có 1807 sinh viên năm thứ nhất. Trong số này có 453 sv chọn môn tin học, 576 sv chọn môn toán và 299 sv chọn cả hai môn toán và tin. Có bao nhiêu sinh viên không học toán cũng không học tin. (Kq 1807-721=1086) Vd2: Tính: N(A B C) Nguyên lý quy nạp Chứng minh P(n) đúng với mọi số nguyên dương n thì cần hai bước B1: Bước cơ sở: Chỉ ra P(1) là đúng B2: Bước quy nạp: Chứng minh phép kéo theo p(n) -->P(n+1) là đúng với mọi số nguyên dương n, trong đó P(n) được gọi là giả thiết quy nạp. Vd1: Chứng minh 1+3+5+(2n-1) = n2 vd2: Chứng minh: n Bài toán đếm | Toán Rời Rạc Giảng viên: Ths. Trần Xuân Sang E-mail: transang1981dhv@ Chương I: Lý thuyết tổ hợp Nội dung Một số nguyên lý cơ bản Bài toán đếm Bài toán tồn tại Bài toán liệt kê Công thức truy hồi Một số nguyên lý cơ bản Nội dung Các phép toán tập hợp Nguyên lý nhân Nguyên lý cộng Nguyên lý bù trừ Nguyên lý quy nạp Bài tập Phần bù: của A trong X ký hiệu A là các phần tử của X không thuộc vào A. Hợp: A và B ký hiệu A B là các phần tử hoặc thuộc vào A hoặc thuộc vào B hoặc thuộc vào cả A và B Giao: của A và B, ký hiệu A B là các phần tử đồng thời thuộc vào cả A và B Tích Đêcac: A x B = {(a,b)|a A, b B} Các phép toán tập hợp Nguyên lý nhân Nếu mỗi thành phần ai của bộ có thứ tự k thành phần (a1,a2,.ak) có ni khả năng chọn thì số bộ được tạo ra là tích số của các khả năng này n1n2nk Vd1: Đi qua các chăng đường Vd2: Chương trình vòng for lồng nhau Vd3: Có bao nhiêu tên biến trong Pascal độ dài 10 chỉ chứa hai chữ cái A,B bắt đầu bởi AAA hoặc ABA (KQ 256)
