CHUYÊN ĐỀ: ĐẬI SỐ TỔ HỢP (Rất hay)

Tài liệu tham khảo về đại cương đại số tổ hợp, ôn tập môn hoá dành cho học sinh trung học phổ thông ôn thi tốt nghiệp và đại học cao đẳng.
Nội dung trích xuất từ tài liệu:
CHUYÊN ĐỀ: ĐẬI SỐ TỔ HỢP (Rất hay)CHUYÊN ĐỀ: ĐẬI SỐ TỔ HỢP Phương XuânTrịnh CHUYÊN ĐỀ ĐẠI SỐ TỔ HỢPI/ LÝ THUYẾT CƠ BẢN 1) Quy tắc cộng: Có n1 cách chọn đối tượng A1. n2 cách chọn đối tượng A2. A1 ∩ A2 = ∅⇒ Có n1 + n2 cách chọn một trong các đối tượng A1, A2. 2) Quy tắc nhân: Có n1 cách chọn đối tượng A1. Ứng với mỗi cách chọn A1, có n2 cách chọn đối tượng A2. ⇒ Có n1.n2 cách chọn dãy đối tượng A1, A2. 3) Hoán vị: −Mỗi cách sắp thứ tự n phần tử gọi là một hoán vị của n phần tử. −Số hoán vị: Pn = n!. 4) Chỉnh hợp: −Mỗi cách lấy ra k phần tử từ n phần tử (0 < k ≤ n) và sắp thứ tự củachúng gọi là một chỉnh hợp chập k của n phần tử. n! −Số các chỉnh hợp: A n = (n − k)! k 5) Tổ hợp: −Mỗi cách lấy ra k phần tử từ n phần tử (0 ≤ k ≤ n) gọi là một tổ hợpchập k của n phần tử. n! −Số các tổ hợp: Cn = k!(n − k)! k −Hai tính chất Ck = Cn −k n n k −1 Cn −1 + C k −1 = Ck n n 6) Nhị thức Newton n (a + b) n = ∑ C k a n − k b k n k =0 = C0 a n + C1 a n −1b + ... + C n b n n n n k n−k k −Số hạng tổng quát (Số hạng thứ k + 1): Tk +1 = Cn a b −Đặc biệt: (1 + x) = Cn + xCn + x Cn + ... + x Cn n 0 1 2 2 n nTổ Toán 1 Trương THPT Lương TàiCHUYÊN ĐỀ: ĐẬI SỐ TỔ HỢP Phương XuânTrịnhII / MỘT SỐ VÍ DỤ 1. Bài toán đếm. 1.1 Đếm các số tự nhiênđược thành lập.Ví dụ 1.Từ các chữ số 1, 2, 3, 4, 5, 6, 7 lập được bao nhiêu số tự nhiên gồm 5 chữ sốsao cho a) Các chứ số đều khác nhau. b) Chữ số đầu tiên là 3. c)Các chữ số khác nhau và không tận cùng bằng chữ số 4. Giải a) Mỗi số có 5 chữ số khác nhau được thành lập tương ứng với một chỉnh hợp chập 5 của 7 phần tử ⇒ Có A 7 = 2520 số 5 b) Gọi số cần thiết lập là abcde Chữ số đàu tiên là 3 ⇒ a có 1 cách chọn b, c, d, e đều có 7 cách chọn ⇒ Có 1.7.7.7.7 = 2401 số. c) Gọi số cần thiết lập là abcde Chữ số cuối cùng khác 4 ⇒ e có 6 cách chọn (trừ số 4) a có 6 cách chọn b có 5 cách chọn c có 4 cách chọn d có 3 cách chọn ⇒ Có 6.6.5.4.3 = 2160 số.Ví dụ 2.(ĐH An ninh 97)Từ bảy chữ số 0, 1, 2, 3, 4, 5, 6 thành lập được bao nhiêu số chẵn có 5 chữ sốkhác nhau Giải Gói số cần thiết lập là abcde Xét hai trường hợp+ Trường hợp 1: Chọn e = 0 ⇒ e có 1 cách chọn Khi đó a có 6 cách chọn b có 5 cách chọn c có 4 cách chọn d có 3 cách chọn⇒ Có 6.5.4.3 = 360 số.+ Trường hợp 2: Chọn e ∈ { 2, 4, 6 } ⇒ e có 3 cách chọnKhi đó a có 5 cách chọn trừ số 0 và e b có 5 cách chọn c có 4 cách chọnTổ Toán 2 Trương THPT Lương TàiCHUYÊN ĐỀ: ĐẬI SỐ TỔ HỢP Phương XuânTrịnh d có 3 cách chọn⇒ Có 3.5.5.4.3 = 900 sốVậy có 360 + 900 = 1260 số Ví dụ 3. Từ các chữ số 1, 2, 3, 4, 5, 6, 7 lập được bao nhiêu số có 4 chữ số sao cho số tạo thành gồm các chữ số khác nhau và nhất thiết có chữ số 5. GiảiCách 1: 3Thành lập số có 3 chữ số khác nhau và không có mặt chữ số 5 ⇒ Có A 6 = 120sốVới mỗi số vừa thành lập có 4 vị trí để xen số 5 tạo thành số có 4 chữ số khácnhau và có mặt chữ số 5.⇒ Có 120.4 = 480 số.Cách 2: −Số cần tìm có 1 trong bốn dạng 5bcd, a5bc, ab5d, abc5 −Mỗi dạng có 120 số ⇒ có 480 số Ví dụ 4: Có bao nhiêu số tự nhiên gồm 2008 chữ số sao cho tổng các chữ số bằng 3. GiảiXét các trường hợp+ Trườnghợp 1: Số tạo thành gồm 1 chữ số 3 và 2007 chữ số 0⇒ Chỉ có 1 số 3000…000 (2007 chữ số 0)+ Trường hợp 2: Số tạo thành gồm 1 chữ số 1, 1 chữ số 2 và 2006 chữ số 0Chọn chữ số đầu tiên có 2 cách chọn số 1 hoặc 2Chữ số còn lại có 2007 vị trí để đặt, còn các vị trí khác đặt số 0⇒ Có 2.2007 = 4014 số+ Trường hợp 3: Số tạo thành gồm 3 chữ số 1 và 2005 chữ số 0Chọn chữ số đầu tiên là 1 2Chọn 2 trong 2007 vị trí để đặt chữ số 1 ⇒ có C2007 = 2007.1003 = 2013021Vậy có 1 + 4014 + 2013021 = 2017036 số Ví dụ 5(ĐHQG TPHCM 2001) Có bao nhiêu số tự nhiên gồm bảy chữ số biết rằng chữ số 2 có mặt đúng hai lần, chữ số ba có mặt đúng ba lần, các chữ số còn lại có mặt không quá một lần. Giải+ Coi một dãy gồm 7 chữ số tương ứng với một số gồm 7 chữ số (Kể cả bắtđầu bằng 0). Khi đó ta thành lập số bằng cách xếp các chữ số vào 7 vị tríTổ Toán 3 Trương THPT Lương TàiCHUYÊN ĐỀ: ĐẬI SỐ TỔ HỢP Phương XuânTrịnh 2 Chọn 2 trong 7 vị trí để xếp chữ số 2: có C7 cách Chọn 3 trong 5 vị trí còn lại để xếp chữ số 3: có C3 cách 5 ...