Chuyên đề về Đại số tổ hợp

ĐẠI SỐ TỔ HỢP_CHÂU TRẦN DUYÊN ANH. 1 ĐẠI SỐ TỔ HỢP I. TÓM TẮT LÝ THUYẾT: 1. Qui tắc cộng : Nếu có m cách chọn cho đối tượng A và n cách chọn cho đối tượng B và nếu cách chọn của A không trùng với bất kì cách chọn nào của B thì có m + n cách chọn cho một đối tượng trong các đối tượng đã cho. Ví dụ: Có ba chữ số 1, 2, 3. Hỏi có thể lập được bao nhiêu số có hai chữ số từ ba chữ số trên? } Gọi số có hai chữ số là . Khi đó: a có 3 cách chọn từ 3 chữ số 1, 2, 3. b có 3 cách chọn từ 3 chữ số 1, 2, 3. Vậy theo qui tắc cộng ta có 3 + 3 = 6 cách thành lập số có hai chữ số từ 1,2,3 2. Qui tắc nhân: Nếu có m cách chọn cho đối tượng A, sau đó với mỗi cách chọn A lại có n cách chọn cho đối tượng B, thì có m.n cách chọn. Ví dụ: Có 18 đội bóng thi đấu và có ba huy chương vàng, bạc, đồng. Hỏi có bao nhiêu cách trao huy chương? }Huy chương vàng có thể trao cho một trong 18 đội bóng trên nên có 18 cách chọn. Huy chương bạc không thể trao cho đội đã đoạt huy chương vàng nên có 17 cách chọn. Huy chương đồng cũng không thể trao cho đội đã đoạt huy chương vàng và huy chương bạc nên có 16 cách chọn trong các đội bóng trên. Vậy theo qui tắc nhân ta có 18.17.16 =4896 cách trao huy chương. 3. Hoán vị: Cho tập hợp A gồm n phần tử ( n > 1 ). Một hoán vị n phần tử là một cách sắp thứ tự n phần tử của tập hợp A. Số các hoán vị của n phần tử là: Pn = n! = n(n – 1 )(n – 2 )3.2.1 Ví dụ: Có bao nhiêu số thự nhiên gồm 5 chữ số được thành lập các chữ số 1, 3, 5 ,7 ,9? }Các số tự nhiên gồm 5 chữ số được thành lập từ các chữ số 1, 3, 5, 7, 9 là số hoán vị của 5 phần tử. Do đó có 5! = 120 số. 4. Chỉnh hợp: Cho tập hợp A gồm n phần tử. Một chỉnh hợp chập k của n phần tử của tập hợp A () là một bộ gồm k phần tử sắp thứ tự của tập A. Chú ý: Khi k = n thì một chỉnh hợp chập k là một hoán vị của n phần tử ĐẠI SỐ TỔ HỢP_CHÂU TRẦN DUYÊN ANH. 2 Số các chỉnh hợp chập k của n phần tử là: Ví dụ : Có bao nhiêu số tự nhiên có 4 chữ số được thành lập từ các số 1, 2, 3, 4, 5, 6. }Các số tự nhiên có 4 chữ số được thành lập từ các chữ số trên là số chỉnh hợp chập 4 của 6 phần tử. Tức là có số. 5. Tổ hợp: Cho tập hợp A gồm n phần tử. Một tổ hợp chập k của n phần tử của tập hợp A (0là một tập con gồm k phần tử của tập A Số các tổ hợp chập k của n phần tử là: Ví dụ: Có bao nhiêu cách thành lập một tổ trực gồm 5 học sinh từ 10 học sinh. }Số cách thành lập tổ chính là số tổ hợp chập 5 của 6 phần tử.Tức là: cách. 6. Hệ thức giữa các : 0 < k < n) (0 < k < n) 7. Khai triển nhị thức NEWTON: (a + b)n == = Chú ý: 1. Ta chứng minh nhị thức NEWTON bắng qui nạp. 2. Khi a = b= 1 thì từ công thức nhị thức NEWTON ta suy ra: Suy ra tổng các tập con của tập A gồm n phần tử là 2n. Cần nhớ: Phân biệt chữ số, dãy số, các chữ số đôi một khác nhau.