Tài liệu Bài giảng hoán vị - chỉnh hợp - tổ hợp

Kiểm tra bài cũ Câu hỏi: Nêu quy tắc cộng, quy tắc nhân? Áp dụng thực hiện bài tập sau: Các thành phố A, B, C, D, E được nối với nhau bởi các con đường như hình vẽ sau: A B C D E Hỏi có bao nhiêu cách đi từ A đến E qua thành phố B, C, D chỉ một lần? HOÁN VỊ - CHỈNH HỢP TỔ HỢP I. Hoán vị 1.Định nghĩa Ví dụ1: Bài tập 3 (tiết trước) Có 3 học sinh A, B, C ngồi vào 3 ghế có đánh số 1, 2, 3 cố định. Hỏi có bao nhiêu cách xếp 3 người vào 3 ghế đó? Có 6 cách xếp sau: A 1 B 2 C 3 B 1 C 2 A 3 A 1 C 2 B 3 C 1 A 2 B 3 B 1 A 2 C 3 C 1 B 2 A 3 Ta thấy mỗi cách xếp là kết quả của một sự hoán đổi vị trí của 3 phần tử A, B, C. Ví dụ2: Trong 1 trận bóng đá, sau 2 hiệp phụ hai đội vẫn hòa nên phải đá luân lưu 11m. Mỗi đội chọn ra 5 cầu thủ để đá 5 quả luân lưu. Hãy nêu ra 3 cách đá phạt. Giải: Gọi tên 5 cầu thủ là 5 phần tử A, B, C, D, E. để đá luân lưu HLV phân công người đá quả thứ nhất, thứ 2, thứ 3, thứ 4, thứ 5. Có thể nêu 3 cách là: Quả số Cách 1 Cách 2 Cách 3 Cách 4 1 A A C ….. 2 B B A ….. 3 C C B ….. 4 D E D ….. 5 E D E .….. Nhận xét: Mỗi cách sắp xếp thứ tự 5 cầu thủ là một sự hoán đổi thứ tự đá của 5 phần tử là 5 cầu thủ A, B, C, D, E. Định nghĩa: Cho tập hợp A 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 A được gọi là một hoán vị của n phần tử đó. C1. Hãy liệt kê tất cả các số gồm 3 chữ số khác nhau từ các chữ số 1, 2, 3. Kết quả: Các số có 3 chữ số khác nhau lập được từ các chữ số 1, 2, 3 là: 123; 132; 213; 231; 312; 321. Ta thấy số 123 và số 132 chỉ khác nhau ở thứ tự sắp xếp thứ tự các các phần tử. Nhận xét: 2 hoán vị của n phần tử chỉ khác nhau ở thứ tự sắp xếp. 2. Số các hoán vị VD3: Có bao nhiêu cách sắp xếp 4 bạn An, Bình, Chi, Dung ngồi vào 1 bàn học có 4 chỗ? Giải: Gọi tắt tên 4 bạn là A. B, C, D. Cách 1: Liệt kê: 1.ABCD 2.ABDC 3.ACBD 4.ACDB 5.ADBC 6.ADCB 7.BACD 8.BADC 9.BCAD 10.BCDA 11.BDAC 12.BDCA 13.CABD 14.CADB 15.CBAD 16.CBDA 17.CDAB 18.CDBA 19.DACB 20.DABC 21.DBAC 22.DBCA 23.DCAB 24.DCBA Cách2: Có 4 cách chọn 1 bạn vào chỗ thứ nhất. Có 3 cách chọn 1 bạn vào chỗ thứ hai. Có 2 cách chọn 1 bạn vào chỗ thứ ba. Có 1 cách chọn 1 bạn vào chỗ thứ tư. Theo quy tắc nhân sẽ có 4.3.2.1 = 24 cách. Nếu đem cả lớp 11A5 ra xếp hàng hỏi có bao nhiêu cách xếp thứ tự? Nếu tập A có n phần tử thì sẽ có bao nhiêu cách xếp thứ tự? n phần tử có n chỗ. Chỗ thứ 1 có n cách chọn. Chỗ thứ 2 có n - 1 cách chọn. Chỗ thứ 3 có n - 2 cách chọn. …………………………………….. Chỗ thứ 10 có n – 9 cách chọn. ………………………………………. Chỗ thứ k có n – k +1 cách chọn. ………………………………………… Chỗ thứ n-1 có 2 cách chọn. Chỗ thứ n có 1 cách chọn. Vậy với n phần tử sẽ có: n.(n-1).(n-2)……(n-k+1)….2.1 cách sắp xếp (cách hoán vị). Định lý: Gọi Pn là số các hoán vị của n phần tử thì: Pn = n.(n-1).(n-2)……2.1 Chú ý: Kí hiệu n.(n-1).(n-2)…….2.1 = n! thì ta có Pn = n! (quy ước 0! = 1). C2. Trong giờ học môn GDQP 1 tiểu đội học sinh gồm 10 người xếp thành 1 hàng dọc. Hỏi có bao nhiêu cách xếp? Giải: Số cách xếp 10 người thành 1 hàng dọc = số hoán vị của 10 phần tử vậy có 10! = 3.628.800 cách xếp. II. Chỉnh hợp 1. Định nghĩa VD4. Một nhóm học sinh có 5 bạn A, B, C, D, E. Hãy kể ra một số cách phân công 3 bạn làm trực nhật: 1 bạn quét nhà, 1 bạn lau bảng, 1 bạn kê bàn ghế. Giải: Có thể có 1 số cách sau: Quét nhà Lau bảng Kê bàn ghế A C D A D C A E D ……….. ………. ………. ……….. ……….. ……… Mỗi cách lấy ra 3 phần tử từ 5 phần tử như trên gọi là một chỉnh hợp chập 3 của 5. Định nghĩa: Cho tập hợp A gồm n phần tử (n≥1). Kết quả của việc lấy ra k phần tử khác nhau từ n phần tử của tập hợp A và sắp xếp chúng theo một thứ tự nào đó được gọi là 1 chỉnh hợp chập k của n phần tử C3. Trên mặt phẳng lấy 4 điểm phân biệt A, B, C, D. Liệt kê tất cả các véc tơ khác véc tơ 0 mà có điểm đầu và điểm cuối của chúng thuộc tập hợp 4 điểm đã cho. A B C D Có 12 véc tơ sau:     AB ; BA ; AC ; CA ;     AD ; DA ; BC ; CB ;     CD; DC ; BD; DB 2. Số các chỉnh hợp VD4. Một nhóm học sinh có 5 bạn A, B, C, D, E. Hãy kể ra một số cách phân công 3 bạn làm trực nhật: 1 bạn quét nhà, 1 bạn lau bảng, 1 bạn kê bàn ghế. Giải: Chọn bạn quét nhà có 5 cách. Chọn bạn lau bảng có 4 cách. Chọn bạn kê bàn ghế có 3 cách. Theo quy tắc nhân sẽ có 5.4.3 = 60 cách chọn. Mỗi cách là 1 chỉnh hợp vậy có 60 chỉnh hợp chập 3 của 5 phần tử. Nếu tập A có n phần tử và lấy ra k phần tử rồi sắp xếp theo 1 thứ tự thì sẽ có bao nhiêu cách? Vị trí thứ 1 có n cách. Vị trí thứ 2 có n - 1 cách. Vị trí thứ 3 có n - 2 cách. ……………………………. Vị trí thứ k có n - k + 1 cách. Theo quy tắc nhân sẽ có: n.(n-1).(n-2)…..(n – k + 1) cách. Định lý: Gọi Akn là số chỉnh hợp chập k của n phần tử thì: Akn = n.(n-1).(n-2)…..(n – k + 1) Nhận xét: a) Ann = n.(n-1).(n-2)…..2.1 = Pn b) Có n! = n.(n-1).(n-2)…(n-k+1)(n-k).(n-k-1)...2.1 (n – k)! = (n-k).(n-k-1) ….. 2.1 n! = n.(n-1).(n-2)…(n-k+1)(n-k).(n-k-1)...2.1 (n – k)! (n-k).(n-k-1) ….. 2.1 = n.(n-1).(n-2)…..(n – k + 1) = Ann => Ann = n! (n  k )!