Bài giảng Toán rời rạc - Chương 3: Một số công thức tổ hợp - Bùi Thị Thủy

TOÁN RỜI RẠC (DISCRETE MATHEMATICS) Bùi Thị Thủy Đặng Xuân Thọ Support  Full name: Đặng Xuân Thọ  Mobile: 091.2629.383  Email: thodx@hnue.edu.vn  Website: Toán Rời Rạc - ĐHSPHN 2 NỘI DUNG  Chương 1. Logic mệnh đề  Chương 2. Lý thuyết tập hợp  Chương 3. Một số công thức tổ hợp  Chương 4. Suy luận và kiểm chứng chương trình  Chương 5. Đại số Boole và cấu trúc mạch logic  Chương 6. Thuật toán  Chương 7. Lý thuyết đồ thị Toán Rời Rạc - ĐHSPHN 3 Chương 3. Một số công thức tổ hợp  “Đánh giá số điện thoại nhiều nhất có thể có trong Hà Nội.”  “Xác định số mật khẩu, mỗi mật khẩu gồm sáu, bảy, hoặc tám ký tự; mỗi ký tự có thể chữ hoặc số; mỗi mật khẩu chứa ít nhất một chữ.”  Một số công thức tổ hợp  Chỉnh hợp  Hoán vị  Hoán vị trên đường tròn  Toán Rời Rạc - ĐHSPHN 4 Cơ sở của phép đếm Toán Rời Rạc - ĐHSPHN 5 Cơ sở của phép đếm  Phần này chúng ta chỉ giải quyết xác định lực lượng của tập hợp hữu hạn.  Nếu tập hợp A là tập hợp hữu hạn, thì lực lượng của nó là số lượng phần tử của nó, ký hiệu là 𝐴 .  Định lý: Nếu Ai (i=1,2,..n) là một phân hoạch của tập hợp A thì ta có 𝐴𝑖 𝑛 𝑖=1 = 𝐴 . Toán Rời Rạc - ĐHSPHN 6 Số phần tử của tích Đêcac  Ví dụ: Cho tập hợp A={a,b}. Tìm tất cả các dãy ký tự có ba phần tử được tạo thành từ A?  aaa, aab, bbb, bba, abb, baa, aba, bab  Định lý: cho trước các tập hợp hữu hạn Ai (i=1,..,k) trong đó tập hợp Ai có đúng ni phần tử. Khi đó tích Đêcac A1 x A2 x x Ak có đúng n1n2nk phần tử. Nghĩa là: 𝐴1 × 𝐴2 ×⋯×𝐴𝑘 = 𝐴1 × 𝐴2 × 𝐴𝑘  Đặc biệt ta có: 𝐴𝑛 = 𝐴 𝑛 Toán Rời Rạc - ĐHSPHN 7 Số phần tử của tích Đêcac  Ví dụ: Có bao nhiêu số tự nhiên có chín chữ số mà trong biểu diễn thập phân của nó không có mặt chữ số nào trong tập hợp {0,3,7,9}? Mỗi số tự nhiên có chín chữ số không được viết bởi các chữ số {0,3,7,9} là một dãy chín kí tự có lặp của tập hợp {1,2,4,5,6,8}.  69 Toán Rời Rạc - ĐHSPHN 8 Hai nguyên lý cơ bản Toán Rời Rạc - ĐHSPHN 9 Cơ sở của phép đếm (1/2)  Nguyên lý cộng Giả sử có các công đoạn E1, E2,, Ek. Để thực hiện E ta chỉ cần thực hiện một trong những Ei (i = 1..k) trong đó số cách thực hiện Ei là ni. Khi đó số cách thực hiện E là n1 + n2 + + nk.  Ví dụ: Hà Nội TP. HCM 3 hãng hàng không 2 hãng tàu thủy 15 hãng giao thông đường bộ Có 3 + 2 + 15 = 20 cách 10 Cơ sở của phép đếm (2/2)  Nguyên lý nhân Giả sử có công đoạn E được thực hiện lần lượt qua các công đoạn E1, E2, , Ek trong đó số cách thực hiện Ei là ni (i = 1, k). Khi đó số cách thực hiện E là n1 x n2 x x nk  Ví dụ: Hà Nội TP. HCM 4 cách 8 cách Có 8 * 4 = 32 cách Đà Nẵng Toán Rời Rạc - ĐHSPHN 11 Một Số Công Thức Tổ Hợp Toán Rời Rạc - ĐHSPHN 12  Khái niệm. Hoán vị của một tập các đối tượng khác nhau là một cách sắp xếp có thứ tự các đối tượng này.  Bài toán. Cho tập A có n phần tử. Hãy tính số các hoán vị khác nhau của tập A.  Ví dụ: cho A={a,b,c,d} tìm tất cả các hoán vị có thể có của tập hợp A?  Định lý. Số các hoán vị khác nhau của một tập n phần tử là Pn = n! Hoán vị Toán Rời Rạc - ĐHSPHN 13  Ví dụ: Hãy tính số các số sau:  Có năm chữ số được viết bởi đúng 5 chữ số 1, 2, 3, 4 và 5?  Có năm chữ số được viết bởi đúng 5 chữ số 1, 2, 3, 4 và 5 trong đó ba chữ số đầu là ba chữ số lẻ, hai chữ số sau là hai chữ số chẵn? Hoán vị Toán Rời Rạc - ĐHSPHN 14 Hoán vị trên đường tròn  Ví dụ: Cho tập hợp A = {a,b,c,d}. Tìm tất cả các hoán vị khác nhau của các phần tử của A trên đường tròn? Toán Rời Rạc - ĐHSPHN 15  Bài toán: Tính số các hoán vị khác nhau của một tập hợp A gồm n phần tử nằm trên một đường tròn?  Định lý: Số các hoán vị tròn khác nhau của tập hợp A có n phần tử là Qn = (n – 1)! Hoán vị trên đường tròn Toán Rời Rạc - ĐHSPHN 16 Chỉnh hợp  Bài toán: Cho tập A có n phần tử và số k≤n (kN). Mỗi dãy độ dài k được xếp bởi các phần tử của tập A trong đó mỗi phần tử có mặt không quá một lần được gọi là một dãy k phần tử không lặp của A.  Tính số các dãy đó? Toán Rời Rạc - ĐHSPHN 17 Chỉnh hợp  Định lý: Cho trước tập A có n phần tử và một số tự nhiên k ≤ n. Số các dãy k phần tử không lặp của A là:  Ví dụ: có bao nhiêu số có 4 chữ số mà trong biểu diễn thập phân của nó không có 2 chữ số nào giống nhau và không có mặt chữ số chẵn? Toán Rời Rạc - ĐHSPHN 18 Chỉnh hợp lặp  Cho tập A có n phần tử. Khi đó số dãy gồm k phần tử có lặp thuộc tập A là nk và được gọi là chỉnh hợp lặp chập k của n phần tử.  Ví dụ: có bao nhiêu số tự nhiên có 9 chữ số mà trong biểu diễn thập phân của nó không có mặt chữ số nào trong tập hợp {0,1,2,3,4,5}? Toán Rời Rạc - ĐHSPHN 19 Chỉnh hợp với tần số lặp cho trước  Định lý: Cho trước một tập hợp A có n phần tử. Số các dãy k phần tử có lặp (k1+k2++kn) và (k=k1++kn) là:  Ví dụ: Tính các số tự nhiên có 7 chữ số, trong đó có 3 chữ số 1, 2 chữ số 2 và 2 chữ số 3. 1 2 1 2 ! ( , ,..., ) ! !... ! n n k P k k k k k k  Toán Rời Rạc - ĐHSPHN 20  Tổ hợp chập k của n phần tử là số các tập hợp con k phần tử của một tập n phần tử cho trước (không có thứ tự).  Ví dụ: Cho tập hợp A={a,b,c,d}. Tìm tất cả các tập hợp hai phần tử của A?  {a,b}; {a,c}; {a,d}; {b,c}; {b,d}; {c,d}  Định lý. Số tập hợp con k phần tử của một tập A có n phần tử cho trước là: Tổ hợp Toán Rời Rạc - ĐHSPHN 21  Ví dụ 1. Có bao nhiêu cách tuyển 5 trong số 10 cầu thủ của một đội bóng để đi thi đấu tại một trường khác?  Ví dụ 2. Trong 10 cầu thủ trên, có 3 cầu thủ nữ. Hỏi có bao nhiêu cách chọn 5 cầu thủ đi thi đấu trong đó có 2 cầu thủ nữ. Tổ hợp Toán Rời Rạc - ĐHSPHN 22 Luyện tập 1. Có bao nhiêu số tự nhiên có 5 chữ số đôi một khác nhau? 2. Có bao nhiêu máy điện thoại có 6 chữ số? Và trường hợp 6 chữ số đôi một khác nhau? 3. Cho A={1,2,3,4,5,6,7}. Có bao nhiêu số tự nhiên có 5 chữ số lấy từ A sao cho:  Có chữ số đầu là 3  Không tận cùng bằng chữ số 4  Cứ 2 chữ số kề nhau là khác nhau  Không bắt đầu bằng 123 23 Luyện tập Toán Rời Rạc - ĐHSPHN 24 4. Một lớp học có 40 học sinh với 25 nam và 15 nữ. Có mấy cách chọn 4 học sinh sao cho: a. Chọn nam, nữ tùy ý b. Chọn 2 nam và 2 nữ c. Tính xác suất để chọn ít nhất một nữ 5. Tìm số đường chéo của đa giác lồi có n cạnh. (Đa giác lồi là đa giác có tính chất kéo dài bất kỳ cạnh nào đều không cắt đa giác. Khi đó 2 đỉnh bất kỳ nối lại, được hoặc cạnh hoặc đường chéo.) Luyện tập Toán Rời Rạc - ĐHSPHN 25 6. Từ tập A = {0,1,2,3,4,5} lập được bao nhiêu số tự nhiên có 8 chữ số sao cho: - chữ số 2 có mặt 3 lần - mỗi chữ số còn lại có mặt 1 lần 7. Xét tam giác có đỉnh lấy từ một đa giác lồi có 20 cạnh. a. Có bao nhiêu tam giác nói trên? b. Tính xác suất để chọn được tam giác có đúng 1 cạnh chung với đa giác? c. Có bao nhiêu tam giác có đúng 2 cạnh chung với đa giác? d. Tính xác suất để chọn được tam giác không có cạnh chung với đa giác? Khai triển lũy thừa của đa thức Toán Rời Rạc - ĐHSPHN 26 Hệ số tam giác Pascal Toán Rời Rạc - ĐHSPHN 27 (a+b)2 = a2 + 2ab + b2 (a+b)3 = a3 + 3a2b + 3ab2 + b3 (a+b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4 1 2 1 1 3 3 1 1 4 6 4 1 Nhị thức Newton  Định lý. Cho mỗi số tự nhiên n  1 ta có: = C0nb n + C1nab n-1 + C2na 2bn-2 + + Cn-1na n-1b + Cnna n Toán Rời Rạc - ĐHSPHN 28      n k kknk n n baCba 0 Nhị thức Newton Toán Rời Rạc - ĐHSPHN 29  Tính chất: 1 1 1 1 1 1 1 2 1. 2. 3. ... k n k n n k k k n n n k k k k n n n n k C C C C C C C C C                  Ví dụ Toán Rời Rạc - ĐHSPHN 30  Ví dụ 1: Tính A = C0n + C 1 n + + C n n Chọn x=1 thì: 2n = C0n + C 1 n + + C n n       n k kk n n k knkk n n xCxCx 00 11 = C0n + C 1 nx + C 2 nx 2 + + Cn-1nx n-1 + Cnnx n Luyện tập Toán Rời Rạc - ĐHSPHN 31 8. CM: C02n+C 2 2n+..+C 2n 2n=C 1 2n+C 3 2n+..+C 2n-1 2n       n k kk n n k knkk n n xCxCx 2 0 2 2 0 2 2 2 11 Với x = -1 thì: 0 = C02n - C 1 2n + C 2 2n – C 3 2n+-C 2n-1 2n+C 2n 2n C02n+C 2 2n++C 2n 2n = C 1 2n+C 3 2n++C 2n-1 2n Luyện tập Toán Rời Rạc - ĐHSPHN 32 9. Khai triển đa thức: P(x)=(x+1)10 + (x+1)11 + (x+1)12 + (x+1)13 + (x+1)14 ra dạng: P(x) = a0 + a1x + a2x 2 + + a14x 14. tính a10? Khai triển lũy thừa của đa thức  Định lý. Cho m, n là 2 số nguyên dương. Khi đó ta có: tổng được lấy trên tất cả các bộ m số tự nhiên (k1,k2,,km) sao cho k1 + k2 ++ km = n. 1 2 1 2 1 2 1 2 ... 1 2 ! ( ... ) ... ! !... ! m m kk kn m m k k k n m n x x x x x x k k k         Toán Rời Rạc - ĐHSPHN 33 Ví dụ Toán Rời Rạc - ĐHSPHN 34 Tất cả các bộ (k1,k2,k3) sao cho k1+k2+k3=3 là: (3,0,0), (2,1,0), (2,0,1), (1,2,0), (1,0,2), (1,1,1), (0,3,0), (0,2,1), (0,1,2), (0,0,3).      3 321 321 3 321 321 321 !!! !3 kkk kkk xxx kkk xxx Công thức Tổ hợp trong tập hợp 35 Toán Rời Rạc - ĐHSPHN Số phần tử của một hợp các tập hợp Toán Rời Rạc - ĐHSPHN 36  Ví dụ: Bài kiểm tra Toán có 2 câu hỏi. Cả lớp có 30 em làm được câu thứ nhất, 20 em làm được câu thứ hai, và chỉ có 10 em làm được cả hai câu. Tìm số học sinh cả lớp?  A tập hợp học sinh giải được câu thứ nhất  B tập hợp học sinh giải được câu thứ hai  A∩B là tập hợp học sinh giải được cả hai câu  |A∪B| = |A| + |B| - |A∩B| = 30+20–10 = 40 em Số phần tử của một hợp các tập hợp Toán Rời Rạc - ĐHSPHN 37 |A∪B| = |A| + |B| - |A∩B| |A∪B∪C| = |A|+|B|+|C|-|A∩B|-|B∩C|-|C∩A|+|A∩B∩C| Định lý: cho trước các tập hợp A1,A2,..An. Khi đó: |A1∪A2∪⋯An|= |Ai|- |Ai∩Bj|++(-1) n+1|A1∩A2∩⋯An| Luyện tập Toán Rời Rạc - ĐHSPHN 38 10. Trong một kỳ thi học sinh giỏi Toán, Lý, Hóa. Biết rằng có 20 em thi Toán, 14 em thi Lý, 6 em thi cả Toán và Lý, 5 em thi cả Lý và Hóa, 2 em thi cả Toán và Hóa, và có 1 em tham gia cả 3 môn. Hỏi có bao nhiêu em? 11. Tính số các mật khẩu tạo được bằng cách hoán vị các chữ cái của từ “TINHOCTRE” sao cho không có hai chữ cái nào giống nhau đứng cạnh nhau? THANK YOU!