Thuyết trình cấu trúc rời rạc Chương 2. Phép đếm

CHƯƠNG 2. PHÉP ĐẾM ĐH QG TPHCM ĐH CNTT NỘI DUNG Định nghĩa: trong toán học, tập hợp có thể hiểu tổng quát là một sự tụ tập của một số hữu hạn hay vô hạn các đối tượng nào đó Nếu a là phần tử của tập hợp A, ta kí hiệu aA Và a không là phần tử của tập hợp A kí hiệu aA Hai tập hợp A và B bằng nhau khi mỗi phần tử của A đều thuộc B và ngược lại, kí hiệu A = B Tập hợp không chứa phần tử nào gọi là tập hợp rỗng, kí hiệu là  Chuong 2.phép đếm 1 Có nhiều cách để biểu diễn tập hợp Tập hợp có thể biểu diễn bằng lời ví dụ: A là tập hợp 4 số nguyên. Có thể biểu diễn cách liệt kê phần tử ví dụ: A = {1,2,3,4} Chương 2.phép đếm 2 Định nghĩa: cho 2 tập hợp A và B. A bao hàm trong tập B nếu mỗi phần tử của A đều thuộc tập hợp B. Ta nói rằng B bao hàm A (B chứa A) kí hiệu: A  B (hay B  A) Quan hệ “bao hàm trong” và tập hợp con Khi A  B ta nói A là một tập hợp con của tập hợp B Chương 2.phép đếm 3 Ví dụ: Quan hệ “bao hàm trong” và tập hợp con Chương 2.phép đếm 4 Quan hệ “bao hàm trong” và tập hợp con Tính chất: Chương 2.phép đếm 5 Tập hợp lũy thừa Định nghĩa: cho tập S, tập lũy thừa của S là tập của tất cả các tập con của S, kí hiệu là P(S) Chương 2.phép đếm 6 Chương 2.phép đếm 7 Chương 2.phép đếm 8 Chương 2.phép đếm 9 Chương 2.phép đếm 10 Chương 2.phép đếm 11 Chương 2.phép đếm 12 Ví dụ 1: cho 2 tập hợp A ={1,3,5) và B={1,2,3} Chương 2.phép đếm 13 Hằng đẳng thức tập hợp Chương 2.phép đếm 14 Hằng đẳng thức tập hợp Chương 2.phép đếm 15 Chứng minh tập hợp bằng nhau Chương 2.phép đếm 16 Chứng minh tập hợp bằng nhau Chương 2.phép đếm 17 Tổng quát hóa: Chương 2.phép đếm 18 Chương 2.phép đếm 19 2.1 Hoán vị 1 Bài toán : Trong giờ học môn Giáo dục quốc phòng, một tiểu đội học sinh gồm 10 người được xếp thành một hàng dọc. Hỏi có bao nhiêu cách xếp? Có bao nhiêu cách sắp xếp???? 20 Chương 2.phép đếm Trả lời: Định nghĩa hoán vị : Cho tập hợp A gồm n phần tử khác nhau(n>0).Khi sắp xếp phần tử này theo một thứ tự, ta được một Hoán vị các phần tử của tập A . Các cách xếp 10 người vào hàng là một hoán vị của 10 người đó. 21 Chương 2.phép đếm Định lý: Số các Hoán vị của một tập hợp có phần tử là: Pn= n!=n(n-1)....2.1 Quy ước : 0! = 1 Ví dụ 1: Sắp xếp 6 học sinh vào vào 6 cái ghế. Hỏi có bao nhiêu cách sắp xếp? Đáp án: P6 = 6!=1.2.3…6=720 22 Chương 2.phép đếm Ví dụ 1: Cho A ={a,b,c}. Khi đó A có các hoán vị sau: abc,acb, bac,bca, cab,cba Ví dụ 2: Cho X ={1,2,3,4,5}. Hỏi có bao nhiêu số tự nhiên gồm 5 chữ số khác nhau được tạo từ tập X →5! 23 Chương 2.phép đếm Chỉnh hợp: Bài toán: Trong trận chung kết bóng đá phải phân định thắng thua bằng đá luân lưu 11m . Huấn luyện viên của mỗi đội cần trình với trọng tài một danh sách sắp thứ tự 5 cầu thủ trong số 11 cầu thủ của đội để tham gia đá. Có bao nhiêu cách sắp xếp danh sách thứ tự 5 cầu thủ???? 24 Chương 2.phép đếm Trả lời: Định nghĩa chỉnh hợp : Cho A là tập hợp gồm n phần tử (khác nhau). Mỗi bộ phận gồm k phần tử( 0 k n) sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử. Số các chỉnh hợp chập k của n phần tử ký hiệu là: Danh sách có xếp thứ tự 5 cầu thủ được gọi là một chỉnh hợp chập 5 của 11 cầu thủ. Chương 2.phép đếm 25 Công thức : Nhận xét: Hai Chỉnh hợp khác nhau khi và chỉ khi hoặc có ít nhất một phần tử của Chỉnh hợp này không là phần tử của Chỉnh hợp kia hoặc các phần tử của Chỉnh hợp giống nhau nhưng được sắp xếp theo thứ tự khác nhau. Công thức: = Chương 2.phép đếm 26 Ví dụ 1: Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 3 là: Chương 2.phép đếm 27 Ví dụ 2: Có bao nhiêu số tự nhiên gồm 3 chữ số được tạo thành từ 1,2,3,4,5,6. Kết quả: ab, ba, ac, ca, bc, cb Tổ hợp: Bài toán: Một nhóm có 8 thành viên ,chọn 3 người lên thuyết trình.Hỏi có bao nhiêu cách chọn ???? Chương 2.phép đếm 28 Đáp Án : Chọn 3 người trong 8 người là một tổ hợp chập 3 của 8 Định nghĩa: Cho A có n phần tử và số nguyên k với 0 k n . Mỗi tập con của A có k phần tử gọi là một tổ hợp chập k của n phần tử(gọi tắt là tổ hợp chập k của A). Định lý: Số các tổ hợp chập k của n phần tử với (0 k n) là : Chương 2.phép đếm 29 Tính chất: = = = 1 = = n = + ( k 1) Khác nhau của chỉnh hợp và tổ hợp?? Chỉnh hợp : quan tâm đến thứ tự của các phần tử, còn tổ hợp thì không Chương 2.phép đếm 30 Ví dụ 1: Cho X = {1,2,3,4}. Tổ hợp chập 3 của 4 phần tử của X là : Chương 2.phép đếm 31 Ví dụ 2: Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn -Số cách chọn là tổ hợp chập 10 của 30 là: {1,2,3}, {1,2,4}, {1,3,4} , {2,3,4} . Công thức : (x+y)n = x0yn + x1 yn-1 +…+ xny0 = xkyn-k Tính chất : Số các số hạn của công thức là n+1 Tổng các số mũ của x và y trong mỗi số hạng luôn luôn bằng số mũ của nhị thức: k+n-k= n Chương 2.phép đếm 32 Số hạng tổng quát của nhị thức là: : Các hệ số nhị thức cách đều hai số hạn đầu và cuối thì bằng nhau. ... Ví dụ: (x+y)6 = x0y6 + x1y5 + x2y4 + x3y3 + + x4y2 + x5y1 + x6y0 Chương 2.phép đếm 33 Một số khai triển hay sử dụng: … Chương 2.phép đếm 34 Chương 2.phép đếm 35 Ví dụ: Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp xếp các chữ cái của từ SUCCESS? Chương 2.phép đếm 36 Chương 2.phép đếm 37 Ví dụ. Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn. Chương 2.phép đếm 38 Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể AA, AB, AC, BB, BC, CC 2.6 Tổ hợp lặp Chương 2.phép đếm 39 Chương 2.phép đếm 40 Chương 2.phép đếm 41 Chương 2.phép đếm 42 Chương 2.phép đếm 1. Định nghĩa 2. Công thức Ví dụ : An có 3 áo tay dài và 5 áo tay ngắn , đế chọn 1 cái thì An có mấy cách chọn ? 3 + 5 =8 3. Mở rộng Chương 2.phép đếm 43 44 Chương 2.phép đếm Giả sử làm công việc A cần 2 bước - Bước 1 có n cách làm - Bước 2 có m cách làm Khi đó số cách làm công việc A là n.m Chương 2.phép đếm 45 1. Định nghĩa 2. Công thức Ví dụ : Cho X ={ 1,2,3,4,5,0}Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau mà chia hết cho 2 Chương 2.phép đếm 46 TH2 : c ≠ 0. Khi đó c có 2 cách chọn a có 4 cách chọn ( a ϵ X\{c,0} ) b có 4 cách chọn (b ϵ X\{a,c} ) TH2 có 2.4.4 = 32 cách chọn Vậy có 32 + 20 = 52 cách chọn Chương 2.phép đếm 47 48 Chương 2.phép đếm Công thức (1) còn gọi là nguyên lý bù trừ cho 2 tập hợp Chương 2.phép đếm 49 1. Công thức Tổng quát hơn, ta có: Chương 2.phép đếm 50 Chương 2.phép đếm 51 2. Chứng minh Ví dụ: Trong một lớp ngoại ngữ Anh Pháp. Có 24 HS học Tiếng Pháp, 26 học sinh học Tiếng Anh. 15 học sinh học Tiếng Anh và Tiếng Pháp. Hỏi lớp có bao nhiêu người ? Giải Gọi A là những học sinh học Tiếng Pháp B là những học sinh học Tiếng Anh Chương 2.phép đếm 52 53 Chương 2.phép đếm Nguyên lý Dirichlet do nhà toán học người Đức là Dirichlet đề xuất từ thế kỉ XX đã được áp dụng để chứng minh sự tồn tại nghiệm trong nhiều bài toán tổ hợp. Nguyên lý này được phát triển từ mệnh đề gọi là nguyên lý “nguyên lý quả cam” hay là nguyên lý  “chuồng chim bồ câu”: Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắc chắn có ít nhất một ngăn có nhiều hơn một con chim. 1. Giới thiệu 54 Chương 2.phép đếm Một cách tổng quát, nguyên lý Dirichlet được phát biểu như sau:       Nếu xếp nhiều hơn n+1 đối tượng vào n cái hộp thì tồn tại ít nhất một hộp chứa không ít hơn hai đối tượng.      - Chứng bằng lập luận phản chứng: Giả sử không hộp nào chứa nhiều hơn một đối tượng thì chỉ có nhiều nhất là n đối tượng được xếp trong các hộp, trái với giả thiết là số đối tượng lớn hơn n. 2. Nguyên lý Dirichlet cơ bản 55 Chương 2.phép đếm 3. Nguyên lý Dirichlet mở rộng a. Nguyên lý 56 Chương 2.phép đếm b. Chứng minh 57 Chương 2.phép đếm Ví dụ : Cho tập X ={1,2,3,4,5,6,7,8,9}. Lấy A là tập hợp con của X gồm 6 phần tử. Khi đó trong A sẽ có 2 phần tử có tổng bằng 10 Ta lập các chuồng như sau: {1,9},{2,8},{3,7},{4,6},{5} Do A có 6 phần tử nên trong 6 phần tử đó sẽ có 2 phần tử trong một chuồng. Suy ra đpcm 58 Chương 2.phép đếm