www.MATHVN.com - Toán học Việt Nam Chuyên đề: TỐI ƯU HĨA BÀI TỐN ĐẾM TRONG ĐẠI SỐ TỔ HỢP I ĐẶT VẤN ĐỀ Trong kì thi tuyển sinh Đại học năm 2012 năm 2013 toán tổ hợp xác suất xuất đề khối B (câu tổ hợp) đề khối A (câu xác suất) Điều làm thí sinh bất ngờ, nhiều em tỏ lúng túng khó định hướng cách làm, chí trình bày lời giải khơng biết lời giải đáp án liệu có không Qua nghiên cứu, giảng dạy học tập kinh nghiệm chúng tơi thiết nghĩ cần có giải pháp giúp học sinh nắm chất tốn tổ hợp, để từ học sinh có thêm cơng cụ hữu ích giúp cho q trình tìm lời giải toán tổ hợp học sinh cách chủ động, xác hiệu Chuyên đề khơng có tham vọng giải tất toán liên quan đến đại số tổ hợp, giải phần đại số tổ hợp Nhưng qua chuyên đề hi vọng thầy giáo học sinh có thêm phần tài liệu quý báu hỗ trợ việc tự nghiên cứu, tích lũy chun mơn, ơn tập giảng dạy II GIẢI QUYẾT VẤN ĐỀ *Bố cục Chuyên đề trình bày theo bố cục sau: A Cơ sở lý thuyết B Phương pháp C Các dạng toán D Bài tập tự rèn luyện *Nội dung A Cơ sở lý thuyết Một số kiến thức bản: Quy tắc đếm a Quy tắc cộng: Một công việc V bao gồm k công việc V1; V2; Vk độc lập với đó: V1: có n1 cách thực V2: có n2 cách thực … Vk có nk cách thực Như Số cách thực công việc V n = n1 + n2 + …+nk b Quy tắc nhân: Một công việc V thực qua k giai đoạn Đ1; Đ2; ;Đk độc lập với đó: Giai đoạn Đ1: có n1 cách thực Giai đoạn Đ2: có n2 cách thực … Giai đoạn Đk:có nk cách thực Như Số cách thực công việc V n = n1.n2 nk Hoán vị a) Hốn vị: ( Theo định nghĩa SGK) GV: Hồng Ngọc Hùng - www.mathvn.com www.MATHVN.com - Toán học Việt Nam +Khái niệm: Cho tập hợp A gồm n phần tử khác (n ≥ 1) Mỗi cách thứ tự n phần tử tập gọi hốn vị n phần tử +Cơng thức xác định: Pn = n(n − 1) 3.2.1 = n! + Chú ý: Quy ước 0! = b) Hoán vị có lặp + Khái niệm: Có n vật (n ≥ 1) vào n vị trí đó: Có n1 vật loại Có n2 vật loại … Có nk vật loại Ở n1+n2 + …+nk = n Mỗi cách thứ tự n vật vào n vị trí gọi hốn vị có lặp n phần tử Cơng thức xác định: + Cơng thức xác định: Số hốn vị có lặp n vật n! n1!.n2! nk ! +Chứng minh: Do có n1 vật giống nên số phương án n1 vật vào n1 vị trí phương án cần tìm, ta có n1! phương án giống Tương tự… Từ suy có Pn n! số hoán vị = n1!.n2! nk ! n1!.n2! nk ! c) Hốn vị vịng trịn + Khái niệm: Có n vật vào n vị trí theo đường trịn + Cơng thức xác định: Số hốn vị vòng tròn là: Pn −1 = (n − 1) 3.2.1 = (n − 1)! + Chứng minh: Cố định điểm đường tròn, n -1 vật vào n - vị trí cịn lại Như có (n -1)! số hốn vị vịng trịn Chỉnh hợp + Khái niệm: Cho tập A gồm n phần tử Mỗi gồm k (1 ≤ k ≤ n) phần tử thứ tự tập A gọi chỉnh hợp chập k n phần tử + Công thức xác định Ank = n(n − 1)(n − 2) ( n − k + 1) = n! (n − k )! Chú ý: Khi k = n Ank = Pn Ví dụ: Cho tập A gồm n số khác n ∈ {1,2, ,8,9} Số có k ( k ≤ n ) chữ số khác lấy từ tập A Ank Tổ hợp + Khái niệm: Cho tập A gồm n phần tử Mỗi tập gồm k (0 ≤ k ≤ n) phần tử tập A gọi tổ hợp chập k n phần tử + Công thức xác định số tổ hợp chập k n phần tử Cnk = n! k!(n − k )! + Tính chất: i) Cnk = Cnn − k GV: Hồng Ngọc Hùng - www.mathvn.com www.MATHVN.com - Toán học Việt Nam ii) Cnk−−11 + Cnk−1 = Cnk iii) Ank = k!Cnk Ví dụ: Cho tập A gồm có n phần tử, số tập co k phần tử lấy từ phần tử tập A Cnk B Phương pháp chung giải toán tổ hợp Phương pháp đếm trực tiếp Tùy theo tốn chia trường hợp hay không chia trường hợp Nội dung: Đếm trường hợp thỏa mãn yêu cầu tốn Đếm vị trí + Chọn vị trí cho số thứ theo yêu cầu toán, suy số vị trí cho số tiếp theo… + Sắp xếp số lại Phương pháp đếm loại trừ Nội dung: Đếm loại trừ theo hai bước + Bước 1: Đếm số phương án xảy ta có kết n1 + Bước 2: Đếm số phương án xảy không thỏa mãn yêu cầu tốn ta có kết n2 + Bước 3: Số phương án là: n = n1 – n2 Chú ý: Khi phương pháp đếm trực tiếp có nhiều trường hợp sử dụng phương pháp đếm loại trừ Phương pháp lấy trước xếp sau + Bước 1: Chọn trước cho đủ số lượng thỏa mãn tính chất mà tốn u cầu (Ví dụ chọn tập có k phần tử từ n phần tử ta có Cnk cách) + Bước 2: Sắp xếp Chú ý: Những tốn có xếp, cạnh nhau, có mặt Phương pháp tạo vách ngăn +Bước 1:Sắp xếp m đối tượng vào m vị trí tạo m + vách ngăn +Bước 2: Sắp xếp đối tượng khác theo yêu cầu tốn từ m +1 vách ngăn nói Nhận xét: *Hầu hết toán tổ hợp sử dụng phương pháp để giải quyết, nhiên linh hoạt phương pháp tùy thuộc vào khả học sinh *Đối với tốn mà tập ban đầu có số ta xét trường hợp xem số số có nghĩa ta kết n1, xét trường hợp số đứng đầu ta có kết n2, kết cần tìm n1-n2 C Các dạng tốn thường gặp Dạng 1: Tốn đếm số Cách giải thơng thường: Bước 1: Gọi số cần tìm n = a1a2 ak Bước 2: Liệt kê tính chất số n thỏa mãn yêu cầu Bước 3: Dựa vào tính chất xem tốn có chia trường hợp khơng Bước 4: Thứ tự đếm ( đếm ưu tiên) + Đếm chữ số có mặt tính chất + Đếm chữ số chưa đếm tập hợp ban đầu có chứa số + Đếm chữ số lại Bước 5: Sử dụng quy tắc cộng quy tắc nhân GV: Hoàng Ngọc Hùng - www.mathvn.com www.MATHVN.com - Toán học Việt Nam Chú ý: Đây cách giải thơng thường, sử dụng phương pháp để tốn có lời giải ngắn gọn Những toán tập ban đầu không chứa số Bài mở đầu: Cho tập A = {1,2,3,4,5,6,7} a)Gọi S tập số tự nhiên có chữ số khác lấy từ số tập A Tính n(S) b)Gọi B tập số tự nhiên chẵn có chữ số khác lấy từ tập A Tính n(B) Giải: a)Số cần tìm chỉnh hợp chập ta có n( S ) = A73 = 210 số b) Gọi số cần tìm n = a1a2 a3 +a3 có cách chọn + a1a2 có A62 = 30 + Vậy có 3.30=90 số suy n(B) = 90 Nhận xét: Bài tốn đơn giản, cần biết cơng thức xác suất, giải trọn vẹn câu IX.a đề thi ĐH – kA- 2013 “Gọi S tập hợp tất số tự nhiên gồm chữ số phân biệt chọn từ số 1, 2, 3, 4, 5, 6, Xác định số phần tử S Chọn ngẫu nhiên số từ S, tính xác suất để số chọn số chẵn” Đáp án: Xác suất cần tìm 90 = 210 Bài 1: Cho tập A = {1,2,3,4,5,6,7} Có số lẻ có chữ số khác cho: a) Chữ số đứng đầu số chẵn b) Chữ số ln có mặt lần Giải: a) Chữ số đứng đầu số chẵn Gọi số cần tìm n = a1a2 a3a4 n lẻ a1 chẵn nên a4 ∈ {1,3,5,7}, a1 ∈ {2,4,6} suy + a4 có cách chọn + a1 có cách chọn + chữ số cịn lại có A52 cách chọn Vậy có : 4.3.20 = 240 số cần tìm b) Gọi số cần tìm n = a1a2 a3a4 Cách 1: Đếm loại trừ + Đếm số lẻ có chữ số khác là: a4 có cách chọn (a4 ∈ {1,3,5,7}); chữ số cịn lại có A63 cách chọn, suy có A63 số + Đếm số lẻ có chữ số khác mà khơng có mặt chữ số là: a4 có cách chọn (a5 ∈ {1,3,5,7}); chữ số cịn lại có A53 cách chọn ( số khơng có), suy có A53 + Các số cần tìm là: A63 - A53 =240 số Cách 2: Đếm vị trí GV: Hồng Ngọc Hùng - www.mathvn.com www.MATHVN.com - Tốn học Việt Nam + a4 lẻ nên có cách chọn (a4 ∈ {1,3,5,7}); + Số có vị trí + chữ số cịn lại có vị trí lấy từ số cịn lại nên có A52 Vậy ta có 4.3 A52 = 240 số Bài 2: Cho tập A ={ 1,2,3,4,5,6,7,8,9} Có số tự nhiên có chữ số khác cho: a) Ln có mặt hai chữ số 2, b)Ln có mặt hai chữ số 2, hai chữ số ln đứng kề c)Ln có mặt hai chữ số 2, hai chữ số không đứng kề Giải: Gọi số cần tìm n = a1a2a3a4 a5 a) Cách 1: Đếm vị trí + Chữ số có vị trí suy chữ số có vị trí + chữ số cịn lại có A73 cách xếp + Vậy ta có 5.4 A73 = 4200 (số) Cách 2: Dùng phương pháp lấy trước xếp sau: + Lấy số từ tập A: Số 2,3 có cách chọn, số lại lấy từ tập A\{2,3} nên có C73 cách, suy có C73 cách lấy số mà 2, ln có mặt + Sắp xếp Sắp xếp số vào vị trí ta có 5! cách Vậy ta có C73 5!=4200 số b)Dùng phương pháp lấy trước xếp sau: + Lấy số từ tập A: Số 2,3 có cách chọn, số cịn lại lấy từ tập A\{2,3} nên có C73 cách, suy có C73 cách lấy tập gồm số mà 2, ln có mặt + Sắp xếp 2,3 Sắp xếp số 2,3 kề ta xem số a có 2! cách, xếp số a với số lại có 4! cách, từ số cách xếp chữ số chọn 2!.4! cách Vậy ta có C73 2!.4!=1680 số b)Do số trường hợp 2,3 không đứng cạnh nhiều nên ta sử dụng phương pháp loại trừ + Số số có chữ số khác ln có mặt chữ số 2,3 C73 5! + Số có chữ số khác cho 2,3 đứng kề C73 2!.4! + Vậy số cần tìm là: C73 5!- C73 2!.4!=2520 số Bài 3: GV: Hoàng Ngọc Hùng - www.mathvn.com www.MATHVN.com - Toán học Việt Nam Cho tập A ={ 1,2,3,4,5,6,7,8,9} Có số tự nhiên chẵn có chữ số khác cho: a)Ln có mặt chữ số b)Ln có mặt chữ số Nhận xét: Sự khác hai toán gì? Cách giải có khác hay khơng? Người GV phải định hướng cho HS biết để giải trọn vẹn xác tốn Giải: Gọi số cần tìm n = a1a2 a3a4 a5 a)Cách 1: Đếm vị trí + a5 có cách chọn +chữ số có vị trí +3 chữ số cịn lại có A83 cách xếp + Vậy có 4.4 A83 = 5376 số Cách 2: Chọn xếp (dành cho bạn đọc) b)Dự đoán cách giải học sinh sử dụng: tương tự câu a + a5 có cách chọn + chữ số có vị trí + chữ số cịn lại có A73 cách xếp + Vậy có: 4.4 A73 = 3360 số Sai lầm đâu: trường hợp số a5, cách chọn số khơng Lời giải đúng: *TH1: a5 =4, có A84 = 1680 số *TH1: a5 ≠ 4, + a5 có cách chọn + chữ số có vị trí + chữ số cịn lại có A73 cách xếp + suy ta có: 3.4 A73 = 2520 số Vậy số cần tìm là: 1680 + 2520 = 4200 số Bài 4: Từ số 1, 1, 1, 2, 2, 3, lập số có chữ số có chữ số 1, chữ số chữ số cịn lại 3,4 Giải: + Số số có chữ số từ số cho 7! + Nếu ta hoán vị a lần chữ số khơng đổi có 3!.2! lần bị lặp lại + Vậy số cần tìm 7! = 420 số 3!.2! Bài 5: Cho tập A = {1,2,3,4,5,6,7,8,9} Có số tự nhiên có chữ số chữ số có mặt lần, chữ số có mặt lần, chữ số khác có mặt lần Nhận xét: Sự khác gì? Số chữ số tập số cho số chữ số nhỏ tập số cho Giải: Bằng cách đếm vị trí 5 GV: Hồng Ngọc Hùng - www.mathvn.com www.MATHVN.com - Tốn học Việt Nam + Chọn vị trí vị trí xếp chữ số vào ta có C72 cách + Chọn vị trí xếp chữ số vào C53 cách + Cịn vị trí xếp chữ số khác lấy từ số lại tập A ta có A72 Vậy ta có C72 C53 A72 =8820 số Bài 6: Cho tập A = {1,3,5,7,9} Lập số tự nhiên gồm chữ số khác lấy từ tập A khơng bắt đâù từ 13 Giải: + Số có chữ số lấy từ tập A 5!=120 số +Số bắt đầu 13 là: Số1,3 có cách chọn, số cịn lại hốn vị số 5,7,9 nên có 3!=6 Số + Vậy số cần tìm là: 120 - =114 số Bài 7: Cho tập A = {1,2,3,4,5,6,7} Lập số tự nhiên gồm chữ số khác cho: a)Bắt đầu 456 b)Không bắt đầu 456 Giải: a) 456 Số có chữ số bắt đầu 456 • 4,5,6 có cách chọn • vị trí cịn lại lấy từ số số khác tập A nên có A42 = 12 Suy có 12 số bắt đầu 456 12 số b)Phương pháp loại trừ +Số có chữ số khác lấy từ tập A A75 = 2520 + Số có chữ số khác bắt đầu 456 12 + Số cần tìm 2520 – 12 =2508 số Bài 8: Từ số 1,3,5,6,7 lập số có chữ số khác lớn 6000 Giải: *TH1: số cần tìm có chữ số có 5! =120 (số) ln thỏa mãn điều kiện tốn *TH2: số cần tìm có chữ n = a1a2 a3a4 +a1 có cách chọn, a2 a3a4 có A43 = 24 cách chọn + suy có 2.24=48 số Vậy số cần tìm 120+ 24 =144 số Những toán mà tập số ban đầu chứa số Bài 9: Cho tập A ={0, 1, 2, 3, 7, 8, 9} Hỏi lập số tự nhiên a) có chữ số b) có chữ số khác c) lẻ có chữ số khác d)chẵn có chữ số khác Giải: GV: Hoàng Ngọc Hùng - www.mathvn.com www.MATHVN.com - Toán học Việt Nam Gọi số cần tìm n = a1a2a3a4 a5 a) + a1 có cách chọn (a1 ≠ 0) + a2 a3a4 a5 có 7.7.7.7 =2401 cách + Vậy có 6.2401 =14406 số b) + a1 có cách chọn (a1 ≠ 0) + a2 a3a4 a5 có A64 cách + có A64 = 2160 số c) +a5 lẻ nên a5 có cách chọn +a1 có cách chọn (a1 ≠ 0, a1 ≠ a5) + a2 a3a4 có A53 cách +vậy có 4.5 A53 = 1200 số c) Cách giải có tương tự câu b hay khơng? Dự đốn HS đưa cách giải: +a5 chẵn nên a5 có cách chọn +a1 có cách chọn (a1 ≠ 0, a1 ≠ a5) + a2 a3a4 có A53 cách +vậy có 3.5 A53 = 900 số Sai lầm HS gặp phải: Khi đếm a5 cách đếm a1 phải 6, lời giải sai Vậy cách giải nào? Lời giải Cách 1: Đếm loại trừ +Số tự nhiên có chữ số khác lấy từ tập A 2160 + Số tự nhiên lẻ có chữ số khác lấy từ tập A 1200 + Số tự nhiên chẵn cần tìm 2160 -1200 = 960 số Cách 2: Đếm trực tiếp TH1: a5 = 0:có cách chọn + a1a2a3a4 có A64 = 360 cách +suy ta có 360 số TH2: +a5 ≠ 0: a5 có cách + a1 có cách chọn (a1 ≠ 0, a1 ≠ a5) + a2 a3a4 có A53 = 60 cách chọn + suy ta có 2.5.60 =600 số Vậy số cần tìm 360 + 600 = 960 số Bài 10: Cho tập A = {0,1,2,3,4,5,6,7} a)Có thể lập số tự nhiên có chữ số khác ln có mặt chữ số b)Có thể lập số tự nhiên lẻ có chữ số khác ln có mặt chữ số c)Có thể lập số tự nhiên chẵn có chữ số khác ln có mặt chữ số GV: Hồng Ngọc Hùng - www.mathvn.com www.MATHVN.com - Toán học Việt Nam Giải: a)cách đếm trực tiếp Gọi số cần tìm n = a1a2 a3a4 a5 *TH1 +a1 =2 có cách chọn + a2 a3a4 a5 có A74 cách chọn +Suy ta có A74 = 840 số *TH2 +a2 =2 có cách chọn +a1 ≠ a1 ≠ nên có cách chọn + a3a4 a5 có A63 cách chọn +Suy ta có A63 = 720 số Vì vai trị vị trí a2 , a3 , a4 , a5 giống nên Số cần tìm 840 + 720.4=3720 số b) Gọi số cần tìm n = a1a2 a3a4 a5 *TH1 +a5 lẻ nên có cách chọn +a1 =2 có cách chọn + a2 a3a4 có A63 cách chọn +Suy ta có A63 = 480 số *TH2 +a5 lẻ nên có cách chọn +a2 =2 có cách chọn +a1 ≠ 0,a1 ≠ 2,a1 ≠ a5 nên có cách chọn + a3a4 có A52 cách chọn +Suy ta có 4.5 A52 = 400 số Vì vai trị vị trí a2 , a3 , a4 giống nên Số cần tìm 480 +400.3=1680 số c) Cách 1: Đếm loại trừ Số cần tìm 3720 – 1680 =2040 Cách : Sử dụng phương pháp lấy phần bù (i)Kể số đứng đầu *TH1: a5 =2, có A74 = 840 số *TH2: a5 ≠ 2, + a5 có cách chọn + chữ số có vị trí + chữ số cịn lại có A63 cách xếp + suy ta có: 3.4 A63 = 1440 số Vậy có: 840 + 1440 = 2280 số GV: Hoàng Ngọc Hùng - www.mathvn.com www.MATHVN.com - Toán học Việt Nam (ii) Số đứng đầu thỏa mãn điều kiện + a1 = có cách chọn -TH1 : a5 = có cách chọn, a2 a3 a4 có A63 cách chọn -TH2 : a5 ≠ số chẵn nên có cách chọn, số có vị trí, vị trí cịn lại có A52 Có A63 +2.3 A52 =240 số Vậy số cần tìm 2280-240=2040 số Cách 3: Đếm trực tiếp Gọi số cần tìm n = a1a2 a3a4 a5 Với a5 = *TH1 +a5 =0 nên có cách chọn +a1 =2 có cách chọn + a2 a3a4 có A63 cách chọn +Suy ta có A63 số *TH2 +a5 =0 nên có cách chọn +a1 ≠ nên có cách chọn +Số đặt vị trí a2; a3; a4 nên có cách chọn + vị trí cịn lại có A52 +Suy ta có 1.6.3 A52 số ứng với trường hợp Với a5 ≠ *TH1 +a5 =2 nên có có cách chọn +a1 ≠ 0,a1 ≠ nên có cách chọn + a2 a3a4 có A63 cách chọn +Suy ta có A63 số *TH2 +a5 ≠ 2, a5 ∈ {4,6} nên có cách chọn +a1=2 có cách chọn + a2 a3a4 có A53 cách chọn + suy có A53 số TH3 + a5 ≠ 2, a5 ∈ {4,6} nên có cách chọn + a1 ≠ 2, a1 ≠ nên a1 có cách chọn +Số đặt vị trí cịn lại nên có cách chọn +2 vị trí cịn lại có A52 cách chọn + suy có 2.5.3 A52 số Vậy số cần tìm A63 +1.6.3 A52 + A63 +2 A53 +2.5.3 A52 =2040 số Bài 11: Cho tập A ={1,2,3,4,5,6,7,8,9} GV: Hoàng Ngọc Hùng - www.mathvn.com 10 www.MATHVN.com - Tốn học Việt Nam Hỏi có số có chữ số khác cho ln có chữ số chẵn số tạo thành Giải: Lấy trước xếp sau Bước +Lấy chữ số chẵn số chẵn có C43 cách +Lấy số lẻ số lẻ có C53 cách +Suy số cách lấy chữ số C43 C53 cách Bước Sắp xếp số vào vị trí ta có 6! cách Vậy số cần tìm 6! C43 C53 =28800 (cách) Bài 12: Cho tập A ={0,1,2,3,4,5,6,7,8,9} Hỏi có số có chữ số khác cho ln có chữ số chẵn số tạo thành Nhận xét: khác hai tốn gì? Số có tập A số khơng có tập A Lời giải: +TH1: chữ số lấy không chứa chữ số Kết 11 ta có 6! C43 C53 +TH2 : chữ số lấy có mặt chữ số Bước 1: Chữ số có cách lấy, lấy chữ số chẵn có C42 cách lấy, lấy số lẻ có C53 cách Có C42 C53 cách lấy chữ số ln có mặt chữ số Bước : Sắp xếp +Sắp xếp chữ số lấy vào vị trí kể vị trí đứng đầu ta có ! cách +Vị trí đứng đầu có 5! cách + Số cách xếp thỏa mãn 6! - 5! Vậy số số cần tìm C42 C53 (6! - 5!) =36000 Bài 13 : Từ tập số 0, 1, 2, 6, 7, 8, Có số tự nhiên chẵn có chữ số khác lớn 5000 Giải : Gọi số cần tìm n = a1a2 a3a4 Do n > 5000 nên a1 =6,7,8,9 TH1: +a1 =6, a4 chẵn khác nên có cách chọn + a2 a3 có A52 + suy có A52 = 60 số TH2: +a1 =7, a4 chẵn nên có cách chọn + a2 a3 có A52 = 80 Ta có a1 =8 trường hợp a1 =9 trường hợp Vậy có (60 + 80).2=280 số Dạng 2: Bài toán xếp đồ vật Cách giải: Một số lưu ý giải dạng toán xếp + Sắp xếp n phần tử khác vào n vị trí có n! cách xếp GV: Hồng Ngọc Hùng - www.mathvn.com 11 www.MATHVN.com - Tốn học Việt Nam + Sắp xếp k phần tử giống vào n vị trí có Cnk cách (1 ≤ k ≤ n) + Sắp xếp n phần tử giống ( khơng thay đổi kết quả) vào n vị trí có cách xếp Bài 1: Có sách tốn; sách lý; sách hóa Các sách khác Sắp xếp sách vào kệ dài Có cách xếp cho: a) Các sách nằm tùy ý b)Các sách loại nằm kề Giải: a)Các sách khác nên có 12! cách xếp b) +Sắp xếp sách tốn có 3! cách +Sắp xếp sách lý có 4! cách +Sắp xếp sách hóa có 5! cách +Có 3! xếp nhóm sách +Vậy có 3!.3!.4!.5! = 103680 cách Bài 2: Người ta xếp sách toán, sách lý sách hóa vào kệ dài Biết sách khác nhau.Hỏi có cách xếp cho sách tốn lý khơng đứng cạnh Giải: +Sắp xếp sách vào kệ dài ta có 7! cách +Sắp xếp sách tốn lý đứng cạnh ta có 2! Khi số cách xếp sách cho sách toán lý đứng cạnh 2!6! +Suy số cách xếp cần tìm 7! – 2.6! = 3600 Bài 3: a)Có tem thư khác có bì thư khác Hỏi có cách dán tem thư vào bì thư cho bìa thư dán tem thư? b)Có tem thư khác bì thư khác Chọn tem thư dán vào bì thư cho bì thư dán tem thư Hỏi có cách làm c)Có tem thư khác có bì thư khác Chọn tem thư dán vào bì thư Một bì thư dán tem Hỏi có cách làm thế? Giải: a)Lấy tem thư dán vào bì thư có 4! cách b) +Chọn tem thư từ bì thư có cách chọn +Chọn bì thư từ bì thư có C86 cách chọn +Dán tem thư lên bì thư có 6! Cách dán + Số cách thực là: C86 6! =20160 c)Hoàn toàn tương tự Đáp số: C64 C84 4! =25200 Bài 4: Có bi xanh giống hệt bi đỏ khác Sắp xếp bi vào dãy có vng Hỏi có cách xếp cho a)Các viên bi nằm tùy ý b)Các viên bi màu nằm nhóm c)Các viên bi khác màu nằm xen kẻ GV: Hoàng Ngọc Hùng - www.mathvn.com 12 www.MATHVN.com - Toán học Việt Nam Giải: a) +Lấy vị trí xếp viên bi xanh giống hệt vào ta có C74 cách +Cịn vị trí xếp viên bi đỏ khác vào ta có 3! Cách +Số cách xếp là: 3! C74 cách b) +Số cách xếp viên bi xanh giống hệt làm thành nhóm cách +Số cách xếp viên bi đỏ 3! +Số cách xếp thỏa nhóm 2! Cách Khi ta có 3! 2! cách c) + Đỏ Xanh Đỏ Xanh Đỏ Xanh Đỏ + Chọn vị trí xen kẻ xếp viên bi đỏ giống hệt cách +Còn vị trí 3! cách xếp viên bi xanh khác +Vậy có 3! = cách Bài 5: Sắp xếp viên bi khác vào hộp Có cách xếp cho hộp có viên bi Giải: +Chọn viên bi hộp xếp vào hộp ta có C53 3! +Cịn viên bi xếp vào hộp TH1: Một hộp chứa lần viên bi có C22 C31 TH2: Một hộp chứa viên bi C21.C31 Vậy có tất C53 3! ( C22 C31 + C21 C31 ) Bài 6: Cần xếp thầy giáo học sinh vào dãy ghế dài cho thầy giáo không ngồi cạnh Giải: (phương pháp tạo vách ngăn) + Xếp học sinh vào vị trí ta có 6! + học sinh tạo vách ngăn, ta đặt thầy giáo vào vách ngăn ta có A72 Khi số cách xếp là: A72 6! Dạng 3: Bài toán chọn số phương án để thỏa mãn số điều kiện cho trước Các dạng toán thường gặp 1.Bài toán chọn tùy ý Chọn m phần tử từ n phần tử khác ≤ m ≤ n) số tổ hợp chập m n có Cnm cách 2.Bài tốn chọn nhât nhiều Cách giải: Cách 1: Chia trường hợp Cách 2: Đếm loại trừ (lấy phần bù) 3.Bài tốn chọn có mặt đủ loại Cách giải: GV: Hoàng Ngọc Hùng - www.mathvn.com 13 www.MATHVN.com - Toán học Việt Nam Cách 1: Đếm loại trừ (lấy phần bù) Cách 2: Chia trường hợp 4.Bài toán xếp, đem tặng, đem phân công thực nhiệm vụ khác Cách giải: +Chọn cho đủ số lượng +Đem xếp 5.Bài toán chọn tên Cách giải: +Chọn tên người có mặt +Chọn tên thành viên cịn lại 6.Bài tốn chọn nhiệm vụ Cách giải: +Chọn chức vụ thành viên có chức vụ chọn từ tập hợp ban đầu +Sau chọn xong chức vụ chọn thành viên khơng có chức vụ 7.Bài tốn chọn tên có chức vụ Cách giải: Chia trường hợp Bài 1: Tổ lớp 11A có 11 học sinh có học sinh nam học sinh nữ a)Có cách chọn học sinh tùy ý b)Có cách chọn học sinh có nam nữ c) Có cách chọn học sinh có nam nữ Giải: a)Chọn học sinh tùy ý có C118 cách b)Nhận xét: chia trường hợp có nhiều trường hợp Ta sử dụng cách đếm loại trừ +Chọn học sinh tùy ý có C115 cách +Chọn học sinh nam có C75 cách +Vì ta chọn học sinh ln có học sinh nam, Vậy có C115 - C75 = có nam nữ c) Cách 1: +Chọn học sinh tùy ý có C113 cách +Chọn học sinh nam có C73 cách +Chọn học sinh nữ có C43 + Vậy ta có C113 - C73 - C43 cách Cách 2: TH1: nam nữ, ta có C71 C43 TH2: nam nữ có C42 C72 TH3: nam nữ có C41 C73 Vậy có C71 C43 + C42 C72 + C41 C73 cách Bài 2: Đội bóng chuyền học sinh trường THPT Kỳ Lâm có học sinh khối 10; học sinh khối 11; 10 học sinh khối 12 a)Chọn từ học sinh Có cách chọn cho có đủ khối GV: Hồng Ngọc Hùng - www.mathvn.com 14 www.MATHVN.com - Toán học Việt Nam b)Chọn từ 15 học sinh có đủ khối Có cách chọn cho có học sinh khối 10 Giải: a) +Chọn học sinh tùy ý có C228 cách +Chọn học sinh khối 12 có C108 cách +Chọn học sinh hai khối 10 11 có C128 cách +Chọn học sinh có hai khối 10 12 có C158 - C108 +Chọn học sinh hai khối 12 11 có C178 - C108 +Vậy số cách cần tìm C228 - C108 - C128 -( C158 - C108 )-( C178 - C108 ) b)Xét trường hợp sau TH1:Chọn học sinh khối 10 + chọn học sinh khối 10 ta có C54 cách +Chọn 11 học sinh cịn lại khối 11 12 C1711 cách Suy có C54 C1711 cách TH2: Chọn học sinh khối 10 + chọn học sinh khối 10 ta có 1cách + Chọn 10 học sinh cịn lai khối 11 12 có C1710 − C1010 Suy có C1710 − C1010 cách Vậy số cách cần tìm C54 C1711 + C1710 − C1010 cách Bài 3: Tổ lớp 11A gồm có 12 học sinh có bạn Ánh Tuyết Tuấn Anh Chọn học sinh lập thành tổ học tập Có cách chọn cho Ánh Tuyết Tuấn Anh khơng đồng thời có mặt tổ học tập Giải: +TH1: Có Ánh Tuyết khơng có Tuấn Anh có C116 cách chọn +TH2: Có Tuấn Anh khơng có Ánh Tuyết có C116 cách chọn Vậy có tất C116 cách Bài 4: Một lớp học có 30 học sinh ln có An Lập thành đội văn nghệ có 10 người, có đội trưởng đội phó a)Có cách lập đội cho An ln có mặt đội b) Có cách lập đội cho An ln có mặt đội đội trưởng đội phó Giải: a)Cách 1: +Lấy học sinh An có cách +Lấy học sinh khơng có An có C299 +Chọn đội trưởng 10 bạn có C103 +Chọn đội phó bạn cịn lại có C72 + Vậy số cách chọn xếp là C299 C103 C72 Cách 2: GV: Hoàng Ngọc Hùng - www.mathvn.com 15 www.MATHVN.com - Toán học Việt Nam Xét trường hợp sau: TH1: An đội trưởng +Chọn thêm đội trưởng có C292 cách +Chọn đội phó có C272 cách +Chọn thành viên cịn lại có C255 Suy có C292 C272 C255 cách TH2: An đội phó +Chọn đội trưởng có C293 cách +Chọn thêm đội phó có C26 cách +Chọn thành viên cịn lại có C255 cách C255 cách Suy có C293 C26 TH3: An đội viên ( không đội trưởng, khơng đội phó) +Chọn đội trưởng có C293 cách +Chọn đội phó có C262 cách +Chọn thành viên có C244 cách Suy có C293 C262 C244 cách Vậy số cách cần tìm C292 C272 C255 + C293 C26 C255 + C293 C262 C244 cách b) Xét trường hợp sau: TH1: An đội trưởng +Chọn thêm đội trưởng có C292 cách +Chọn đội phó có C272 cách +Chọn thành viên cịn lại có C255 Suy có C292 C272 C255 cách TH2: An đội phó +Chọn đội trưởng có C293 cách +Chọn thêm đội phó có C26 cách +Chọn thành viên cịn lại có C255 cách Suy có C293 C26 C255 cách Vậy có C292 C272 C255 + C293 C26 C255 cách Bài 5: (ĐH-B-2005) Một đội niên tình nguyện có 15 sinh viên gồm 12 nam nữ Hỏi có cách phân cơng đội tình nguyện giúp đỡ xã miền núi cho xã có nam nữ Giải: +Phân nam nữ xã thứ có C124 C31 cách + Phân nam nữ xã thứ có C84 C21 cách + Phân nam nữ xã thứ có C44 C11 Vậy số cách cần tìm C124 C31 C84 C21 C44 C11 cách GV: Hoàng Ngọc Hùng - www.mathvn.com 16 www.MATHVN.com - Toán học Việt Nam Bài 6: Một giáo có sách tốn sách lý khác Lấy từ đủ hai loại đem tặng cho học sinh em có Hỏi có cách tặng Giải: *Chọn đủ số lượng + Số cách lấy C105 cách + Số cách lấy lý C65 cách, + Do số sách tốn số lượng cần lấy nên số cách lấy đủ loại C105 - C65 *Sắp xếp Lấy đem tặng học sinh có 5! Cách Vậy số cách tặng cần tìm 5!( C105 - C65 ) cách Bài 7:Trong mặt phẳng cho đa giác có 10 cạnh a)Có tam giác tạo thành từ đỉnh tứ giác b)Có tam giác tạo có đủ cạnh đa giác c)Có tam giác tạo có đủ cạnh đa giác d)Có tam giác khơng chứa cạnh đa giác Giải: a)Số đỉnh nên số tam giác tạo thành C103 tam giác b)Tam giác có đỉnh liên tiếp đa giác tam giác có chứa cạnh đa giác Các tam giác bắt đầu A1 A2 A3 ; A2 A3 A4 … A10 A1 A2 suy có 10 tam giác cần tìm c)Tam giác có hai đỉnh thuộc cạnh đa giác đỉnh thứ khơng kề với đỉnh Ứng với cạnh có tam giác tạo thành Vì có 10.6 = 60 tam giác tạo thành d) Số tam giác cần tìm C103 -10 – 60 = 50 tam giác cần tìm D.BÀI TẬP TỰ LUYỆN 1) Có cách xếp người khách gồm nam nữ ngồi vào hàng ghế nếu: a) họ ngồi chỗ được? b) họ ngồi kề nhau? c) nam ngồi kề nhau, nữ ngồi kề hai nhóm có ghế trống? 2) Có cách xếp chỗ ngồi cho người khách a) vào ghế xếp thành dãy b) vào ghế chung quanh bàn tròn, khơng có phân biệt ghế 3) Mười người muốn chụp ảnh chung Họ muốn chụp nhiều ảnh khác cách đổi chỗ đứng lẫn Cho lần đổi chỗ chụp ảnh phút, hỏi cần để chụp tất ảnh khác nhau? 4) Có số tự nhiên gồm ba chữ số khác khác biết tổng ba chữ số 8? 5) Một dãy ghế dành cho nam sinh nữ sinh Có cách xếp chỗ ngồi nếu: a) họ ngồi chỗ b) nam sinh ngồi kề nhau, nữ sinh ngồi kề GV: Hoàng Ngọc Hùng - www.mathvn.com 17 www.MATHVN.com - Tốn học Việt Nam c) có nữ sinh ngồi kề 6) Có số tự nhiên gồm ba chữ số khác biết tổng ba chữ số 12? Một phịng khách có chỗ đặt tranh, ảnh tượng Chủ nhà muốn trang trí cách xếp đặt tranh khác vào chỗ, ảnh khác vào chỗ thứ hai tượng khác vào chỗ cịn lại Hỏi có cách trang trí phịng khách? 7) Ta muốn mời người ngồi vào dãy ghế Có cách xếp chỗ ngồi nếu: a) Có người bọn họ muốn ngồi kề nhau? b) Có người bọn họ khơng muốn ngồi kề nhau? c) Có người bọn họ không muốn ngồi kề đơi một? 8) Một bàn dài có 12 ghế, bên ghế Người ta muốn xếp chỗ ngồi cho 12 người khách gồm nam nữ Hỏi có cách xếp chỗ ngồi nếu: a) họ ngồi chỗ ? b) nam ngồi bên, nữ ngồi bên ? c) nam nữ ngồi đối diện ? d) nam nữ ngồi xen kẽ đối diện ? 9) Cho số 0,1,2,3,4,5,6 Có thể lập số gồm chữ số khác lấy từ số cho, cho: a) Số chẵn b) Số chia hết cho c) Ln có mặt chữ số 10) Cho số: 0,1,2,3,4,5,6,7 Có thể lập số gồm chữ số khác lấy từ chữ số cho cho số lẻ đứng liền 11) Cho số : 0,1,2,3,4,5,6 a) Có thể lập số gồm chữ số lấy từ số cho cho số có mặt lần, số khác có mặt lần b) Có thể lập số có chữ số lấy từ số cho cho số có mặt lần, số khác có mặt vài lần 12) Cho số: 0,1,2,3,4,5 Có thể lập số từ số khác lấy từ số cho Sao cho: a) Ln có mặt chữ số b) Số chia hết cho c) Không chữ số 13) Cho số: 0,1,2,3,4,5,6 Có thể lập số có chữ số lấy từ số cho cho: a) Số đầu số cuối giống nhau, số khác b) chữ số đầu chữ số cuối giống 14) Cho số: 0,1,2,3,4,5,6,7 a) Có thể lập số gồm 10 chữ số cho số có mặt lần, số có mặt lần Các số khác có mặt lần b) Có thể lập số gồm chữ số cho số có mặt lần, số khác có mặt vài lần 15) Cho số: 0,1,2,3,4,5 Có thể lập số gồm chữ số cho số chẵn không đứng liền GV: Hoàng Ngọc Hùng - www.mathvn.com 18 www.MATHVN.com - Tốn học Việt Nam 16) Một nhóm người thành lập công ty Họ muốn chọn ban điều hành gồm giám đốc,một phó giám đốc thủ qũy Có 10 người hội đủ điều kiện để chọn Hỏi có cách chọn ban điều hành? 17) Huấn luyện viên đội bóng muốn chọn cầu thủ để đá luân lưu 11m Có cách chọn nếu: a) Cả 11 cầu thủ có khả nhau? ( Kể thủ mơn) b) Có cầu thủ bị chấn thương thiết phải bố trí cầu thủ A đá số cầu thủ B đá số 4? 18) Một người muốn xếp đặt số tượng vào dãy chỗ trống kệ trang trí Có cách xếp nếu: a) Người có tượng khác nhau? b) Người có tượng khác nhau? c) Người có tượng khác nhau? 19) Với năm số 1,2,3,4,5 lập số gồm chữ số số có mặt hai lần số cịn lại số có mặt lần? 20) Có số tự nhiên gồm chữ số khác biết rằng: a) số chia hết cho 5? b) số phải có mặt ba chữ số 0,1,2 ? 32) Với sáu số 2,3,5,6,7,8, ta muốn thành lập số gồm bốn chữ số khác a) Có số nhỏ 5000 ? b) Có số chẵn nhỏ 7000 ? 21) Một lớp học có 30 học sinh Trong có 12 nữ, cần thành lập tổ cơng tác gồm người Có cách lập cho tổ có nữ 22) Trong không gian cho tập hợp gồm điểm khơng có điểm đồng phẳng Hỏi lập hình tứ diện với đỉnh thuộc tập hợp cho 23) Một đề thi có 15 câu hỏi Mỗi thí sinh phải rút câu (4 câu rút “ đề thi ” thí sinh này) a) Có đề thi khác nhau? ( Hai đề thi coi khác có câu khác ) b) Tham gia kỳ thi có 2736 thí sinh Chứng tỏ có thí sinh gặp đề thi 24) Một tổ trực gồm nam sinh nữ sinh Giáo viên trực muốn chọn học sinh để trực thư viện Có cách chọn nếu: a) Chọn học sinh được? b) Có nữ sinh chọn? c) Có nữ sinh chọn? 25) Một họ n đường thẳng song song cắt họ m đường thẳng song song Hỏi có hình bình hành tạo thành 26) Cho tập X = {a, b, c, d } Có tạp X a) Không chứa phần tử a? b) Chứa phần tử a? 27) Một bình đựng viên bi xanh, viên bi đỏ, chúng khác màu Lấy hai viên a) Có kết khác nhau? GV: Hoàng Ngọc Hùng - www.mathvn.com 19 www.MATHVN.com - Tốn học Việt Nam b) Có cách lấy viên bi xanh?, hai viên bi đỏ? Hai viên bi khác màu? 28) Giáo viên hướng dẫn lao động muốn chia học sinh làm nhóm gồm 4, 3, học sinh Có cách chia? 29) Cho đa giác lồi có n đỉnh ( n ≥ ) a) Tính số đường chéo đa giác này; b) Biết ba đường chéo khơng qua đỉnh khơng đồng quy, tính số giao điểm ( đỉnh ) đường chéo 30) Một tổ trực gồm nam sinh nữ sinh Giáo viên trực muốn chọn nhóm học sinh Có cách chọn nhóm phải có nữ sinh? 31) Giám đốc cơng ty muốn chọn nhóm người vào hội đồng tư vấn Trong cơng ty có 12 người hội đủ điều kiện để chọn, có hai cặp vợ chồng Hỏi có cách chọn nếu: a) Hội đồng có cặp vợ chồng? b) Hội đồng gồm vợ lẫn chồng ( có )? 32) Tính số đường chéo đa giác lồi có n cạnh Tìm đa giác có số cạnh số đường chéo 33) (ĐH-B-2002) Cho đa giác A1 A2 A2 n (n ≥ 2, n ∈ Z ) nội tiếp đường trịn (O) Biết số tam giác có đỉnh 2n điểm A1 , A2 , , A2 n nhiều gấp 20 lần số hình chữ nhật có đỉnh 2n điểm A1 , A2 , , A2 n , tìm n? 34) (ĐH-B-2004) Trong mơn học, thầy giáo có 30 câu hỏi khác gồm câu hỏi khó, 10 câu hỏi trung bình, 15 câu hỏi dễ Từ 30 câu hỏi lập đề kiểm tra, đề gồm câu hỏi khác nhau, cho đề thiết phải có đủ loại câu hỏi ( khó, trung bình, dễ ) số câu hỏi dễ khơng 2? 35) Có số tự nhiên gồm 2008 chữ số cho tổng chữ số III KẾT LUẬN Theo quan điểm riêng chuyên đề “tối ưu hóa tốn đếm đại số tổ hợp” có đóng góp sau: Đã hệ thống hóa, phân tích, diễn giải số khái niệm đại số tổ hợp khái niệm liên quan có chứng minh 2.Thống kê số dạng toán điển hình liên quan đến tổ hợp – đặc biệt toán đếm 3.Xây dựng số biện pháp sư phạm để rèn luyện kỹ giải vấn đề liên quan đến đại số tổ hợp mà chủ yếu tốn đếm GV: Hồng Ngọc Hùng - www.mathvn.com 20 ... học sinh được? b) Có nữ sinh chọn? c) Có nữ sinh chọn? 25) Một họ n đường thẳng song song cắt họ m đường thẳng song song Hỏi có hình bình hành tạo thành 26) Cho tập X = {a, b, c, d } Có tạp X a)... khác theo yêu cầu to? ?n từ m +1 vách ngăn nói Nhận xét: *Hầu hết to? ?n tổ hợp sử dụng phương pháp để giải quyết, nhiên linh hoạt phương pháp tùy thuộc vào khả học sinh *Đối với to? ?n mà tập ban đầu... Dạng 2: Bài to? ?n xếp đồ vật Cách giải: Một số lưu ý giải dạng to? ?n xếp + Sắp xếp n phần tử khác vào n vị trí có n! cách xếp GV: Hoàng Ngọc Hùng - www.mathvn.com 11 www.MATHVN.com - To? ?n học Việt