chương 1 được tham khảo từ các tài liệu [2], [4], [5]. Quy tắc cộng và quy tắc nhân Trong khoa học cũng như trong cuộc sống, chúng ta thường phải xác định số phần tử bằng cách đếm số phần tử. Vì vậy bài toán đếm số phần tử của một tập hợp xuất hiện khá phổ biến trong khoa học cũng như trong cuộc sống. Nếu số phần tử của một tập hợp không nhiều thì ta có thể đếm trực tiếp số phần tử bằng cách liệt kê.
Tuy nhiên, nếu số phần tử của một tập hợp rất lớn thì cách đếm trực tiếp là không khả thi. Vì vậy trong phần này, cung cấp cho chúng ta hai quy tắc đếm cơ bản để giải quyết bài toán đếm cho tập hợp có nhiều phần tử khi dùng cách liệt kê không khả thi. Quy tắc cộng Ví dụ 1. Một trường THPT cử một học sinh đi dự trại hè toàn quốc.
Nhà trường quyết định chọn một học sinh tiên tiến trong lớp 11A hoặc lớp 12B. Hỏi nhà trường có bao nhiêu cách chọn học sinh 4 đi dự trại hè toàn quốc, biết rằng lớp 11A có 31 học sinh tiên tiến và lớp 12B có 22 học sinh tiên tiến? Lời giải. Nhà trường có hai phương án chọn. Phương án thứ nhất là chọn một học sinh tiên tiến của lớp 11A, phương án này có 31 cách chọn.
Phương án thứ hai là chọn một học sinh tiên tiến của lớp 12B, phương án này có 22 cách chọn. Vậy nhà trường có tất cả 31 + 22 = 53 cách chọn. Ta có quy tắc đếm sau đây gọi là "quy tắc cộng". Quy tắc cộng: Giả sử một công việc có thể được thực hiện theo phương án A hoặc phương án B.
Có n cách thực hiện phương án A và có m cách thực hiện phương án B. Khi đó công việc có thể thực hiện bởi n + m cách. Quy tắc cộng cho công việc với nhiều phương án được phát biểu như sau: Quy tắc cộng tổng quát: Giả sử một công việc có thể được thực hiện theo một trong k phương án A1 , A2 ,. Có n1 cách thực hiện phương án A1 , n2 cách thực hiện phương án A2 ,.
và nk cách thực hiện phương án Ak. Khi đó công việc có thể được thực hiện bởi n1 + n2 +. Giả sử từ tỉnh A đến tỉnh B có thể đi bằng các phương tiện: ô tô, tàu hỏa, tàu thủy hoặc máy bay. Mỗi ngày có 10 chuyến ô tô, 5 chuyến tàu hỏa 3 chuyến tàu thủy và 2 chuyến máy bay.
Vậy số cách để di chuyển từ tỉnh A đến tỉnh B là bao nhiêu? Lời giải. Theo quy tắc cộng, ta có 10 + 5 + 3 + 2 = 20 cách để di chuyển từ tỉnh A đến tỉnh B. Quy tắc nhân Ví dụ 1. An muốn qua nhà Bình để cùng Bình đến chơi nhà Cường.
Từ nhà An đến nhà Bình có 4 con đường đi, từ nhà Bình đến 5 nhà Cường có 6 con đường đi. Hỏi An có bao nhiêu cách chọn đường đi qua nhà Bình đến nhà Cường? Hình 1.1: Hình minh họa cho Ví dụ 1. Với mỗi cách đi từ nhà An đến nhà Bình sẽ có 6 cách đi tiếp từ nhà Bình đến nhà Cường. Vì có 4 cách đi từ nhà An đến nhà Bình nên ta có 4.6 = 24 cách đi từ nhà An qua nhà Bình đến nhà Cường.
Ta có quy tắc đếm sau đây gọi là "quy tắc nhân". Quy tắc nhân: Giả sử một công việc nào đó bao gồm hai công đoạn A và B. Công đoạn A có thể làm theo n cách. Với mỗi cách thực hiện công đoạn A thì công đoạn B có thể làm theo m cách.
Khi đó công việc có thể thực hiện theo m. Quy tắc nhân cho công việc với nhiều công đoạn được phát biểu như sau: Quy tắc nhân tổng quát: Giả sử một công việc nào đó bao gồm k công đoạn A1 , A2 ,. Công đoạn A1 có thể thực hiện theo n1 cách, công đoạn A2 có thể thực hiện theo n2 cách ,. và công đoạn Ak có thể thực hiện theo nk cách.
Khi đó công việc có thể được thực hiện theo n1. Biển số xe của tỉnh A (nếu không kể mã số của tỉnh) có 6 kí tự, trong đó kí tự ở vị trí đầu tiên là một chữ cái (trong bảng 26 chữ cái tiếng anh), kí tự ở vị trí thứ hai là một chữ số thuộc tập {1, 2, ., 9}, mỗi kí tự ở bốn vị trí tiếp theo là một chữ số thuộc tập {0, 1, 2,. Hỏi nếu chỉ dùng một mã số tỉnh thì tỉnh A có thể làm được nhiều nhất bao nhiêu biển số xe máy khác nhau? 6 Lời giải. Ta có 26 cách chọn chữ cái được xếp ở vị trí đầu tiên.
Tương tự có 9 cách chọn chữ số cho vị trí thứ 2 và có 10 cách chọn chữ số cho mỗi vị trí trong bốn vị trí còn lại. Theo quy tắc nhân, ta có tất cả 26. Hoán vị − Chỉnh hợp − Tổ hợp Trong xác suất các khái niệm về hoán vị, chỉnh hợp, tổ hợp đóng vai trò quan trọng trong việc tính toán các phần tử trong một tập hợp ngoài hai phép đếm cơ bản. Hoán vị Định nghĩa 1.
Khi sắp xếp n phần tử này theo một thứ tự, ta được một hoán vị các phần tử của tập A (gọi tắt là một hoán vị của A). Số các hoán vị của một tập hợp có n phần tử là P (n) = n(n − 1)(n − 2). Việc sắp xếp thứ tự n phần tử của A là một công việc gồm n công đoạn. Công đoạn 1 là chọn phần tử để xếp vào vị trí thứ nhất, công đoạn 2 là chọn phần tử để xếp vào vị trí thứ hai, công đoạn 3 là chọn phần tử để xếp vào vị trí thứ ba,., công đoạn n là chọn phần tử để xếp vào vị trí thứ n.
Ở công đoạn 1 ta có thể chọn bất kì phần tử nào trong n phần tử của A nên có n cách thực hiện. Sau khi chọn xong phần tử xếp vào vị trí thứ nhất, ở công đoạn 2 ta có thể chọn bất kì phần tử nào trong n − 1 phần tử còn lại của A để xếp vào vị trí thứ hai nên có n − 1 cách thực hiện. Tiếp tục như vậy ở công đoạn 3 ta có n − 2 cách thực hiện,., và ở công đoạn thứ n (công đoạn cuối cùng) ta chỉ còn 1 cách thực hiện. Theo quy tắc nhân, ta có n(n − 1)(n − 2).1 = n! cách sắp xếp thứ tự n phần tử của tập A, tức có n! hoán vị.
Một đoàn khách du lịch dự định đến tham quan bảy địa điểm A, B, C, D, E, G và H ở thủ đô Hà Nội. Họ đi tham quan theo 7 một thứ tự nào đó, chẳng hạn B → A → C → E → D → G → H. Như vậy, mỗi cách chọn thứ tự các địa điểm tham quan là một hoán vị của tập {A, B, C, D, E, G, H}. Vậy đoàn khách có tất cả 7! = 5040 cách chọn.
(Hoán vị có lặp) 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., nk ) là số hoán vị có lặp của n phần tử gồm k loại, mà các phần tử loại i (1 ≤ i ≤ k) xuất hiện ni lần và được tính theo công thức n! P (n1 , n2 ,. Từ tập A ta lập được bao nhiêu số có bảy chữ số sao cho chữ số 1 xuất hiện 2 lần, chữ số 6 xuất hiện 2 lần và các chữ số khác xuất hiện đúng 1 lần và số này chia hết cho 5? Lời giải. Vì số có bảy chữ số được lập từ tập A chia hết cho 5 nên chữ số hàng đơn vị phải là số 5. Vì vậy bài toán trở thành tính các số có 6 chữ số được tạo ra từ tập 1; 3; 6; 9 sao cho chữ số 1 xuất hiện 2 lần, chữ số 6 xuất hiện 2 lần, chữ số 3 xuất hiện 1 lần và chữ số 9 xuất hiện 1 lần.
Theo quy tắc hoán vị lặp ta có: 6! P (2, 2, 1, 1) = = 180. Chỉnh hợp Định nghĩa 1. (Chỉnh hợp không lặp) Cho tập hợp A gồm n phần tử và số nguyên k với 1 ≤ k ≤ n. Khi lấy ra k phần tử của A và sắp xếp chúng theo một thứ tự, ta được một chỉnh hợp chập k của n phần tử của A (gọi tắt là một chỉnh hợp chập k của A).
Số các chỉnh hợp chập k của một tập hợp có n phần tử (1 ≤ k ≤ n) là n! Akn = n(n − 1)(n − 2). Việc lập một chỉnh hợp chập k của một tập hợp có n phần tử được coi như một công việc gồm k công đoạn. Công đoạn 1 là chọn phần tử xếp vào vị trí thứ nhất, công đoạn 2 là chọn phần tử xếp vào vị trí thứ hai,., công đoạn k là chọn phần tử xếp vào vị trí thứ k. Vì tập hợp có n phần tử nên công đoạn 1 có n cách thực hiện.
Sang công đoạn 2 chỉ còn n − 1 phần tử chưa chọn nên có n − 1 cách thực hiện. Tương tự, công đoạn 3 có n − 2 cách thực hiện,.và ở công đoạn cuối (công đoạn thứ k ) ta có n − k + 1 cách thực hiện. Theo quy tắc nhân, ta có n.(n − k + 1) cách lập ra một chỉnh hợp chập k. Đó cũng chính là số các chỉnh hợp chập k của một tập hợp gồm n phần tử.
Từ định nghĩa ta thấy một hoán vị của một tập hợp gồm n phần tử là một chỉnh hợp chập n của tập đó nên Ann = Pn = n!. Với 0 < k < n thì ta có thể viết n! Akn =. (Chỉnh hợp có lặp) Cho tập hợp X gồm n phần tử. Mỗi dãy có độ dài k 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 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.
Kí hiệu số chỉnh hợp có lặp chập k của n là Akn , tính bởi công thức Akn = nk. Có bao nhiêu cách chọn bốn cầu thủ khác nhau trong mười cầu thủ của đội bóng quần vợt để chơi bốn trận đấu đơn, các trận đấu là có thứ tự? Lời giải. Mỗi cách chọn có thứ tự bốn cầu thủ của đội bóng là một chỉnh hợp chập bốn của mười phần tử.