Chương 1 GIẢI TÍCH TỔ HỢP Không có bài toán nào không giải được. Chúng ta phải biết và sẽ biết – David Hilbert 1.1 Quy tắc cộng – Quy tắc nhân .1 Quy tắc cộng .2 Quy tắc nhân .2 Hoán vị – Chỉnh hợp – Tổ hợp .1 Hoán vị không lặp .2 Chỉnh hợp không lặp .3 Tổ hợp không lặp .3 Bài tập tự luận .4 Câu hỏi trắc nghiệm. 10 Mục tiêu: Sau khi học xong chương này, sinh viên có khả năng giải quyết các vấn đề sau: 1) Hiểu được quy tắc cộng, quy tắc nhân. 2) Áp dụng được quy tắc cộng, quy tắc nhân để giải các bài toán liên quan.
3) Hiểu định nghĩa tổ hợp không lặp, chỉnh hợp không lặp và hoán vị. 4) Áp dụng được công thức tổ hợp không lặp, chỉnh hợp không lặp và hoán vị để giải các bài toán liên quan.1 Quy tắc cộng – Quy tắc nhân 1.1 Quy tắc cộng Để đếm số cách thực hiện một công việc nào đó. Ta giả sử rằng, công việc đó có thể có nhiều trường hợp để thực hiện, cụ thể như sau: – Trường hợp 1 có n1 cách thực hiện. – Trường hợp 2 có n2 cách thực hiện.
7 GIẢI TÍCH TỔ HỢP. – Trường hợp k có nk cách thực hiện. Khi đó, số cách thực hiện công việc này được tính như sau: n = n1 + n2 +. Trong một lớp có 15 sinh viên nam và 30 sinh viên nữ.
Hỏi có bao nhiêu cách chọn ra 1 sinh viên làm lớp trưởng? Giải. Ta thấy • Trường hợp là Nam −→ n1 = 15 cách chọn; • Trường hợp là Nữ −→ n2 = 30 cách chọn. Khi đó, số cách chọn 1 lớp trưởng là n = n1 + n2 = 15 + 30 = 45 cách.2 Quy tắc nhân Tương tự như trên, nếu công việc đó được chia thành nhiều giai đoạn để thực hiện, cụ thể như sau: – Giai đoạn 1 có n1 cách thực hiện. – Giai đoạn 2 có n2 cách thực hiện.
– Giai đoạn k có nk cách thực hiện. Khi đó, số cách thực hiện công việc này được tính như sau: n = n1. Giả sử rằng để đi từ A đến B chỉ có thể đi từ A qua B rồi qua C mới đến được D. Cho biết để đi từ điểm A đến điểm B có 3 cách đi; đi từ điểm B đến điểm C có 5 cách đi; đi từ điểm C đến điểm D có 4 cách đi.
Hỏi có bao nhiêu cách đi từ điểm A đến điểm D? Giải. Ta thấy • Từ A −→ B: n1 = 3 cách đi; • Từ B −→ C: n2 = 5 cách đi; • Từ C −→ D: n3 = 4 cách đi. Khi đó, số cách đi từ A −→ D là n = n1 · n2 · n3 = 3. Trang 8 GIẢI TÍCH TỔ HỢP 1.2 Hoán vị – Chỉnh hợp – Tổ hợp 1.1 Hoán vị không lặp Cho một tập hợp gồm n phần tử (n ≥ 1).
Mỗi kết quả của sự sắp xếp thứ tự n phần tử của tập hợp được gọi là một hoán vị của n phần tử đó. Ký hiệu và công thức tính: Pn = n! = n. Có bao nhiêu cách sắp xếp 4 sinh viên vào một cái bàn dài có 4 chỗ ngồi? Giải. Theo yêu cầu bài toán, ta có P4 = 4! = 4.2 Chỉnh hợp không lặp Cho một tập hợp gồm n phần tử (n ≥ 1).
Chỉnh hợp chập k của n phần tử (1 ≤ k ≤ n) là một nhóm k phần tử không lặp và có thứ tự lấy ra từ n phần tử đã cho. Ký hiệu và công thức tính: n! Akn =. (n − k)! Trong trường hợp k = n, ta có n! n! Ann = = = n! = Pn. Trong một giải đấu bóng đá, có các đội: A, B, C và D tham dự.
Hỏi có bao nhiêu trận đấu diễn ra? Biết rằng trong giải đấu này, hai đội bất kỳ gặp nhau hai lần theo quy định sân nhà, sân khách; sau đó tổng kết để trao giải. Ta thấy: • n = 4, k = 2; • Quan tâm đến thứ tự lấy ra. Khi đó, số trận đấu diễn ra là: 4! A24 = = 12 trận. Trong một lớp học có 45 sinh viên, giảng viên chọn ngẫu nhiên lần lượt 3 sinh viên để lập ra ban quản lý lớp bao gồm: lớp trưởng, lớp phó và thủ quỹ.
Hỏi có bao nhiêu cách lập ban quản lý lớp như trên? Giải. Ta thấy: Trang 9 GIẢI TÍCH TỔ HỢP • n = 45, k = 3; • Bài toán quan tâm đến thứ tự chọn. Khi đó, ta có số cách lập ban quản lý là: 45! A345 = = 85140 cách.3 Tổ hợp không lặp Cho một tập hợp gồm n phần tử (n ≥ 1). Tổ hợp chập k của n phần tử (1 ≤ k ≤ n) là một nhóm k phần tử không lặp và không thứ tự lấy ra từ n phần tử đã cho.
Ký hiệu và công thức tính: n! Cnk =. k!(n − k)! Trong trường hợp k = n, ta có n! Cnn = = 1. Trong bộ đề thi có một chủ đề có 25 câu hỏi thi. Hỏi có bao nhiêu cách chọn ngẫu nhiên ra 3 câu hỏi thi khác nhau của chủ đề này? Giải.
Ta thấy: • n = 25, k = 3; • Không quan tâm đến thứ tự chọn. Khi đó, ta có số cách lập đề thi thoả mãn yêu cầu bài toán: 3 25! C25 = = 2300 cách. Trong một lớp học có 45 sinh viên, giảng viên chọn ngẫu nhiên 3 sinh viên để lập ra ban quản lý lớp. Hỏi có bao nhiêu cách lập ban quản lý lớp như thế? Giải.
Ta thấy: • n = 45, k = 3; • Bài toán không quan tâm đến thứ tự chọn. Khi đó, ta có số cách lập ban quản lý thoả mãn yêu cầu bài toán: 3 45! C45 = = 14190 cách. 3!(45 − 3)! Trang 10 GIẢI TÍCH TỔ HỢP 1.3 Bài tập tự luận Bài 1. Trong tủ sách có tất cả 10 cuốn sách.
Hỏi có bao nhiêu cách sắp xếp sao cho quyển thứ nhất ở kề quyển thứ hai? Bài 2. Có bao nhiêu số tự nhiên gồm 6 chữ số khác nhau sao cho các chữ số đầu và chữ số cuối đều làm số chẵn? Bài 3. Một cuộc họp có 15 người, lúc ra về mỗi người đều bắt tay người khác một lần, riêng chủ tọa chỉ bắt tay 4 người. Hỏi có bao nhiêu cái bắt tay? Bài 4.
Một lớp có 40 sinh viên. Giảng viên chủ nhiệm muốn chọn ra một ban cán sự lớp: 1 lớp trưởng, 1 lớp phó, 1 thủ quỹ. Hỏi giảng viên chủ nhiệm có bao nhiêu cách chọn ban cán sự lớp? Bài 5. Một giảng viên có 10 cuốn sách Toán cao cấp khác nhau, trong đó có 3 cuốn Đại số tuyến tính, 4 cuốn Giải tích và 3 cuốn Xác suất.
Ông muốn lấy ra 5 cuốn và tặng cho 5 sinh viên sao cho sau khi tặng mỗi loại sách còn lại ít nhất một cuốn. Hỏi giảng viên có bao nhiêu cách chọn sách để tặng? Bài 6. Một hộp đựng 5 viên bi trắng, 5 viên bi xanh. Lấy ngẫu nhiên 3 bi từ hộp.
Hỏi (1) Có bao nhiêu cách lấy được 3 bi trắng? (2) Có bao nhiêu cách lấy được ít nhất 1 bi trắng? (3) Có bao nhiêu cách lấy được 2 bi trắng, 1 bi xanh? Bài 7. Một hộp đựng 5 viên bi trắng, 4 viên bi xanh và 6 bi vàng. Lấy ngẫu nhiên lần lượt từng bi từ hộp cho đến khi lấy được bi xanh thì dừng lại. Hỏi (1) Có bao nhiêu cách lấy đến bi thứ 2 thì dừng? (2) Có bao nhiêu cách lấy đến bi thứ 3 thì dừng? (3) Có bao nhiêu cách lấy đến bi thứ 3 thì dừng và các bi đều khác màu? Bài 8.
Năm người A, B, C, D, E sẽ phát biểu trong một hội nghị. Có bao nhiêu cách sắp xếp để: (1) Người B phát biểu sau người A. (2) Người A phát biểu xong thì đến người B phát biểu. Có 7 sinh viên được sắp xếp ngồi vào 7 chỗ đã ghi số thứ tự trên một bàn dài.
Tìm số cách xếp (1) 7 sinh viên ngồi vào bàn này. (2) 7 sinh viên ngồi vào bàn này sao cho 2 sinh viên A, B ngồi cạnh nhau. Trang 11 GIẢI TÍCH TỔ HỢP (3) 7 sinh viên ngồi vào bàn này sao cho 2 sinh viên A, B không ngồi cạnh nhau. Một hộp có 10 bi đỏ, 8 bi trắng, 6 bi vàng.
Người ta chọn ra ngẫu nhiên 6 bi từ hộp đó. Hỏi có bao nhiêu cách chọn nếu: (1) Có 2 bi vàng. (2) Có 2 bi đỏ và tối đa 2 bi vàng. (3) Có ít nhất 2 bi đỏ, ít nhất 1 bi trắng và ít nhất 1 bi vàng.4 Câu hỏi trắc nghiệm Câu 1.
Một địa điểm bán bánh trung thu có bán 8 loại bánh nhân ngọt và 6 loại bánh nhân mặn. Một người muốn mua một hộp có 4 cái khác loại nhau trong đó không có bánh nhân mặn nào, hỏi người đó có bao nhiêu cách chọn? A 420. Một hộp có 20 bi, mỗi bi là bi đỏ hoặc bi xanh, mỗi bi là bi trơn hoặc bi nhám. Biết rằng hộp có 8 bi xanh, 11 bi trơn và 2 bi đỏ nhám.
Một người lấy ngẫu nhiên hai bi ra từ hộp, hỏi có bao nhiêu cách lấy được một bi nhám và một bi trơn. Một hộp gồm có 8 chính phẩm và 4 phế phẩm. Người thứ nhất lấy từ hộp ra một sản phẩm rồi để bên ngoài, người thứ hai sau đó mới lấy ra hai sản phẩm từ hộp. Nếu người thứ nhất đã lấy được 1 chính phẩm từ hộp, thì người thứ hai có bao nhiêu cách lấy được ít nhất một chính phẩm? A 70.
Một địa điểm bán bánh trung thu có bán 8 loại bánh nhân ngọt và 6 loại bánh nhân mặn. Một người muốn mua một hộp có 4 cái khác loại nhau trong đó phải có một bánh dẻo nhân ngọt và một bánh thập cẩm nhân mặn có bán ở địa điểm trên, hỏi người đó có bao nhiêu cách chọn? A 35. Một hộp có 20 bi, mỗi bi là bi đỏ hoặc bi xanh, mỗi bi là bi trơn hoặc bi nhám. Biết rằng hộp có 8 bi xanh, 11 bi trơn và 2 bi đỏ nhám.
Một người lấy ngẫu nhiên hai bi ra từ hộp, hỏi có bao nhiêu cách lấy được một bi đỏ trơn và một bi nhám. Một địa điểm bán bánh trung thu có bán 8 loại bánh nhân ngọt và 6 loại bánh nhân mặn. Một người muốn mua một hộp có 4 cái khác loại nhau trong đó có ít nhất một cái bánh nhân mặn, hỏi người đó có bao nhiêu cách chọn? A 756. Trang 12 GIẢI TÍCH TỔ HỢP Câu 7.