Oán ứng dụng - Bài 2: Bài toán đếm và bài toán tồn tại

guyên lý nhân 3.3 Nguyên lý bù trừ 4. GIẢI TÍCH TỔ HỢP 4.1 Hốn vị 4.2 Chỉnh hợp 4.3 Tổ hợp 4.4 Hốn vị lặp 4.5 Tổ hợp và chỉnh hợp lặp 5. BÀI TỐN TỒN TẠI 5.1 Nguyên lý Dirichlet 5.2 Nguyên lý Dirichlet tổng quát BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.1 Khái niệm Tập hợp là một khái niệm cơ bản của Tốn học, khơng được định nghĩa. Cĩ thể hiểu tập hợp là một nhĩm đối tượng cĩ chung một tính chất nào đĩ. Ví dụ: 1) Tập hợp sinh viên một trường đại học. 2) Tập hợp các số nguyên 3) Tập hợp các bài thơ của Nguyễn Bính. Cơ sở Logic BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.1 Khái niệm Những đối tượng tạo thành một tập hợp gọi là phần tử (hay điểm) của tập hợp. Nếu a là một phần tử của tập hợp A, ta viết aA (đọc "a thuộc A") Trường hợp ngược lại, ta viết a A (đọc "a khơng thuộc A") Cơ sở Logic BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Tập hợp 1.2 Diễn tả tập hợp Cách 1: Bằng lời "A là tập hợp bốn số nguyên dương đầu tiên" "B là tập hợp các màu trên quốc kỳ Pháp" Cách 2: Liệt kê các phần tử, đặt giữa cặp { } X = {4, 2, 1, 3} Y= {đỏ, trắng, xanh} Cách 3: Đưa ra tính chất đặc trưng A={ n N | n chia hết cho 3} Cơ sở Logic BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.3 Lực lượng của tập hợp Số phần tử của tập hợp A được gọi là lực lượng của tập hợp, kí hiệu |A|. Nếu tập hợp A cĩ hữu hạn phần tử, ta nĩi A hữu hạn. Ngược lại, ta nĩi A vơ hạn. Tập hợp khơng cĩ phần tử nào gọi là tập hợp rỗng, kí hiệu là Ø Ví dụ Tập hợp số N, Z, R, là các tập vơ hạn Tập hợp X={1,3,4,5} là tập hữu hạn, Ta cĩ: |X|=4 1. Tập hợp BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.4 Tập hợp con Nếu mọi phần tử của tập hợp B đều là phần tử của tập hợp A thì ta nĩi B là tập hợp con của A (hay B được bao hàm trong A). Kí kiệu: B  A hay A  B B  A  (x | x B  x A) P(A)-là kí hiệu tập hợp tất cả tập con của A Ví dụ A={1,2}, B={1} - là tập con của A P(A)={Ø,{1},{2},{1,2}} Ø: là tập con của mọi tập hợp 1. Tập hợp BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.5 Biểu đồ Venn Biểu diễn tập hợp bởi một đường cong kín Mỗi phần tử của tập hợp được đặc trưng bởi điểm nằm trong đường cong ấy Ví dụ A  B C ≠ D 1. Tập hợp AB C D BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.6 Các phép tốn trên tập hợp Phép hợp: Hợp của tập hợp A và B là một tập hợp tạo bởi tất cả các phần tử thuộc A hoặc thuộc B. Ký hiệu: A  B A  B= {x  xA  xB} Ví dụ A= {a,b,c,d} B= {c,d,e,f} A  B = {a,b,c,d,e,f} A B 1. Tập hợp BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.6 Các phép tốn trên tập hợp Phép giao: Giao của tập hợp A và B là một tập hợp tạo bởi các phần tử thuộc A và thuộc B. Ký hiệu: A  B A  B ={x  xA  xB} Ví dụ A= {a,b,c,d} B= {c,d,e,f} A  B = {c,d} 1. Tập hợp A B A BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.6 Các phép tốn trên tập hợp Hiệu của hai tập hợp: Hiệu của tập hợp A với B là một tập hợp tạo bởi tất cả các phần tử thuộc tập A mà khơng thuộc tập B. Kí hiệu: A\B A\B= { x  xA  xB} Phần bù: Cho B  A, A\B gọi là bù của B trong A Ví dụ A= {a,b,c,d} B= {c,d,e,f} A\B = {a,b} 1. Tập hợp A BB A\B BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.7 Tính chất của phép tốn trên tập hợp a/. Tính giao hốn: A  B = B  A A  B = B  A. b/. Tính kết hợp: (A  B)  C = A  (B  C) (A  B)  C = A  (B  C) c/. Tính phân phối: A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C) 1. Tập hợp BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.7 Tính chất của phép tốn trên tập hợp d/. Cơng thức De Morgan: e/. Tính lũy đẳng: A  A = A A  A = A 1. Tập hợp BABAvàBABA  BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.8 Tích Descartes của các tập hợp Tích Descartes của tập hợp A với tập hợp B là tập hợp gồm tất cả các cặp thứ tự (x,y) với xA và xB Ký hiệu là A B hoặc A.B A B = {(x,y)| xA, yB} Tích của 2 tập hợp khơng cĩ tính chất giao hốn. |A x B| = |A| x |B| 1. Tập hợp BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1.8 Tích Descartes của các tập hợp Tích Đề các của n tập hợp A1, A2,..., An là tập mọi dãy cĩ thứ tự (x1,x2,...,xn), trong đĩ xi  Ai (i=1,...,n) Kí hiệu A1. A2... An A1. A2...An = {(x1,x2,...,xn)  xiAi (i=1,...,n) } Cách viết khác: 1. Tập hợp  i i i I i i i I A (x ) i I , x A      BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2.1 Khái niệm Một quan hệ hai ngơi giữa tập hợp A và tập hợp B là tập con R của AxB. Kí hiệu: R  A x B. Viết a R b thay cho (a, b)  R Quan hệ từ A đến A được gọi là quan hệ trên A 2. Quan hệ R = { (a1, b1), (a1, b3), (a3, b3) } BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2.1 Khái niệm Ví dụ: Cho A = {1, 2, 3, 4}, R = {(a, b) | (a A, b A, a là ước của b} R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)} 1 2 3 4 1 2 3 4 2. Quan hệ BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2.1 Khái niệm Một quan hệ n-ngơi giữa các tập hợp A1, A2,..., An là tập con R của A1x A2x...xAn. Ví dụ: Xét quan hệ 4-ngơi cĩ tên là Sinh viên biểu diễn trong bảng sau: 2. Quan hệ Mã SV Họ tên Ngày sinh Khĩa học 99051110 Tran Anh 20-10-1990 1 99051111 Hoang Xuan 02-07-1990 1 99051112 Nguyen Viet 16-11-1990 1 ... BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: mij = 0 nếu (ai , bj)  R 1 nếu (ai , bj)  R Ví dụ: Nếu R là quan hệ từ A = {1, 2, 3} đến B = {1, 2} với a R b khi a > b. Ma trận biểu diễn của R là MR 2.2 Ma trận biểu diễn quan hệ Cho R là quan hệ từ A = {a1,a2,,am} đến B = {b1,b2,,bn}. Ma trận biểu diễn của R là ma trận cấp m × n MR = [mij] xác định bởi 19 2. Quan hệ            11 01 00 RM 1 2 1 2 3 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2.2 Ma trận biểu diễn quan hệ Ví dụ: Cho R là quan hệ từ A = {a1, a2, a3} đến B = {b1, b2, b3, b4, b5} R xác định gồm các cặp: {(a1, b2),(a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)}            10101 01101 00010 RM b1 b2 b3 b4 b5 a1 a2 a3 2. Quan hệ BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.1 Nguyên lý cộng Giả sử để thực hiện cơng việc A cĩ n-phương pháp - Phương pháp 1 cĩ m1 cách làm - Phương pháp 2 cĩ m2 cách làm - Phương pháp n cĩ mn cách làm Khi đĩ số cách chọn thực hiện cơng việc là m1 + m2 +...+mn 3. Bài tốn đếm BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.1 Nguyên lý cộng Ví dụ Cho tập hợp A={1,2,3}. Hỏi cĩ bao nhiêu cách chọn 1 tập con B của A. Giải: - t/hợp 1: chọn tập B là tập hợp rỗng- 1 cách chọn - t/hợp 2: chọn tập B chứa 1 phần tử của A - 3 cách chọn - t/hợp 3: chọn tập B chứa 2 phần tử của A - 3 cách chọn - t/hợp 4: chọn tập B chứa 3 phần tử của A - 1 cách chọn Áp dụng nguyên lý cộng, số cách chọn tính được là 8 cách. 3. Bài tốn đếm BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.2 Nguyên lý nhân Giả sử một cơng việc A cần được thực hiện qua n- bước liên tiếp. - bước 1 cĩ t1 cách làm - bước 2 cĩ t2 cách làm - bước n cĩ tn cách làm Khi đĩ số cách chọn thực hiện cơng việc là t1 x t2 x ... x tn 3. Bài tốn đếm BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.2 Nguyên lý nhân Ví dụ A B C Cĩ 3x2 =6 cách đi từ A đến C 3. Bài tốn đếm BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Ví dụ: Cho tập X ={1,2,3,4,5,0} Hỏi cĩ bao nhiêu số tự nhiên cĩ 3 chữ số khác nhau (lấy từ tập X) mà chia hết cho 2 Giải. Gọi số cĩ 3 chữ số là abc TH1: c=0. Khi đĩ c cĩ 1 cách chọn a cĩ 5 cách chọn ( aX\{0} ) b cĩ 4 cách chọn ( bX\{a, 0} ) TH1 cĩ 1x4x5 =20 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ĩ 2x4x4 =32 Tổng cộng cĩ 20+32 =52 (số cĩ 3 chữ số thỏa mãn bài tốn) 3. Bài tốn đếm BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.3 Nguyên lý bù trừ Với hai tập hợp A và B thì: |AB| = |A|+|B|-|AB| Ví dụ: Trong một cơ quan cĩ 180 người. Cĩ 55 người biết sử dụng MS-Word, 45 người biết sử dụng MS-Excel và 15 người vừa thạo MS-Word, vừa thạo MS-Excel. Hỏi cĩ bao nhiêu người khơng sử dụng được cả hai tiện ích? (95) 3. Bài tốn đếm A  B BA BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3.3 Nguyên lý bù trừ Với ba tập hợp A, B và C thì: |ABC| = |A|+|B|+|C|-|AB|-|BC|-|CA|+|ABC| 3. Bài tốn đếm A  B A  C BC A  B  C A B C BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.1 Hốn vị Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt cĩ thứ tự n phần tử của A được gọi là một hốn vị của n phần tử. - Số các hốn vị của n phần tử ký hiệu là Pn Pn = n! = 1.2.3... (n-1).n Quy ước 0! =1 Ví dụ Cho A ={a,b,c}. Khi đĩ A cĩ các hốn vị sau abc,acb, bac,bca, cab,cba 4. Giải tích tổ hợp BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.2 Chỉnh hợp Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử (1 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 ký hiệu là - Cơng thức   ! ! k n n A n k   k nA Ví dụ. Cho X ={abc}. Khi đĩ X cĩ các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb. 4. Giải tích tổ hợp BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.3 Tổ hợp Cho A là tập hợp gồm n phần tử. Mỗi tập con gồm k phần tử (1 k n) của A (khơng phân biệt thứ tự) được gọi là một tổ hợp chập k của n phần tử Số các tổ hợp chập k của n ký hiệu là - Cơng thức Ví dụ. Một lớp cĩ 30 học sinh. Hỏi cĩ bao nhiêu cách chọn 10 bạn? 4. Giải tích tổ hợp k nC   ! ! ! k n n C k n k   10 30C BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.4 Hốn vị lặp Cho n đối tượng trong đĩ cĩ ni đối tượng loại i giống hệt nhau (i =1,2,,k ; n1+ n2,+ nk= n). Mỗi cách sắp xếp cĩ thứ tự n đối tượng đã cho gọi là một hốn vị lặp của n. Số hốn vị của n đối tượng, trong đĩ cĩ n1 đối tượng giống nhau thuộc loại 1, n2 đối tượng giống nhau thuộc loại 2, ... nk đối tượng giống nhau thuộc loại k, là 4. Giải tích tổ hợp 1 2 ! ! !... !k n n n n BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.4 Hốn vị lặp 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? Giải. Trong từ SUCCESS cĩ 3 chữ S, 1 chữ U, 2 chữ C và 1 chữ E. Vậy tổng số chuỗi tạo được là 4. Giải tích tổ hợp 7 ! 420 3!1!2 !1!  BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.5 Tổ hợp và chỉnh hợp lặp a/. Một chỉnh hợp lặp chập k từ n phần tử là một bộ cĩ thứ tự gồm k phần tử lấy từ n phần tử đã cho, trong đĩ mỗi phần tử cĩ thể lấy lặp lại. Cách tính: b/. Một tổ hợp lặp chập k từ n phần tử là một bộ gồm k phần tử (khơng phân biệt thứ tự), mỗi phần tử cĩ thể lấy lặp lại từ n phần tử đã cho Cách tính: 4. Giải tích tổ hợp BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 4.5 Tổ hợp và chỉnh hợp lặp 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? Ta cĩ mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể là AA, AB, AC, BB, BC, CC Ví dụ Để đăng ký một loại hàng hĩa mới, người ta dùng 3 chữ số trong 9 chữ số từ 1 đến 9. Hỏi cĩ thể đánh số theo cách này được cho bao nhiêu loại hàng hĩa? Kết quả là: 93 = 729 4. Giải tích tổ hợp 2 2 2 3 3 2 1 4 6K C C    BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 5.1 Nguyên lý Dirichlet (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ì tồn tại ít nhất một ngăn cĩ nhiều hơn một con chim. 5. Bài tốn tồn tại 2 1 1 2 BÀI TỐN ĐẾM VÀ BÀI TỐN TỒN TẠI TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 5.2 Nguyên lý Dirichlet tổng quát Nếu xếp nhiều hơn n đố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 2 đối tượng. Tổng quát: Nếu xếp nhiều hơn n đối tượng vào k cái hộp, thì tồn tại ít nhất một hộp chứa khơng ít hơn [n/k] đối tượng. Kí hiệu [x] là số nguyên nhỏ nhất khơng nhỏ hơn x. 5. Bài tốn tồn tại 2 1 1 2