Tài liệu Một số kỹ năng giải bài toán đếm

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐỖ VĂN THUẬN MỘT SỐ KỸ NĂNG GIẢI BÀI TOÁN ĐẾM LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐỖ VĂN THUẬN MỘT SỐ KỸ NĂNG GIẢI BÀI TOÁN ĐẾM Chuyên ngành: Mã số: Phương pháp toán sơ cấp 60.46.01.13 LUẬN VĂN THẠC SĨ KHOA HỌC HƯỚNG DẪN KHOA HỌC: PGS.TS. NGUYỄN VŨ LƯƠNG Hà Nội - 2014 Mục lục 1 Một số kỹ năng giải bài toán đếm 1.1 Sử dụng các khái niệm cơ bản . . . . . 1.1.1 Quy tắc cộng, quy tắc nhân . . 1.1.2 Hoán vị . . . . . . . . . . . . . . 1.1.3 Chỉnh hợp . . . . . . . . . . . . 1.1.4 Tổ hợp . . . . . . . . . . . . . . 1.2 Phép tương ứng 1- 1 . . . . . . . . . . 1.2.1 Mô tả phần tử đếm . . . . . . . 1.2.2 Mã hóa 0, 1 phần tử đếm . . . 1.2.3 Phương pháp đánh số . . . . . 1.3 Một số phương pháp giải nâng cao của 1.3.1 Nguyên lí bao gồm và loại trừ . 1.3.2 Phương pháp truy hồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . bài toán đếm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3 3 6 10 13 17 17 19 24 26 26 30 2 Một số dạng bài toán tổ hợp liên quan đến bài toán đếm 34 2.1 Nguyên lí bất biến . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.1.1 Phát hiện đại lượng bất biến trong bài toán . . . . . . . 34 2.1.2 Giải toán bằng đại lượng bất biến . . . . . . . . . . . . . 39 2.1.3 Bất biến đơn điệu . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.4 Một số bài toán nâng cao . . . . . . . . . . . . . . . . . . 44 2.2 Phân hoạch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.2.1 Chứng minh không tồn tại phân hoạch thỏa mãn tính chất (G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.2.2 Chứng minh có tồn tại phân hoạch thỏa mãn tính chất (G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.2.3 Xây dựng phân hoạch tính chất (G) . . . . . . . . . . . . 49 2.2.4 Phân hoạch cân bằng . . . . . . . . . . . . . . . . . . . . . 52 2.2.5 Một số bài toán minh họa . . . . . . . . . . . . . . . . . . 53 2.3 Nguyên lí Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . 55 TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . 57 1 Lời mở đầu Trong các dạng bài toán tổ hợp thì bài toán đếm và một số dạng toán tổ hợp liên quan đến bài toán đếm là các dạng bài cơ bản và rất quan trọng. Những dạng toán này xuất hiện rất nhiều trong các kì thì vào các trường chuyên, thi học sinh giỏi quốc gia, quốc tế. Việc giải các bài toán dạng này nhiều khi gặp rất nhiều khó khăn và rất dễ mắc phải những sai lầm vì đây là những dạng toán khó và chúng ta không nắm được các phương pháp, các kỹ năng giải. Liên quan đến bài toán đếm có hai vấn đề được quan tâm nghiên cứu. - Một số kỹ năng giải các bài toán đếm; - Một số dạng bài toán tổ hợp liên quan đến bài toán đếm. Để giải được nhanh chóng và chính xác các bài toán đếm chúng ta cần phải nắm được các kỹ năng giải và việc giải thành thạo các bài toán đếm giúp ta rất nhiều trong việc giải các bài toán tổ hợp liên quan đến bài toán đếm. Hiện nay có nhiều sách tham khảo, tài liệu viết về các dạng toán tổ hợp nhưng một số kỹ năng giải bài toán đếm và đặc biệt là một số dạng bài toán tổ hợp liên quan đến bài toán đếm như nguyên lí bất biến, phân hoạch thì chưa được đề cập nhiều. Chính vì vậy, chúng tôi xin chọn đề tài cho luận văn của mình là: “Một số kỹ năng giải bài toán đếm”. Trong luận văn này ngoài việc trình bày một số kỹ năng giải bài toán đếm, chúng tôi còn đưa ra một số dạng toán tổ hợp liên quan đến bài toán đếm. Nội dung luận văn này gồm hai chương: - Chương 1: Trình bày một số kỹ năng giải bài toán đếm như sử dụng các khái niện cơ bản, phép tương ứng 1- 1 và một số phương pháp giải nâng cao. - Chương 2: Đưa ra một số dạng bài toán tổ hợp liên quan đến bài toán đếm như nguyên lí bất biến, phân hoạch và nguyên lí Dirichlet kèm theo các bài tập và lời giải chi tiết. Các kết quả chính của luận văn nằm trong mục 1.2 của chương 1 và mục 2.2 của chương 2. Tôi xin được gửi lời cảm ơn sâu sắc và lòng biết ơn chân thành tới PGS. TS Nguyễn Vũ Lương. Cảm ơn thầy đã hướng dẫn, chỉ bảo và giúp đỡ tận tình trong suốt quá trình tôi thực hiện luận văn này. Tôi cũng xin gửi lời cảm ơn tới các thầy, cô giáo của trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội đã hết lòng đào tạo, dạy dỗ giúp đỡ tôi trong suốt thời gian tôi học tập tại trường. Mặc dù vây, do năng lực cá nhân còn hạn chế cũng như thời gian hạn hẹp luận văn không tránh khỏi những thiếu sót cả về mặt nội dung và hình thức, rất mong sự đóng góp ý kiến của các thầy cô và các bạn. 2 Chương 1 Một số kỹ năng giải bài toán đếm Bài toán đếm là một nội dung cơ bản không chỉ dành cho các bài toán thi đại học mà còn rất cần thiết khi giải các bài toán tổ hợp khó trong các kỳ thi học sinh giỏi. Một đặc điểm rất đặc thù của nội dung này là khi giải toán, học sinh thường nhận được các đáp số khác nhau vì những sai sót mà bản thân không nhận ra. Chính vì vậy xây dựng các kỹ năng giải là thực sự cần thiết và nội dung của phần này là trình bày các kỹ năng này. 1.1 1.1.1 Sử dụng các khái niệm cơ bản Quy tắc cộng, quy tắc nhân Quy tắc cộng. Nội dung quy tắc: Nếu có m1 cách chọn đối tượng a1 , m2 cách chọn đối tượng a2 , ..., mn cách chọn đối tượng an , trong đó cách chọn đối tượng ai (1 ≤ i ≤ n) không phụ thuộc vào bất kì cách chọn đối tượng aj n P (1 ≤ i ≤ n, i 6= j ) thì sẽ có mk cách chọn đối tượng a1 , hoặc a2 , ..., k=1 hoặc an . Quy tắc nhân. Nội dung quy tắc: Cho n đối tượng a1 , a2 , ..., an . Nếu có m1 cách chọn đối tượng a1 và với mỗi cách chọn a1 có m2 cách chọn đối tượng a2 , sau đó với mỗi cách chọn a1 , a2 có m3 cách chọn đối tượng a3 ,... Cuối cùng với mỗi cách chọn a1 , a2 , a3 , ..., an−1 có mn cách chọn đối tượng an . Như vậy sẽ có m1 .m2 ...mn−1 .mn cách chọn các đối tượng a1 , rồi a2 , rồi a3 ... rồi an . Sau đây ta xét một số bài toán minh họa: 3 Bài 1.Với sáu chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm bốn chữ số khác nhau và trong mỗi số nhất thiết phải có chữ số 1. Bài giải Gọi số cần lập là abcd. Xét các trường hợp: Trường hợp 1: a = 1 có 1 cách chọn a, có A35 cách chọn các chữ số b, c, d. Trường hợp 2: a 6= 1. Có 4 cách chọn a ( vì a 6= 0). - Nếu b = 1 thì có 1 cách chọn b và có A24 cách chọn c, d; - Nếu c = 1 thì có 1 cách chọn c và có A24 cách chọn b, d; - Nếu d = 1 thì có 1 cách chọn d và có A24 cách chọn b, c; Vậy theo quy tắc cộng có thể lập được 1.A35 + 4.A24 + 4.A24 + 4.A24 = 204 (số). Bài 2. Từ thành phố A đến thành phố B có 3 con đường, từ thành phố A đến thành phố C có 2 con đường, từ thành phố B đến thành phố D có 2 con đường, từ thành phố C đến thành phố D có 4 con đường. Không có con đường nào nối thành phố B với thành phố C. Hỏi có tất cả bao nhiêu con đường nối từ thành phố A đến thành phố D. Bài giải Trường hợp 1: Đi từ A đến B rồi đến D. Có 3 cách đi từ A đến B và có 2 cách đi từ B đến D. Theo quy tắc nhân thì số cách chọn đường đi từ A đến D qua B là 3.2 = 6; Trường hợp 2: Đi từ A đến C rồi đến D. Có 2 cách đi từ A đến C và có 4 cách đi từ C đến D. Theo quy tắc nhân thì số cách chọn đường đi từ A đến D qua C là 2.4 = 8. Vì cách chọn đường từ A sang D qua B và cách chọn đường từ A sang D qua C không phụ thuộc lẫn nhau, nên theo quy tắc cộng, ta có số con đường để đi từ A sang D là 6 + 8 = 14 (cách). Bài 3. Từ các chữ số 1, 2, 3, 4, 5, 6, 7, 8, 9 có thể lập được bao nhiêu số gồm 4 chữ số khác nhau? Tìm tổng của tất cả các số này. Bài giải Gọi số cần lập có dạng abcd. Có 9 cách chọn a; Có 8 cách chọn b (b 6= a); Có 7 cách chọn c (c 6= a, c 6= b); Có 6 cách chọn d (d 6= a, d 6= b, d 6= c). Vậy theo quy tắc nhân thì số các số có thể lập được là 9.8.7.6 = 3024 (số). Số lớn nhất, số nhỏ nhất trong các số dạng này lần lượt là 9876 và 1234 có tổng bằng 11110, nên đối với số bất kì abcd đều tồn tại số a0 b0 c0 d0 , mà 4 abcd + a0 b0 c0 d0 = 11110 Khi đó, ta có đẳng thức: (a+a0 ).1000+(b+b0 ).100+(c+c0 ).10+d+d0 = 10.1000+10.100+10.10+1.10 Từ đó, ta có các đẳng thức a + a0 = b + b0 = c + c0 = d + d0 = 10 a 6= a0 ⇔ b 6= b0 ⇔ c 6= c0 ⇔ d 6= d0 Bởi vậy, nếu abcd có các chữ số không trùng nhau thì a0 b0 c0 d0 cũng có các 1 chữ số không trùng nhau. Do đó có .9.8.7.6 cặp số abcd, a0 b0 c0 d0 gồm 4 2 chữ số không trùng nhau thuộc tập {1, 2, 3, 4, 5, 6, 7, 8, 9} Vậy tổng tất cả các số dạng trên là : 1 .9.8.7.6.11110 = 16798320 2 Bài 4. Một con ngựa trên bàn cờ vua 8x8. Hỏi có bao cách di chuyển con ngựa trên bàn cờ. Bài giải Các ô của bàn cờ có thể đặt theo quy tắc aij (i=1..8 ,j=1..8) a11 có 2 cách di chuyển. a12 có 3 cách di chuyển. a13 , a14 , a22 có 4 cách di chuyển. a23 , a24 có 6 cách di chuyển. a33 , a34 , a44 có 8 cách di chuyển. Lấy đối xứng các vị trí trên qua 4 trục đối xứng của bàn cờ, ta có tổng số cách là: n = 4.2 + 8.3 + 20.4 + 16.6 + 16.8 = 336. Bài 5. Cho bàn cờ vua 8x8. Có bao nhiêu cách chọn ra 1 ô trắng và 1 ô đen? Có bao cách chọn 1 ô trắng, 1 ô đen cùng nằm trên 1 hàng hay 1 cột? Bài giải Trên bàn cờ có 32 ô trắng, 32 ô đen. Có 32 cách chọn ra một ô đen, 32 cách chọn một ô trắng. Vậy số cách chọn n1 =32.32=1024 (cách). Có 32 cách chọn một ô trắng. Số ô đen cùng hàng, cùng cột với ô trắng đã chọn ra là 8. Vậy số cách chọn n2 =32.8=256 (cách). 5 Bài 6 Có 28 quân domino ở 2 đầu có x,y chấm 0 ≤ x, y ≤ 6. Có bao nhiêu cách chọn ra 2 quân domino có thể nối với nhau (số chấm ở một đầu của quân này bằng số chấm ở một đầu quân khác). Bài giải Lấy một quân domino bất kỳ nó thuộc một trong 2 loại: Loại 1 (7 quân): (0,0), (1,1),...,(6,6). Loại 2 (21 quân): có số chấm 2 đầu khác nhau. - Nếu quân domino chọn ra là loại 1 (sẽ có 7 cách chon) sẽ được nối với 6 quân khác. Ví dụ như (1,1) sẽ được nối với (1,0), (1,2), (1,3),(1,4),(1,5),(1,6). Vậy số cặp nối được trong trường hợp này là: n1 = 7.6 = 42. - Nếu quân domino chọn ra là loại 2 (sẽ có 21 cách chọn), sẽ được nối với 12 quân khác. Ví dụ (2,3) sẽ được nối với (2,0), (2,1), (2,4), (2,2), (2,5), (2,6),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6). Vậy số cặp nối đươc trong trường hợp này là n2 = 21.12 = 252.. Theo quy tắc cộng thì số cách nối đươc là 252+42=294 (kể cả thứ tự). Vì thứ tự giữa 2 đầu của quân domini được xác định, và mỗi cặp 2 quân 294 domino nối được đến 2 lần, ta suy ra số cặp nối được là n = = 147. 2 1.1.2 Hoán vị Hoán vị không lặp Định nghĩa: Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó (mỗi phần tử có mặt đúng một lần) được gọi là một hoán vị của n phần tử đã cho. Kí hiệu số hoán vị của n phần tử bằng Pn Ta có công thức Pn = n! Sau đây ta xét một số bài oán minh họa: Bài 7.Với năm chữ số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm năm chữ số khác nhau? Bài giải Mỗi số cần lập là một hoán vị của năm chữ số đã cho. Vậy số các số lập được bằng số hoán vị của năm phần tử bằng P5 = 5! = 120 6 Bài 8. Trong một hội nghị có 5 báo cáo viên A, B, C, D, E mỗi người báo cáo một lần? 1. Có bao nhiêu cách xếp thứ tự cho báo cáo viên. 2. Có bao nhiêu cách xếp thứ tự cho báo cáo viên nếu yêu cầu báo cáo viên B báo cáo ngay sau báo cáo viên A? 3. Có bao nhiêu cách xếp thứ tự cho báo cáo viên nếu B không báo cáo trước A? Bài giải 1. Số cách xếp thứ tự cho báo cáo viên bằng 5! = 120 2. B báo cáo ngay sau A ta thay thế bằng một cặp báo cáo viên X= AB. Khi đó, xem X như là một báo cáo viên. Vậy số cách là n2 = 4! = 24. 3. Trong mọi cách sắp xếp khả năng A đứng trước B hay đứng sau B là như nhau. 1 Vậy số cách sắp xếp B không báo cáo trước A là .5! = 60. 2 Bài 9 Có bao nhiêu cách xếp 5 người đàn ông, 5 người đàn bà xung quanh một bàn tròn 10 ghế sao cho không có 2 người đàn ông hoặc 2 người đàn bà nào ngồi cạnh nhau. Bài giải Lấy 1 ghế bất kỳ. Nếu xếp 1 người đàn ông thì ghế tiếp theo là của đàn bà..... Số cách xếp 5 đàn ông vào vị trí có sẵn là 5!, số cách xếp 5 đàn bàn vào vị trí là 5!. Số cách xếp theo vị trí này là 5!5!. Nếu xếp 1 người đàn bà thì số cách xếp tương tự bằng 5!5!. Đáp số:: 2.(5!)2 . Hoán vị có lặp Định nghĩa: Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị có lặp. Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i (1 ≤ i ≤ k ) xuất hiện ni lần được kí hiệu là P (n1 , n2 , ..., nk ) và được tính bằng công thức P (n1 , n2 , ..., nk ) = n! . n1 !.n2 !...nk ! Sau đây ta xét một số bài toán minh họa: Bài 10. Với các chữ số 1, 2, 3, 4, 5, 6 có thể lập được bao nhiêu số gồm chín chữ số, trong đó mỗi chữ số 1, 2, 3, 4 xuất hiện đúng một lần, chữ số 5 xuất hiện đúng hai lần và chữ số 6 xuất hiện đúng ba lần. 7 Bài giải Xét một số tùy ý x = 154626356 và kí hiệu các vị trí của x một cách hình thức, ta có x = a1 a2 a3 a4 a5 a6 a7 a8 a9 . Khi đó, mỗi số x tương ứng với một hoán vị lặp của chín phần tử a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9 . Số các hoán vị khác nhau của chín phần tử ai (1 ≤ i ≤ 9) là 9! song do a2 = a8 = 5 nên khi đổi chỗ a2 và a8 cho nhau thì hoán vị x = a1 a2 a3 a4 a5 a6 a7 a8 a9 vẫn chỉ cho ta số x. Tương tụ đổi chỗ hai trong ba phần tử a4 , a6 , a9 cho nhau vẫn chỉ cho số x. Như vậy, khi thực hiện 2! hoán vị a2 , a8 và 3! hoán vị a4 , a6 , a9 , ta chỉ được một số cần tìm x. Vậy số các số có thể lập được là 9! = 30240 S= 2!3! Bài 11. Với sáu chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số chia hết cho 5 gồm 11 chữ số, trong đó chữ số 1 có mặt 4 lần, chữ số 2 có mặt 3 lần, chữ số 3 có mặt 2 lần chữ số 4 có mặt 1 lần và tổng số lần xuất hiện của chữ số 0 và chữ số 5 là 1. Bài giải Để số cần lập x = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 chia hết cho 5, thì x phải tận cùng bằng chữ số 0 hoặc chữ số 5. Vì tổng số lần xuất hiện trong x của 0 và 5 bằng 1 nên nếu x tận cùng bằng 0 thì 5 không có mặt và ngược lại nếu x tận cùng bằng 5 thì chữ số 0 không xuất hiện. Bởi vậy ai (1 ≤ i ≤ 10) chỉ có thể là một trong những chữ số 1, 2, 3, 4. Bởi vậy số khả năng lập phần đầu độ dài 10 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 của x bằng số hoán vị lặp của 10 phần tử thuộc 4 loại chữ số: 1, 2, 3, 4 với 1 xuất hiện 4 lần, 2 xuất hiện 3 lần, 3 xuất hiện 2 lần và 4 xuất hiện 1 lần sẽ bằng P (1, 2, 3, 4) . Ngoài ra a11 lại có thể nhận 0 hoặc 5 nên có thể lập được 10! = 25200 2.P (1, 2, 3, 4) = 2. 1!2!3!4! Bài 12. Có bao nhiêu cách đảo từ PARABOLA sao cho các phụ âm và nguyên ân được xếp xen kẽ. Bài giải Vì có 4 phụ âm và 4 nguyên âm nên ta xếp 4 phụ âm (có 4! cách xếp) và 4! xếp vào 4 vị trí xem kẽ 4 nguyên âm là . 3! Vị trí ban đầu có thể là phụ âm hoặc nguyên âm đối với mỗi hoán vị 4! của phụ âm. Suy ra số cách xếp: n = 2.4!. = 192. 3! 8 Bài 13. Tìm số cách đảo từ ROKOKO sao cho 3 chữ O không đứng liền nhau. Bài giải Tất cả các cách đảo từ bằng n1 = 6! 6.5.4 = = 60. 3!2! 2 Số cách đảo từ mà 3 chữ O đứng cạnh nhau (coi như là một chữ) bằng 4! n2 = = 4.3 = 12. 2! Đáp số: n = n1 − n2 = 48 Ta xét một ví dụ đơn giản sau: Xét tập A = {a, b}, ta lập tập B = {a, a, b, b, b}. Khi đó B = (A, α) ,α(a) = 2, a xuất hiện 2 lần, α(b) = 3 gọi là tập bội số lần xuất hiện α. Khi đó, số cách xếp thành một hàng ngang của B bằng: P (2, 5) = 5! . 2!3! Mở rộng, xét tập A = {x1 , x2 , ..., xn } gồm n phần tử riêng biệt. Xét tập bội B trong đó xi xuất hiện α(xi ) = αi lần. Khi đó, số cách xếp thành một hàng ngang của B bằng P (α1 , α2 , ..., αn ) = (α1 + α2 + ... + αn )! α1 !.α2 !...αn ! Hoán vị vòng quanh Ví dụ dẫn dắt. Mời sáu người khách ngồi xung quanh một bàn tròn. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi. Bài giải Nếu ta mời một người nào đó ngồi vào một vị trí bất kì, thì số cách sắp xếp 5 người còn lại vào 5 vị trí giành cho họ sẽ là 5! = 120. Vậy có tất cả 120 cách sắp xếp 6 người ngồi xung quanh một bàn tròn. Số hoán vị vòng quanh của n phần tử khác nhau (Qn ) được tính bằng công thức Qn = (n − 1)! Sau đây ta xét một số bài toán minh họa 9 Bài 14. Một hội nghị bàn tròn có năm nước tham gia. Anh có 3 đại biểu, Pháp có 5 đại biểu, Đức có 2 đại biểu, Nhật có 3 đại biểu, Mỹ có 4 đại biểu. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho mọi đại biểu sao cho hai người cùng quốc tịch đều ngồi cạnh nhau. Bài giải Đầu tiên ta sắp xếp khu vực cho đại biểu từng nước. Ta mời phái đoàn nào đó ngồi vào chỗ trước. Khi đó, bốn phái đoàn còn lại có 4! cách sắp xếp. Đối với mỗi cách sắp xếp các phái đoàn lại có: 3! cách sắp xếp đại biểu trong nội bộ phái đoàn Anh; 5! cách sắp xếp đại biểu trong nội bộ phái đoàn Pháp; 2! cách sắp xếp đại biểu trong nội bộ phái đoàn Đức; 3! cách sắp xếp đại biểu trong nội bộ phái đoàn Nhật; 4! cách sắp xếp đại biểu trong nội bộ phái đoàn Mỹ. Bởi vậy, số cách sắp xếp chỗ ngồi cho tất cả các đại biểu để những người cùng quốc tịch ngồi cạnh nhau sẽ bằng 4!3!5!2!3!4! = 4976640 Bài 15. Có bao nhiêu cách sắp xếp 5 nam A1 , A2 , A3 , A4 , A5 và 3 nữ B1 , B2 , B3 vào một bàn tròn sao cho: a) Không có điều kiện gì?; b) Nam A1 không ngồi cạnh nữ B1 ? c) Nữ không ngồi cạnh nhau? Bài giải a) Mỗi cách sắp xếp bất kì là một hoán vị vòng quanh của 8 phần tử, nên số cách sắp xếp bằng số hoán vị vòng quanh của 8 phần tử, bằng Q8 = 7! = 5040. b) Năm nam và hai nữ không kể B1 có (7 − 1)! = 6! cách sắp xếp. Ứng với một trong những phương án sắp xếp năm nam và hai nữ không kể B1 , khi đó B1 có thể xếp vào giữa A2 , B2 , giữa B2 , A4 , giữa A4 , B3 , giữa A5 , B3 , giữa A3 , A5 . Như vậy có 7 − 2 = 5 cách sắp xếp B1 Vậy có 6!.5 = 720 cách sắp xếp. c) Trước hết ta xếp 5 nam ngồi xung quanh bàn tròn. Số cách sắp xếp này bằng số hoán vị vòng quanh của 5 phần tử, bằng (5 − 1)! = 4! = 24. Có 5 cách sắp xếp nữ B1 , 4 cách sắp xếp nữ B2 và 3 cách sắp xếp nữ B3 . Vậy số cách sắp xếp cần tìm là 4!.5.4.3 = 1440. 1.1.3 Chỉnh hợp Chỉnh hợp không lặp 10 Định nghĩa: Cho tâp hợp A hữu hạn gồm n phần tử. Mỗi bộ gồm k (0 ≤ k ≤ n) phần tử được 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ử thuộc A. Ta ký hiệu số chỉnh hợp chập k của n phần tử bằng Akn . Số chỉnh hợp chập k của n phần tử được tính bởi công thức Akn = n(n − 1)...(n − k + 1) = n! . (n − k)! Chứng minh Để có một hoán vị chập k ta làm như sau: Có n cách lấy ra phần tử thứ 1. Có n-1 cách lấy ra phần tử thứ 2.. ... Có n-k+1 cách chọn ra phần tử thứ k Theo quy tắc nhân, số hoán vị của k phần tử bằng n(n-1)...(n-k+1) (đpcm). Sau đây ta xét một số bài toán minh họa: Bài 16. Từ các chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số tự nhiên mà trong mỗi số này các chữ số khác nhau? Bài giải Ta xét các trường hợp sau: Trường hợp 1: Lập số có 1 chữ số có 6 số; Trường hợp 2: Lập số có 2 chữ số có 5.5 = 25 số; Trường hợp 3: Lập số có 3 chữ số có 5.A25 = 100 số; Trường hợp 4: Lập số có 4 chữ số có 5.A35 = 300 số; Trường hợp 5: Lập số có 5 chữ số có 5.A45 = 600 số; Trường hợp 6: Lập số có 6 chữ số có 5.A55 = 600 số; Vậy số các số tự nhiên có thể lập là 6 + 25 + 100 + 300 + 600 + 600 = 1631 Bài 17. Một cuộc khiêu vũ có 10 nam và 6 nữ tham gia. Đạo diễn chọn có thứ tự 4 nam và 4 nữ để ghép thành 4 cặp. Hỏi có bao nhiêu cách chọn? Bài giải Mỗi cách chọn có thứ tự 4 nam trong 10 nam là một chỉnh hợp chập 4 10! của 10. Số chỉnh hợp này là A410 = = 5040. Vậy có 5040 cách (10 − 4)! chọn 4 nam. Mỗi cách chọn có thứ tự 4 nũ trong 6 nũ là một chỉnh hợp chập 4 của 6! 6. Số chỉnh hợp này là A46 = = 360. Vậy có 360 cách chọn 4 nữ. (6 − 4)! 11 Mỗi cách chọn nam lại tương ứng với tất cả các cách chọn nữ, nên số cách chọn có thứ tự 4 nam, 4 nữ trong số nam, nữ tham gia hội diễn sẽ là 5040.360 = 1814400 cách chọn. Bài 18. Có 7 thành viên ứng cử vào hội đồng trường. Hỏi có bao nhiêu cách chọn ra một chủ tịch, một phó chủ tịch, một thư ký, một thủ quỹ trong số họ. Bài giải Có 7 cách chọn 1 người làm chủ tịch. Có 6 cách chọn 1 người làm phó chủ tịch trong số còn lại. Có 5 cách chọn 1 người làm thư ký. Có 4 cách chọn 1 người làm thủ quỹ. Theo quy tắc nhân, số cách chọn bằng n=7.6.5.4=840. Bài 19 Chọ tập A={0, 1, 2, 3, 4, 5}.Hỏi có bao nhiêu số gồm 4 chữ số phân biệt lập được từ các chữ số của A. Hỏi có bao nhiêu số chẵn gồm 4 chữ số phân biệt lập được từ các chữ số của A. Bài giải Đáp số n1 = 5.A35 = 300. Ta chia tất cả các số chẵn thành 2 loại: Loại 1: Số 0 đứng cuối cùng. Loại 2: Số 2 hoặc số 4 đứng cuối cùng. Số các số gồm 4 chữ số phân biệt mà số 0 đứng cuối bằng |S1 | = A35 =60. Số các số mà số 2 hoặc 4 đứng cuối cùng (theo quy tắc nhân) bằng |S2 | = 4.4.3.2 = 96. Đáp số n2 = |S1 | + |S2 | = 60 + 96 = 156. Bài 20. Cho tập A = {0, 1, 2, 3, 4, 5} có bao nhiêu số gồm 4 chữ số phân biệt của A chia hết cho 5. Bài giải - Xét các số mà chữ số 0 đứng cuối cùng. Trong trường hợp này số các số thỏa mãn yêu cầu của bài toán bằng n1 = A35 = 60. - Xét các số có số 5 đứng cuối cùng, ta cần chọn thêm 3 chữ số phân biệt (số có 3 chữ số phân biệt) xếp phía trên số 5. Có 5.4.3 bộ 3 số phân biệt. Có 4.3 số phân biệt mà số 0 đứng đầu. Suy ra số các số thỏa mãn yêu cầu của bài toán trong trường hợp này bằng n2 = 5.4.3 − 4.3 = 48. Đáp số n = n1 + n2 = 60 + 48 = 108. 12 Chỉnh hợp có lặp Định nghĩa. Cho tập hữu hạn X gồm n phần tử. Mỗi dãy có độ dài k các phần tử của tập X, mà mỗi phần tử có thể lặp lại nhiều lần và được sắp xếp theo một thứ tự nhất định được gọi là một chỉnh hợp lặp chập k của n phần tử thuộc tập X. Số chỉnh hợp lặp chập k của n phần tử kí hiệu là Akn bằng số ánh xạ từ tập k phần tử đến tập n phần tử và bằng nk , tức Akn = nk Sau đây ta xét một số bài toán minh họa: Bài 21.Từ bốn chữ số 1, 2, 3, 5 có thể lập được bao nhiêu số chẵn gồm 4 chữ số? Bài giải Gọi số cần lập có dạng x = abcd. Vì x là số chẵn nên d = 2 Mỗi cách chọn bộ ba chữ số a, b, c là một chỉnh hợp lặp chập 3 của 4 phần tử 1, 2, 3, 5. Vậy số các số chẵn có thể lập được bằng A34 = 43 = 64. Bài 22.Có thể lập được bao nhiêu biển số xe với hai chữ cái đầu thuộc tập {A, B, C, D, E}, tiếp theo là một số nguyên dương gồm năm chữ số chia hết cho 5? Bài giải Giả sử biển số xe cần lập có dạng XY abcde. Vì X, Y có thể trùng nhau nên XY là chỉnh hợp lặp chập 2 của 5 phần tử A, B, C, D, E, nên số cách chọn XY bằng A25 = 52 = 25 Do a 6= 0 nên có 9 cách chọn a Vì abcde chia hết cho 5 nên e = 0 hoặc e = 5. Vậy có 2 cách chọn chữ số e. Do b, c, d có thể trùng nhau nên mỗi bộ b, c, d là một chỉnh hợp lặp chập 3 của 10. Vậy số cách chọn bộ b, c, d bằng A310 = 103 = 1000 Vậy số biển số xe có thể lập được theo yêu cầu là:25.2.1000 = 50000. 1.1.4 Tổ hợp Tổ hợp không lặp Định nghĩa. Cho tập A gồm n phần tử. Mỗi tập con gồm k (0 ≤ k ≤ n) phần tử thuộc A được gọi là tổ hợp chập k của n phần tử đã cho. 13 Hai tổ hợp được coi là khác nhau khi và chỉ khi có ít nhất một phần tử khác nhau. Số tổ hợp chập k (0 ≤ k ≤ n) của n phần tử được kí hiệu là Cnk và được tính theo công thức Cnk = n(n − 1)(n − k + 1) n! = k! k!(n − k)! Sau đây ta xét một số bài toán minh họa: Bài 23. Có bao nhiêu cách chia một lớp 40 học sinh thành 4 tổ, sao cho mỗi tổ có đúng 10 học sinh. Bài giải Đầu tiên lập tổ 1 bằng cách chọn tùy ý 10 học sinh trong 40 học sinh của lớp. Số cách chọn bằng số các tổ hợp chập 10 của 40, bằng 10 C40 = 40! 10!30! Tổ 2 có thể chọn 10 em tùy ý trong 30 em còn lại, số cách chọn bằng số các tổ hợp chập 10 của 30, bằng 10 C30 = 30! 10!20! Tổ 3 có thể chọn 10 em tùy ý trong 20 em còn lại, số cách chọn bằng số các tổ hợp chập 10 của 20, bằng 10 C20 = 20! 10!10! Tổ 4 gồm 10 em còn lại nên chỉ có 1 cách chọn. Vậy số cách chia sẽ là 10 10 10 10 C40 .C30 .C20 .C10 = 40!.30!.20! 40! = 10!30!20!10!10!10! (10!)4 Bài 24. Một lớp học sinh có 40 em gồm 25 nam và 15 nữ. Giáo viên chủ nhiệm định chọn một ban cán sự gồm 4 người. Hỏi có bao nhiêu cách chọn nếu: a) Số nam hoặc nữ trong ban là tùy ý? b) Ban cán sự có 1 nam và 3 nữ ? c) Ban cán sự có 2 nam và 2 nữ? d) Ban cán sự có ít nhất 1 nam? e) Ban cán sự có ít nhất 1 nam và một nữ? 14 Bài giải a) Nếu số nam (nữ) là tùy ý, thì số cách chọn là số các tổ hợp chập 4 của 40 phần tử, bằng 4 C40 = 40! = 91390 (cách) 4!36! b) Nếu trong ban cán sự có 1 nam và 3 nữ, thì số cách chọn 1 nam trong 1 3 25 nam là C25 còn số cách chọn 3 nữ trong số 15 nữ là C15 . Vậy số cách chọn theo yêu cầu là 3 1 = .C15 C25 25! 15! . = 11375 (cách) 1!24! 3!12! c) Tương tự như trên, số cách chọn 2 nam và 2 nữ là 2 2 = .C15 C25 25! 15! . = 31500 (cách) 2!23! 2!13! d) Nếu trong ban cán sự có ít nhất 1 nam thì có 4 khả năng xảy ra: 1 3 1 nam và 3 nữ có C25 .C15 cách chọn; 2 2 2 nam và 2 nữ có C25 .C15 cách chọn; 1 3 cách chọn; .C15 3 nam và 1 nữ có C25 4 4 nam và không nữ có C25 cách chọn; 4 1 3 2 2 3 1 = 469575 (cách chọn). + C25 .C15 + C25 .C15 + C25 .C15 Vậy có C25 4 4 ) cách chọn. Vậy số (C15 e) Nếu ban cán sự gồm toàn nam (nữ) có C25 cách chọn để ban cán sự có ít nhất 1 nam và ít nhất 1 nữ là 10 4 4 C40 − (C15 + C25 ) = 77375 (cách) Bài 25. Cho 6 điểm trên mặt phẳng sao cho không có 3 điểm nào thẳng hàng. Hỏi có bao nhiêu đường thẳng đi qua 2 điểm trong 6 điểm này. Bài giải Theo giả thiết, từ một cặp 2 điểm xác định duy nhất một đường thẳng. Vậy số đường thẳng bằng số cặp 2 điểm từ 6 điểm: n = C62 = 15. Bài 26. Từ 7 học sinh nam, 4 học sinh nữ. Hỏi có bao nhiêu cách chọn một đội bóng chuyền cho 6 em sao cho trong đội có ít nhất 2 nữ. Bài giải Ký hiệu S2 là tập các đội bóng có 2 nữ, S3 là tập các đội bóng có 3 nữ, S4 là các đội bóng có 4 nữ. Có C42 cách chọn 2 nữ, C74 cách chọn 4 nam. Suy ra, |S2 | = C42 .C74 . Tương tự ta có :|S3 | = C43 .C73 , |S4 | = C44 .C72 15 Vậy số cách chọn bằng n = |S2 | + |S3 | + |S4 | = 6.35 + 4.35 + 1.21 = 371 Bài 27. Có 12 nam, 15 nữ. Hỏi có bao nhiêu cách chọn ra 4 cặp nhảy (mỗi cặp 1 nam, một nữ). Bài giải Mỗi cách chọn tương ứng với cách chọn ra 4 em nam xếp thành một hàng, 4 em nữ xếp thành một hàng. (Khi đó 2 em đứng thẳng hàng tạo thành một cặp nhảy). Vậy số cách chọn bằng 4 4 .4!. .C15 n = C12 Chú ý: Lấy 1 em nam (trong 4 em) có 4 cách chọn 1 em nữ. Lấy 1 em nam trong 3 em còn lại có 3 cách chọn 1 em nữ trong 3 nữ còn lại. Lấy 1 em nam trong 2 em còn lại có 2 cách chọn 1 em nữ. Vậy số cách xếp cặp cho 4 nam, 4 nữ bằng 4! Tổ hợp lặp Định nghĩa. Cho tập hợp A = {a1 , a2 , ..., an }. Một tổ hợp lặp chập m (m không nhất thiết phải nhỏ hơn n) của n phần tử thuộc A là một bộ gồm m phần tử mà mỗi phần tử này là một trong những phần tử của A. Ta sử dụng Cnm để kí hiệu số tổ hợp lặp chập m của n phần tử. Khi đó m Cnm = Cm+n−1 Sau đây ta xét một số bài toán minh họa: Bài 28. Giả sử có 4 loại bóng màu: Xanh, Đỏ, Tím, Vàng với số lượng mỗi loại không hạn chế. Hai bộ bóng được xem là khác nhau nếu có ít nhất một màu với số lượng thuộc hai bộ khác nhau. Hỏi có bao nhiêu cách chọn ra các bộ 6 (quả bóng) khác nhau? Bài giải Vì trong mỗi bộ sáu quả bóng có thể có các quả bóng cùng màu và không phân biệt thứ tự chọn, nên số cách chọn khác nhau bằng số tổ hợp lặp chập 6 của 4 phần tử (tập hợp bóng cùng màu được coi là một phần tử) và được tính bằng công thức 9! = 84 6!3! Bài 29.Tiền giấy của Ngân hàng quốc gia Việt nam ban hành phổ biến trên thị trường có 10 loại 200đ, 500đ, 1000đ, 2000đ, 5000đ, 10000đ, 20000đ, 50000đ, 100000đ, 500000đ. Hãy xác định số bộ khác nhau gồm 15 tờ giấy bạc của Ngân hàng quốc gia Việt Nam. Bài giải 6 = C46 = C4+6−1 16 Mỗi bộ gồm 15 tờ giấy bạc thuộc không quá 10 loại, nên có những tờ giấy bạc cùng loại. Mặt khác trong mỗi bộ không quan tâm đến thứ tự sắp xếp, nên số bộ giấy bạc khác nhau gồm 15 tờ sẽ bằng số tổ hợp lặp chập 15 của 10 (loại), bằng 15 15 = C 15 C10 10+15−1 = C24 = 1.2 24! = 1307504 15!9! Phép tương ứng 1- 1 Xét hai tập hữu hạn A, B. Khi đó có tồn tại một song ánh (phép tương ứng 1- 1) f : A → B khi và chỉ khi |A|= |B|. Như vậy, nếu tồn tại song ánh f thì ta có thể thay thế việc đếm các phần tử của tập A bởi các phần tử của tập B. trong các bài toán cụ thể thì song ánh f có thể được mô tả như các kỹ năng giải cụ thể rất hiệu quả như sau: 1.Mô tả phần tử đếm: Thay thế phần tử đếm bởi sự mô tả cụ thể chính xác của nó. 2.Mã hóa 0, 1 phần tử đếm: Thay thế phần tử đếm bởi bộ toàn số 0, 1. 3.Phương pháp đánh số: Thay thế cách xác định vị trí bởi các số thỏa mãn yêu cầu của bài toán. Tuy nhiên, chỉ thông qua việc giải các bài toán cụ thể chúng ta mới có thể nắm vững các kỹ năng giải này. 1.2.1 Mô tả phần tử đếm Kỹ năng này gồm 2 bước: 1. Xác định vị trí; 2. Sắp xếp vào vị trí đã chọn. Sau đây chúng ta xét một số bài toán minh họa: Bài 1. Tìm các số nguyên dương có 6 chữ số bao gồm 3 chữ số chẵn và 3 chữ số lẻ. Bài giải Ta có C63 cách lấy ra 3 vị trí để đặt 3 chữ số chẵn và 3 vị trí còn lại đặt 3 chữ số lẻ. Ở mỗi vị trí đã chọn ta có 5 cách chọn 1 chữ số chẵn hoặc lẻ. Vậy theo quy tắc nhân ta có C63 .56 bộ 6 chữ số trong đó có 3 chữ số chẵn, 3 chữ số lẻ. Tuy nhiên, nếu chữ số 0 đứng đầu thì chỉ được số có 5 chữ số nên ta phải bớt đi các bộ số này. Có C52 cách chọn 2 vị trí để đặt chữ số chẵn (vì số 0 đứng đầu). Vậy số bộ có số 0 đứng đầu là C52 .55 . 17 Đáp số: d = C63 .56 − C52 .55 = 281250. Bài 2. Cho tập A = {1, 2, 3}. Có bao nhiêu số nguyên dương gồm 10 chữ số lập được từ tập A, trong đó chữ số 3 xuất hiện đúng 2 lần. Hỏi có bao nhiêu số trong các số này chia hết cho 9. Bài giải 2 Có C10 cách chọn 2 vị trí trong 10 vị trí để đặt số 3. Tại mỗi vị trí trong 8 2 vị trí còn lại có 2 cách sắp xếp (1 hoặc 2). Vậy đáp số d = C10 .28 = 11520. Ký hiệu S(n) là tổng các chữ số của số n (với n là số thỏa mãn yêu cầu của bài toán). Ta suy ra: 14 = 6 + 8.1 ≤ S(n) ≤ 6 + 8.2 = 22 Vì n chia hết cho 9 nên 9|S(n), vậy nên S(n) = 18. Đã có hai số 3 nên tổng 8 chữ số còn lại bằng 12 nên chỉ có thể có bốn số 2 và bốn số 1. Suy ra số các số thỏa mãn yêu cầu bài toán và chia hết 10! cho 9 bằng d2 = P (2, 4, 4) = ⇒ d2 = 3150. 2!.4!4! Bài 3. Có bao nhiêu số gồm 4 chữ số được cấu tạo từ những chữ số của số 123124. Bài giải Trong kỹ năng mô tả phần tử của những bài toán phức tạp thì bước đầu tiên là phân loại các phần tử đếm có tính chất giống nhau (thường gọi là liệt kê). Những số được cấu tạo thuộc một trong những trường hợp sau: 1. Có 4 chữ số phân biệt d1 = 4! (vì chỉ có 4 chữ số phân biệt 1,2,3,4). 4! =6 2. Có 2 cặp chữ số giống nhau (2,2,1,1): d2 = 2!.2! 3. Có 1 cặp chữ số giống nhau, còn 2 chữ số còn lại là phân biệt. Có 2 cách chọn một cặp 2 chữ số giống nhau và C32 cách chọn 2 chữ số phân biệt từ 3 chữ số phân biệt còn lại. Suy ra d3 = 2.C32 .P (2, 1, 1) = 72 Đáp số: 24+6+72 =102. Bài 4. Cho tập A = {1, 2, 3, 4, 5}. Hỏi có bao nhiêu số gồm 6 chữ số của A trong đó có 3 số a, 2 số b và 1 số c, với a, b, c là các số đôi một phâm biệt thuộc A. Bài giải. Có C53 cách lấy 3 số phân biệt đôi một a, b, c của tập A. Có 3 cách chỉ định số nào xuất hiện 3 lần, số nào xuất hiện 2 lần sẽ có 2 cách chỉ định, 6! hiển nhiên số còn lại xuất hiện 1 lần và ta có đáp số d = C53 .3.2. . 3!2! Bài 5. Cho tập A = {0, 1, 2, 3, 4, 5}. Hỏi có bao nhiêu số gồm 5 chữ số của A sao cho mỗi số có đúng 3 chữ số giống nhau. Bài giải. 18