Phương pháp giải bài toán to hợp chỉnh hợp

CHUYÊN ĐỀ:HOÁN VỊ – CHỈNH HỢP – TỔ HỢPA. TÓM TẮT GIÁO KHOA VÀ PHƯƠNG PHÁP GIẢI TOÁN1. Hoán vịĐịnh nghĩa1Cho tập hợp X gồm n phần tử phân biệt [ n � 0] . Mỗi cách sắp xếp n phần tử của X theo một thứ tự nàođó được gọi là một hoán vị của n phần tử. Số các hoán vị của n phần tử được ký hiệu là Pn.Pn = n! = 1.2...n . Quy ước: 0! = 1.Ví dụ 1. Sắp xếp 5 người vào một băng ghế có 5 chỗ. Hỏi có bao nhiêu cách.GiảiMỗi cách đổi chỗ 1 trong 5 người trên băng ghế là 1 hoán vị.Vậy có P5 = 5! = 120 cách sắp.Ví dụ 2. Từ các chữ số 0, 1, 2, 3, 4 có thể lập được mấy số tự nhiên có 5 chữ số khác nhau.Giải2Gọi A = a1a2a3a4a5 với a1 � 0 và a1, a2, a3, a4, a5 phân biệt là số cần lập.+ Bước 1: chữ số a1 � 0 nên có 4 cách chọn a1.+ Bước 2: sắp 4 chữ số còn lại vào 4 vị trí có 4! = 24 cách.Vậy có 4.24 = 96 số.2. Chỉnh hợpĐịnh nghĩa3Cho tập hợp X gồm n phần tử phân biệt [ n � 0] . Mỗi cách chọn ra k [ 0 � k � n ] phần tử của X vàsắp xếp theo một thứ tự nào đó đượ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 kcủa n phần tử được ký hiệu là A kn .A kn =n!.[n - k]!Nhận xét:A nn = n! = Pn .Ví dụ 3. Sắp xếp 5 người vào một băng ghế có 7 chỗ. Hỏi có bao nhiêu cách.4GiảiMỗi cách chọn ra 5 chỗ ngồi từ băng ghế để sắp 5 người vào và có hoán vị là một chỉnh hợp chập 5 của 7.7!5= 2520 cách sắp.Vậy có A 7 =[7 - 5]!Ví dụ 4. Từ tập hợp X = { 0; 1; 2; 3; 4; 5} có thể lập được mấy số tự nhiên có 4 chữ số khác nhau.GiảiGọi A = a1a2a3a4 với a1 � 0 và a1, a2, a3, a4 phân biệt là số cần lập.+ Bước 1: chữ số a1 � 0 nên có 5 cách chọn a1.5+ Bước 2: chọn 3 trong 5 chữ số còn lại để sắp vào 3 vị trí A 53 cách.Vậy có 5A 53 = 300 số.3. Tổ hợpĐịnh nghĩaCho tập hợp X gồm n phần tử phân biệt [ n � 0] . Mỗi cách chọn ra k [ 0 � k � n ] phần tử của X đượcgọ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 phần tử được ký hiệu là C kn .6n!.k![n - k]!Ví dụ 5. Có 10 cuốn sách toán khác nhau. Chọn ra 4 cuốn, hỏi có bao nhiêu cách.GiảiMỗi cách chọn ra 4 trong 10 cuốn sách là một tổ hợp chập 4 của 10.4Vậy có C10= 210 cách chọn.Ckn =Ví dụ 6. Một nhóm có 5 nam và 3 nữ. Chọn ra 3 người sao cho trong đó có ít nhất 1 nữ. Hỏi có bao nhiêucách.Giải7+ Trường hợp 1: chọn 1 nữ và 2 nam.- Bước 1: chọn ra 1 trong 3 nữ có 3 cách.- Bước 2: chọn ra 2 trong 5 nam có C25 .Suy ra có 3C25 cách chọn.+ Trường hợp 2: chọn 2 nữ và 1 nam.- Bước 1: chọn ra 2 trong 3 nữ có C23 cách.- Bước 2: chọn ra 1 trong 5 nam có 5.Suy ra có 5C23 cách chọn.+ Trường hợp 3: chọn 3 nữ có 1 cách.8Vậy có 3C25 + 5C23 + 1 = 46 cách chọn.Ví dụ 7. Hỏi có thể lập được bao nhiêu số tự nhiên có 4 chữ số sao cho trong mỗi số đó, chữ số hàngngàn lớn hơn hàng trăm, chữ số hàng trăm lớn hơn hàng chục và chữ số hàng chục lớn hơn hàng đơn vị.GiảiGọi A = a1a2a3a4 với 9 � a1 > a2 > a3 > a4 � 0 là số cần lập.X = { 0; 1; 2; ...; 8; 9} .Từ 10 phần tử của X ta chọn ra 4 phần tử bất kỳ thì chỉ lập được 1 số A. Nghĩa là không có hoán vị hay làmột tổ hợp chập 4 của 10.94Vậy có C10= 210 số.Nhận xét:i] Điều kiện để xảy ra hoán vị, chỉnh hợp và tổ hợp là n phần tử phải phân biệt.ii] Chỉnh hợp và tổ hợp khác nhau ở chỗ là sau khi chọn ra k trong n phần tử thì chỉnh hợp có sắp thứ tựcòn tổ hợp thì không.4. Phương pháp giải toán4.1. Phương pháp 110Bước 1. Đọc kỹ các yêu cầu và số liệu của đề bài. Phân bài toán ra các trường hợp, trong mỗi trường hợplại phân thành các giai đoạn.Bước 2. Tùy từng giai đoạn cụ thể và giả thiết bài toán để sử dụng quy tắc cộng, nhân, hoán vị, chỉnh hợphay tổ hợp.Bước 3. Đáp án là tổng kết quả của các trường hợp trên.11Ví dụ 8. Một nhóm công nhân gồm 15 nam và 5 nữ. Người ta muốn chọn từ nhóm ra 5 người để lậpthành một tổ công tác sao cho phải có 1 tổ trưởng nam, 1 tổ phó nam và có ít nhất 1 nữ. Hỏi có bao nhiêucách lập tổ công tác.Giải+ Trường hợp 1: chọn 1 nữ và 4 nam.- Bước 1: chọn 1 trong 5 nữ có 5 cách.2- Bước 2: chọn 2 trong 15 nam làm tổ trưởng và tổ phó có A 15cách.2- Bước 3: chọn 2 trong 13 nam còn lại có C13cách.22Suy ra có 5A 15cách chọn cho trường hợp 1..C1312+ Trường hợp 2: chọn 2 nữ và 3 nam.- Bước 1: chọn 2 trong 5 nữ có C25 cách.2- Bước 2: chọn 2 trong 15 nam làm tổ trưởng và tổ phó có A 15cách.- Bước 3: chọn 1 trong 13 nam còn lại có 13 cách.2Suy ra có 13A 15.C25 cách chọn cho trường hợp 2.+ Trường hợp 3: chọn 3 nữ và 2 nam.- Bước 1: chọn 3 trong 5 nữ có C53 cách.2- Bước 2: chọn 2 trong 15 nam làm tổ trưởng và tổ phó có A 15cách.132Suy ra có A 15.C53 cách chọn cho trường hợp 3.2222Vậy có 5A 15.C13+ 13A 15.C25 + A 15.C53 = 111300 cách.Cách khác:2+ Bước 1: chọn 2 trong 15 nam làm tổ trưởng và tổ phó có A 15cách.+ Bước 2: chọn 3 tổ viên, trong đó có nữ.2- Trường hợp 1: chọn 1 nữ và 2 nam có 5.C13cách.- Trường hợp 2: chọn 2 nữ và 1 nam có 13.C25 cách.- Trường hợp 3: chọn 3 nữ có C53 cách.142223Vậy có A 15 [ 5.C13 + 13.C5 + C5 ] = 111300 cách.4.2. Phương pháp 2.Đối với nhiều bài toán, phương pháp 1 rất dài. Do đó ta sử dụng phương pháp loại trừ [phần bù] theophép toán A U A = X � A = X \ A .Bước 1. Chia yêu cầu của đề thành 2 phần là yêu cầu chung X [tổng quát] gọi là loại 1 và yêu cầu riêngA. Xét A là phủ định của A, nghĩa là không thỏa yêu cầu riêng gọi là loại 2.Bước 2. Tính số cách chọn loại 1 và loại 2.Bước 3. Đáp án là số cách chọn loại 1 trừ số cách chọn loại 2.15Chú ý:Cách phân loại 1 và loại 2 có tính tương đối, phụ thuộc vào chủ quan của người giải.Ví dụ 9. Từ các chữ số 0, 1, 2, 3, 4 có thể lập được mấy số tự nhiên có 5 chữ số khác nhau.Giải+ Loại 1: chữ số a1 tùy ý, ta có 5! = 120 số.+ Loại 2: chữ số a1 = 0, ta có 4! = 24 số.Vậy có 120 – 24 = 96 số.16Ví dụ 10. Một nhóm có 7 nam và 6 nữ. Chọn ra 3 người sao cho trong đó có ít nhất 1 nữ. Hỏi có baonhiêu cách.Giải3+ Loại 1: chọn 3 người tùy ý trong 13 người có C13 cách.+ Loại 2: chọn 3 nam [không có nữ] trong 7 nam có C73 cách.3Vậy có C13- C73 = 251 cách chọn.17Ví dụ 11. Từ 20 câu hỏi trắc nghiệm gồm 9 câu dễ, 7 câu trung bình và 4 câu khó người ta chọn ra 10 câuđể làm đề kiểm tra sao cho phải có đủ cả 3 loại dễ, trung bình và khó. Hỏi có thể lập được bao nhiêu đềkiểm tra.Giải10+ Loại 1: chọn 10 câu tùy ý trong 20 câu có C20 cách.+ Loại 2: chọn 10 câu có không quá 2 trong 3 loại dễ, trung bình và khó.- Trường hợp 1: chọn 10 câu dễ và trung bình trong 16 câu có C1016 cách.- Trường hợp 2: chọn 10 câu dễ và khó trong 13 câu có C1013 cách.- Trường hợp 3: chọn 10 câu trung bình và khó trong 11 câu có C1011 cách.1810Vậy có C20 -1010+ C11[ C1610 + C13] = 176451 đề kiểm tra.Chú ý:Giải bằng phương pháp phần bù có ưu điểm là ngắn tuy nhiên nhược điểm là thường sai sót khi tính sốlượng từng loại.Ví dụ 12. Từ 20 câu hỏi trắc nghiệm gồm 9 câu dễ, 7 câu trung bình và 4 câu khó người ta chọn ra 7 câuđể làm đề kiểm tra sao cho phải có đủ cả 3 loại dễ, trung bình và khó. Hỏi có thể lập được bao nhiêu đềkiểm tra.Cách giải sai:197+ Loại 1: chọn 7 câu tùy ý trong 20 câu có C20cách.+ Loại 2: chọn 7 câu không thỏa yêu cầu.- Trường hợp 1: chọn 7 câu dễ trong 9 câu có C79 cách.- Trường hợp 2: chọn 7 câu trung bình có 1 cách.7- Trường hợp 3: chọn 7 câu dễ và trung bình trong 16 câu có C16cách.7- Trường hợp 4: chọn 7 câu dễ và khó trong 13 câu có C13cách.7- Trường hợp 5: chọn 7 câu trung bình và khó trong 11 câu có C11cách.207Vậy có C20 -[ 1 + C79 + C167 + C137 + C117 ] = 63997 đề kiểm tra!Sai sót trong cách tính số đề loại 2. Chẳng hạn, khi tính số đề trong trường hợp 3 ta đã tính lặp lại trườnghợp 1 và trường hợp 2.Cách giải sai khác:7+ Loại 1: chọn 7 câu tùy ý trong 20 câu có C20cách.+ Loại 2: chọn 7 câu không thỏa yêu cầu.7- Trường hợp 1: chọn 7 câu dễ hoặc trung bình trong 16 câu có C16cách.7- Trường hợp 2: chọn 7 câu dễ hoặc khó trong 13 câu có C13cách.217- Trường hợp 3: chọn 7 câu trung bình hoặc khó trong 11 câu có C11cách.7Vậy có C20 -[ C167 + C137 + C117 ] = 64034 đề kiểm tra.Sai sót do ta đã tính lặp lại số cách chọn đề chỉ có 7 câu dễ và đề chỉ có 7 câu trung bình trong trường hợp1 và trường hợp 2.Cách giải đúng:7+ Loại 1: chọn 7 câu tùy ý trong 20 câu có C20cách.+ Loại 2: chọn 7 câu không thỏa yêu cầu.7- Trường hợp 1: chọn 7 câu dễ hoặc trung bình trong 16 câu có C16cách.227- Trường hợp 2: chọn 7 câu dễ và khó trong 13 câu có C13- C79 cách.7- Trường hợp 3: chọn 7 câu trung bình và khó trong 11 câu có C11- 1 cách.7Vậy có C20 -[ C167 + C137 -7C79 + C11- 1] = 64071 đề kiểm tra.Ví dụ 13. Hội đồng quản trị của một công ty gồm 12 người, trong đó có 5 nữ. Từ hội đồng quản trị đóngười ta bầu ra 1 chủ tịch hội đồng quản trị, 1 phó chủ tịch hội đồng quản trị và 2 ủy viên. Hỏi có mấycách bầu sao cho trong 4 người được bầu phải có nữ.Giải+ Loại 1: bầu 4 người tùy ý [không phân biệt nam, nữ].232- Bước 1: bầu chủ tịch và phó chủ tịch có A 12cách.2- Bước 2: bầu 2 ủy viên có C10cách.22Suy ra có A 12cách bầu loại 1..C10+ Loại 2: bầu 4 người toàn nam.- Bước 1: bầu chủ tịch và phó chủ tịch có A 27 cách.- Bước 2: bầu 2 ủy viên có C25 cách.Suy ra có A 27.C25 cách bầu loại 2.2422Vậy có A 12.C10- A 27.C25 = 5520 cách.5. Hoán vị lặp [tham khảo]Cho tập hợp X có n phần tử gồm n1 phần tử giống nhau, n2 phần tử khác lại giống nhau, …, nk phần tửkhác nữa lại giống nhau [ n1 + n2 + ... + nk = n ] . Mỗi cách sắp n phần tử này vào n vị trí là một hoánvị lặp, số hoán vị lặp làn!.n1 !n2 !...nk !25