Tài liệu Các bài giảng về tổ hợp

PHẠM HỒNG PHONG - ĐẶNG VĂN HIẾU ĐẠI SỐ & GIẢI TÍCH 11 TỔ HỢP KHỞI THẢO THÁNG 5 – 2014 Khách có kẻ: Giương buồm giong gió chơi vơi, Lướt bể chơi trăng mải miết … (Bạch Đằng giang phú – Trương Hán Siêu) Mục lục Chủ đề 1. Hai quy tắc đếm cơ bản .......................................................................1 Chủ đề 2. Ba khái niệm cơ bản của tổ hợp ..........................................................7 §1. Phương trình, bất phương trình và hệ liên quan đến các số chỉnh hợp, tổ hợp, hoán vị ........... 8 §2. Ứng dụng ba khái niệm cơ bản vào bài toán đếm ..................................................................... 14 Chủ đề 3. Công thức khai triển nhị thức Niu-tơn .............................................23 §1. Chứng minh đẳng thức .............................................................................................................. 24 §2. Hệ số của một lũy thừa trong khai triển.................................................................................... 29 Khách có kẻ: Giương buồm giong gió chơi vơi, Lướt bể chơi trăng mải miết … (Bạch Đằng giang phú – Trương Hán Siêu) Chủ đề 1. Hai quy tắc đếm cơ bản A. TÓM TẮT LÝ THUYẾT 1. Quy tắc cộng Giả sử để thực hiện công việc A , ta phải thực hiện một trong k công việc: A1 , A2 , ..., Ak . Nếu thực hiện công việc Ai có ni cách ( i  1, , n ), thì thực hiện công việc A có k n   ni  n1  n2  nk (cách). i 1 Phương án A1 Phương án A2 n1 cách n2 cách . . . Công việc A: n1+n2+...+nk cách Phương án Ak nk cách Hình 1: Quy tắc cộng 2. Quy tắc cộng Giả sử để thực hiện công việc A , ta phải lần lượt thực hiện k công việc: A1 , A2 , ..., Ak . Nếu thực hiện công việc Ai có ni cách ( i  1, , n ), thì thực hiện công việc A , ta có k n   ni  n1 .n2 ..nk (cách). i 1 Công việc A1 Công việc A2 n1 cách n2 cách ... Công việc Ak Công việc A: nk cách n1n2...nk cách Hình 2: Quy tắc nhân B. CÁC VÍ DỤ 1 Ví dụ 1. Bạn Kiên có 5 cuốn sách Văn học khác nhau và 6 cuốn sách Lịch sử khác nhau. Hỏi Kiên có bao nhiêu cách chọn một cuốn sách để tặng sinh nhật một người bạn. Giải. Để chọn một cuốn sách, Kiên có hai phương án:  Phương án 1: Chọn sách Văn học. Vì Kiên có 5 cuốn sách Văn học khác nhau nên số cách thực hiện phương án này là 5 (cách)  Phương án 2: Chọn sách Lịch Sử. Vì Kiên có 6 cuốn sách Lịch sử khác nhau nên số cách thực hiện phương án này là 6 (cách) Theo quy tắc cộng, số cách chọn sách của Kiên là: 5  6  11 (cách). Ví dụ 2. Từ tỉnh A đến tỉnh B có 3 đường đi, từ tỉnh B đến tỉnh C có 4 đường đi. Hỏi có bao nhiêu cách đi từ tỉnh A đến tỉnh C biết rằng muốn đi từ tỉnh A đến tỉnh C bắt buộc phải đi qua tỉnh B . Giải. Để đi từ tỉnh A đến tỉnh C ta phải thực hiện hai bước.  Bước 1: Đi từ tỉnh A đến tỉnh B . Vì có 3 đường đi từ A đến B nên số cách thực hiện bước này là 3 (cách).  Bước 1: Đi từ tỉnh B đến tỉnh C . Vì có 4 đường đi từ B đến C nên số cách thực hiện bước này là 4 (cách). Theo quy tắc nhân, số cách đi từ A đến C là 3  4  12 (cách). Ví dụ 3. Có thể lập được bao nhiêu số có năm chữ số đôi một khác nhau từ các chữ số từ 0 đến 9. Giải. Giả sử số cần lập là A  a1a2  a5 . Để lập số A , ta phải lần lượt chọn a1 , a2 , ..., a5 sao cho a1  0 và a1 , a2 , ..., a5 đôi một khác nhau.  Vì a1  0 nên có 9 cách chọn a1 .  Vì a2 có thể bằng 0 , tuy nhiên a2  a1 nên có 9 cách chọn a2 .  Lập luận hoàn toàn tương tự, ta có số cách chọn a3 , a4 , a5 lần lượt là: 8 , 7 , 6 cách. Vậy theo quy tắc nhân thì số cách lập số A là 9.9.8.7.6  27216 (cách). Ví dụ 4. Có thể lập được bao nhiêu số có năm chữ số đôi một khác nhau chia hết cho 5 từ các chữ số từ 0 đến 9 . Giải. Giả sử số cần lập là A  a1a2  a5 . Để lập số A ta có hai phương án như sau với chú ý rằng a5 phải bằng 0 hoặc 5 :  Phương án 1: Nếu chọn a1  5 thì a5  0 . Số cách chọn a2 , a3 , a4 lần lượt là: 8 , 7 , 6 cách. Theo quy tắc nhân thì phương án này có số cách thực hiện là: 8.7.6  336 (cách).  Phương án 2: Nếu Chọn a1  5 thì có 8 cách chọn a1 , 2 cách chọn a5 ( a5 có thể bằng 0 hoặc 5 ). Số cách chọn a2 , a3 , a4 lần lượt là: 8 , 7 , 6 cách. Theo quy tắc nhân thì phương án này có số cách thực hiện là: 8.2.8.7.6  5376 cách. Áp dụng quy tắc cộng ta có số cách lập số A là 336  5376  5712 cách. 2 Nhận xét. Việc lập số A trong Ví dụ 4 được chia thành hai phương án vì việc a1 có bằng 5 hay khác 5 có ảnh hưởng đến số cách chọn a5 . Ví dụ 5. Có thể lập được bao nhiêu số có năm chữ số đôi một khác nhau từ các chữ số từ 0 đến 9 biết rằng số này có đúng hai chữ số 1 và các chữ số còn lại đôi một khác nhau. Giải. Giả sử số cần lập là A  a1a2 ...a5 . Để lập số A ta có hai phương án như sau (về cách chọn a1 ):  Phương án 1: a1  1 .  Chọn thêm một vị trí nữa cho cho chữ số 1 có 4 cách.  Lần lượt chọn chữ số cho ba vị còn lại có số cách lần lượt là 9 , 8 , 7 cách. Do đó, số cách lập số A theo phương án này là 1.4.9.8.7  2016 cách.  Phương án 2: a1  1 .  Có 8 cách chọn a1 .  Có 6 cách chọn hai vị trí cho chữ số 1 : chọn a2 và a3 , a2 và a4 , a2 và a5 , a3 và a4 , a3 và a5 , a4 và a5 .  Lần lượt chọn chữ số cho hai vị còn lại có số cách lần lượt là 8 , 7 cách. Do đó, số cách lập số A theo phương án này là 8.6.8.7  2688 cách. Vậy số cách lập số A là 2016  2688  4704 cách. Ví dụ 6. Từ các chữ số 0 , 1 , 2 , 3 , 4 , 5 có thể lập được bao nhiêu số tự nhiên mà mỗi số có 6 chữ số đôi một khác nhau và chữ số 2 đứng cạnh chữ số 3 . Giải. Giả sử số cần lập là A  a1a2 ...a5 . Để lập số A ta có hai phương án như sau:  Phương án 1: xếp 2 và 3 vào hai vị trí đầu tiên có n1  2 cách ( a1  2 , a2  3 hoặc ngược lại). Số cách chọn chữ số cho các vị trí a3 , a4 , a5 lần lượt là 4 , 3 , 2 cách. Do đó, số cách thực hiện phương án này là 4  3  2  24 (cách).  Phương án 2: xếp 2 và 3 vào hai vị trí khác vị trí a1 . Có thể xếp 2 và 3 vào các vị trí: a 2 và a3 , a 3 và a4 , a 4 và a5 , suy ra số cách xếp 2 và 3 theo phương án này là 2.3  6 cách. Số cách chọn a1 là m2  3 cách. Chọn chữ số cho 2 vị trí còn lại có số cách lần lượt là 3 , 2 . Vậy số các thực hiện phương án này là 6  3  3  2  108 (cách) Vậy số các số thỏa mãn yêu cầu bài toán là: 24  108  132 . Ví dụ 7. Có 6 quả cầu xanh được đánh số từ 1 đến 6 , 5 quả cầu đỏ được đánh số từ 1 đến 5 và 4 quả cầu vàng được đánh số từ 1 đến 4 . Hỏi có bao nhiêu cách chọn ra 3 quả cầu vừa khác mầu vừa khác số. Giải. Để chọn được 3 quả cầu thỏa mãn yêu cầu bài toán, ta lần lượt làm như sau:  Bước 1: Chọn quả cầu vàng có n1  4 cách. 3  Bước 2: Chọn quả cầu đỏ: vì không được chọn quả cầu đỏ có số trùng với số của quả cầu vàng đã chọn ở bước 1 nên số cách chọn quả cầu đỏ là n2  4 .  Bước 3: Chọn quả cầu xanh: vì không được chọn quả cầu xanh có số trùng với số của các quả cầu đã chọn ở bước 1 và bước nên số cách chọn quả cầu đỏ là n3  4 . Vậy số cách chọn ra 3 quả cầu vừa khác mầu vừa khác số là: n1 .n2 .n3  64 . C. BÀI TẬP Bài 1. Giả sử bạn muốn mua áo sơ mi cỡ 39 hoặc 40. Áo cỡ 39 có 5 màu khác nhau, áo cỡ 40 có 4 màu khác nhau. Hỏi a) Có bao nhiêu sự lựa chọn một chiếc áo? b) Có bao nhiêu sự lựa chọn hai chiếc áo khác cỡ? ĐS: a) 9 ; b) 20 . Bài 2. Giả sử bạn muốn mua áo sơ mi cỡ 39 hoặc 40. Áo cỡ 39 có 4 màu là trắng, đỏ, xanh, vàng; áo cỡ 40 có 3 màu là trắng, đỏ, tím. Hỏi a) Có bao nhiêu sự lựa chọn một chiếc áo? b) Có bao nhiêu sự lựa chọn hai chiếc áo khác cỡ? c) Có bao nhiêu sự lựa chọn hai chiếc áo khác cả cỡ và màu? ĐS: a) 7 ; b) 12 ; c) 10. Bài 3. Có bao nhiêu số tự nhiên có năm chữ số sao cho 3 chữ số đầu tiên khác nhau và các chữ số cách đều chữ số đứng giữa thì giống nhau. ĐS: 648. Bài 4. Từ cách chữ số 1 , 5 , 6 , 7 có thể lập được bao nhiêu số tự nhiên a) Có bốn chữ số. b) Có bốn chữ số đôi một khác nhau. ĐS: a) 256; b) 24. Bài 5. Từ các chữ số 1 , 5 , 6 , 7 có thể lập được bao nhiêu số có 4 chữ số tự và lớn hơn 4000 nếu a) Các chữ số không nhất thiết khác nhau. b) Các chữ số đôi một khác nhau. ĐS: a) 64 ; b) 6 . Bài 6. Có bao nhiêu số có 3 chữ số được tạo thành từ các chữ số 2 , 3 , 4 , 5 , 6 nếu a) Các chữ số của nó không nhất thiết khác nhau. b) Các chữ số của nó đôi một khác nhau. c) Các chữ số của nó hoàn toàn giống nhau. ĐS: a) 125 ; b) 60 ; c) 5 . Bài 7. Từ cách chữ số 0 , 1 , 2 , 3 , 4 , 5 có thể lập được bao nhiêu số tự nhiên a) Có bốn chữ số. b) Có bốn chữ cố đôi một khác nhau. c) Có bốn chữ số đôi một khác nhau và chia hết cho 5. ĐS: a) 1080 ; b) 300 ; c) 108 . 4 Bài 8. Có bao nhiêu số tự nhiên lẻ trong khoảng  2000;3000  có thể tạo nên từ các chữ số 1 , 2 , 3 , 4 , 5 , 6 nếu a) Các chữ số của nó không nhất thiết khác nhau. b) Các chữ số của nó đôi một khác nhau. ĐS: a) 125 ; b) 60 . Bài 9. Khi gieo đồng thời ba con xúc xắc khác nhau có bao nhiêu khả năng mà tổng số chấm xuất hiện trên ba mặt của ba con súc sắc lớn hơn 9 . ĐS: 6 . Bài 10. Có 4 hành khách bước lên một đoàn tàu có 4 toa. Hỏi a) Có bao nhiêu trường hợp có thể xảy ra về cách chọn toa của 4 hành khách. b) Có bao nhiêu trường hợp mà mỗi toa có 1 người lên. c) Có bao nhiêu trường hợp mà một toa có 3 người lên, một toa có 1 người lên và hai toa còn lại không có ai lên. ĐS: a) 256 ; b) 24 ; c) 36 . 5 Chủ đề 2. Ba khái niệm cơ bản của tổ hợp 1. Hoán vị  Cho tập hợp A có n phần tử ( n  1 ). Mỗi cách sắp xếp n phần tử của nó theo một thứ tự được gọi là một hoán vị của n phần tử của A .  Số các hoán vị của tập hợp có n phần tử là Pn  n !  1.2.3. ... .n . Với quy ước 0!  1 , ta có thể định nghĩa P0  1 . 2. Chỉnh hợp  Cho tập hợp A có n phần tử ( n  1 ) và số nguyên k với 1  k  n . Mỗi cách lấy ra k phần tử của A và sắp xếp chúng theo một thứ tự được gọi là một chỉnh hợp chập k của n phần tử của A .  Số các chỉnh hợp chập k của tập hợp có n phần là Ank  n!  n  n  1 n  2  ...  n  k  1 .  n  k ! (1) Ta thấy công thức (1) cũng có nghĩa khi k  0 nên, để cho tiện, ta định nghĩa số Ank với k , n nguyên và 0  k  n . 3. Tổ hợp  Cho tập hợp A có n phần tử ( n  1 ) và số nguyên k với 1  k  n . Mỗi cách lấy ra k phần tử của A được gọi là một tổ hợp chập k của n phần tử của A .  Số các tổ hợp chập k của tập hợp có n phần tử là: Cnk  n  n  1 n  2  ...  n  k  1 Ank n!   . k ! k ! n  k  ! k! (2) Ta thấy công thức (2) cũng có nghĩa khi k  0 nên, để cho tiện, ta định nghĩa số Cnk với k , n nguyên và 0  k  n .  Hai tính chất cơ bản của số tổ hợp:  Cnk  Cnn  k . (công thức phần bù)  Cnk1  Cnk  Cnk 1 (công thức Pa-xcan). 7 §1. Phương trình, bất phương trình và hệ liên quan đến các số chỉnh hợp, tổ hợp, hoán vị A. TÓM TẮT LÝ THUYẾT Khi giải phương trình, bất phương trình và hệ liên quan đến các số chỉnh hợp tổ hợp, hoán vị, ta cần chú ý:  Pn  n !  1 2   n có nghĩa khi và chỉ khi n   .  Ank  n! n! và Cnk  có nghĩa khi và chỉ khi: n   và 0  k  n . k ! n  k  !  n  k ! B. CÁC VÍ DỤ Ví dụ 1. Chứng minh các đẳng thức sau n a) k 1 1 với n , n  2 .  1 n! k 2 k !  3 b)  Pn  CnnC2nnC3nn   3n  ! với n   . n c) 1 A k 2 2 k  n 1 với n   ; n  2 . n Giải. a) Ta có  1 k 1 n  1 1 1 1   1 1 1 1                  1 (ĐPCM).  k  1 ! k ! 1! 2! 2! 3! n  1 ! n ! n !         k 2 k ! k 2         n b) Ta có  Pn  3 3 Cnn C2nn C3nn   n !   n ! 3  2n ! .  3n ! n! . n ! n  n  ! n ! 2n  n  ! n ! 3n  n ! n !  2n  !  3n  ! . .   3n  ! (ĐPCM). n !0! n !n ! n ! 2n  ! c) Với mọi k nguyên, 2  k  n ta có k! 1 1 1 1 Ak2   k  k  1  2    . Ak k  k  1 k  1 k  k  2! Do đó n n 1 1  1 1   1 1  1  1  1                    2 k  1 2   2 3   n 1 n  k  2 Ak k 2  k  1  1 1 n 1  (ĐPCM). n n 8 Ví dụ 2. Giải các phương trình, bất phương trình và hệ sau: a) [TN2007] Cn4  Cn5  3Cn61 . b) [TN2005] Cnn21  Cnn 2  5 2 An . 2  C xy1 6 (1)  y 1  5  Cx c) [TN2003]  y 1 .  C x  5 (2)  Cxy 1 2 Giải. a) Điều kiện: n là số nguyên và n  5 . Áp dụng hằng đẳng thức Pa-xcan ta có Cn4  Cn5  Cn51 . Phương trình đã cho tương đương với  n  1!  3  n  1!  1  1  n  6 (thỏa mãn). Cn51  3Cn61  5! n  4  ! 6! n  5 ! n4 2 b) Điều kiện: n là số nguyên và n  2 . Áp dụng hằng đẳng thức Pa-xcan ta có Cnn21  Cnn 2  Cnn3 . Bất phương trình đã cho tương đương với  n  3!  5 n !   n  1 n  2  n  3  5 5 Cnn3  An2  2 n !3! 2  n  2 ! 3n  n  1   n  1 n  2  n  3  15n  n  1  n3  9n 2  26n  6  0 . (1) Với mọi n  2 , áp dụng bất đẳng thức Cô-si cho 2 số dương n3 và 26n 2 , ta có n3  26n  2 n3 .26n  2 26n 2  2.5n 2  10n 2 . Do đó VT (1)  10n 2  9n 2  6  n 2  6  0  (1) nhận mọi n  2 là nghiệm  bất phương trình đã cho nhận mọi n  2 là nghiệm. c) Điều kiện: x , y nguyên, 1  y  x  1 . Ta có  x  1! .  y  1! x  y  1!  6   x  1 y  1  6 . y ! x  y  1 ! x! 5  x  y  x  y  1 5  y  1! x  y  1!  5   x  y  x  y  1  5 x! (2)  . x! 2 y  y  1 2  y  1! x  y  1! (1)  (3) . (4) Nhân từng vế (3) và (4) ta có x 1  3  x  3 y 1 . y (5) Thay (5) vào (4) ta được 9 2 y  2 y  1 y  y  1  2 y  2 y  1 5 5    3 y2  9 y  0  y  3 2 y  y  1 2 Thay y  3 vào (5) ta được x  8 . Ta thấy cặp giá trị  x; y    8;3 x  8 , y  3 thỏa mãn điều kiện để hệ có nghĩa. Vậy hệ có nghiệm duy nhất  x; y    8;3 . Ví dụ 3. [ĐHD05] Tính giá trị của biểu thức M  An41  3 An3 biết rằng  n  1! Cn21  2Cn2 2  2Cn23  Cn2 4  149 . (1) Giải. Điều kiện: n nguyên, n  3 . Ta có  n  1!  2.  n  2 !  2.  n  3!   n  4 ! VT (1)  2! n  1 ! 2!n ! 2! n  1! 2! n  2 !  n  n  1 2   n  1 n  2    n  2  n  3   n  3 n  4  2 1 6n 2  24n  28   2  3n 2  12n  14 .  Do đó  x  5  thoûa maõn  (1)  3n 2  12n  14  149  3n 2  12n  135  0   .  x  9  loaïi  Ví dụ 4. Chứng minh các đẳng thức sau a) Cnk  3Cnk 1  3Cnk 2  Cnk 3  Cnk3 , với k , n là các số nguyên dương thỏa mãn 3  k  n . b) Cnk  Cnk11  Cnk21  ...  Ckk 1  Ckk11 , với k , n là các số nguyên dương thỏa mãn k  n . Giải. a) Áp dụng liên tiếp hằng đẳng thức Pa-xcan, ta có VP  Cnk 2  Cnk21   Cnk1  Cnk11    Cnk11  Cnk12   Cnk1  2Cnk11  Cnk12   Cnk  Cnk 1   2  Cnk 1  Cnk 2    Cnk  2  Cnk 3   Cnk  3Cnk 1  3Cnk 2  Cnk 3  VT (1) (điều phải chứng minh). a) Áp dụng hằng đẳng thức Pa-xcan, ta có Cnk  Cnk1  Cnk11 Cnk1  Cnk 2  Cnk21 10 C k k 1   Ckk  Ckk 1 . Cộng từng vế các đẳng thức trên, giản ước Cnk1  ...  Ckk1 ở hai vế, ta được Cnk  Cnk11  Cnk21  ...  Ckk 1  Ckk  Cnk11  Cnk21  ...  Cnk21  Ckk11 (chú ý: Ckk  1  Ckk11 ). Ví dụ 5. Chứng minh 1 1 1 1     2 , 1! 2! 3! n! (1) với n  * . Giải. Ta có (1)  1 1 1    1 . 2! 3! n! Lại có 1 1 2 1 1 1     , 2! 1.2 1.2 1 2 1 1 3 2 1 1     , 3! 2.3 2.3 2 3 1 1 43 1 1     , 4! 3.4 3.4 3 4  n   n  1 1 1 1 1     . n !  n  1 n  n  1 n n  1 n Cộng từng vế n  1 đẳng thức, bất đẳng thức nói trên, ta thu được 1 1 1   1 1   1 1   1 VT (2)                   1 2   2 3   3 4   n 1 n  1  1   1 (ĐPCM). n Ví dụ 6. Cho n  * . Tìm max C2kn  . k  0;2 n Giải.Với k  0; 2n  1 , xét tỷ số k ! 2n  k  ! 2n  k C2kn1  2n  ! T k  .  . C2 n  k  1 ! 2n  k  1 ! k 1  2n ! Ta có 2n  k 1  1  k  n   k  0; n  1 . k 1 2 Chú ý rằng dấu “  ” không xảy ra. Thay từng giá trị của k vào T ta được T 1 C21n  C20n    C2nn1  C2nn  C2nn1    C22nn 1  C22nn . 11 Vậy max C2kn   C2nn . k  0;2 n Ví dụ 7. [ĐHB06] Cho tập hợp A gồm n phần tử ( n  4 ). Biết rằng số tập con gồm 4 phần tử của A bằng 20 lần số tập con gồm 2 phần tử của A . Tìm k  1; 2;...; n sao cho số tập con gồm k phần tử của A lớn nhất. Giải. Mỗi một cách chọn k phần tử từ tập A cho ta một tập con gồm gồm k phần tử của A  số tập con gồm k phần tử của A là Cnk . Số tập con gồm 4 phần tử của A bằng 20 lần số tập con gồm 2 phần tử của A nghĩa là Cn4  20Cn2   n! n!  20 4! n  4  ! 2! n  2 !  n  18  thoûa maõn  1 20   n 2  5n  234  0   . 12  n  3 n  2  n   13 loaï i    Vậy số phần tử của A là 18 . Với k  1;17 , xét tỷ số T k !18  k ! 18  k C18k 1 18!  .  . k C18  k  1 !17  k ! 18! k 1 Ta có T 1 18  k 17 1 k   k  1;8 . k 1 2 Chú ý rằng dấu “  ” không xảy ra. Thay từng giá trị của k vào T ta được 17 C181  C182  ...  C188  C189  C1810  ...  C18  C1818 . Do đó C18k  max C18k   k  9 . Vậy số tập con gồm 9 phần tử của A là tập con có số tập con k 1;18 lớn nhất. C. BÀI TẬP Baøi 1. Chứng minh a) Pn  Pn 1   n  1 Pn 1 với n  * . b) Cnk  c) nCnk11 với k , n  * , k  n . k n2 1 1   với n  * , n  2 . n !  n  1 !  n  2 ! d) [ĐHB08] n 1  1 1  1  k  k 1   k với k , n   , 0  k  n . n  2  Cn 1 Cn 1  Cn e) Annk2  Annk1  k 2 Ann k với n , k  * , k  2 . f) Pk An21 An23 An25  nk ! An55 với n  * . 12 g) Pn  1  P1  2 P2  3P3  ...   n  1 Pn 1 với n   ; n  2 . h) Cn1  2 i) Cn1  2 n  n  1 Cn2 Cn3 Cnn với n  * .  3  n  2 2 n 1 Cn Cn Cn 2 Cn2 Cn3 Cnn  3  ...  n  Cn21 với n  * . Cn1 Cn2 Cnn 1 j) 1.1! 2.2! 3.3! ...  n.n !   n  1! với n  * . n k) k 1  1 với n  * . k 1 Pk  Bài 1. Chứng minh a) Cnk44  Cnk  4Cnk 1  6Cnk  2  4Cnk 3  Cnk  4 , với k , n   , 0  k  n  4 ; b) Cnn 1  Cnn11  Cnn12    C2nn11  C2nn với n  * . Bài 2. Giải các phương trình, bất phương trình, hệ phương trình sau: n !  n  1 ! 1 a)  . ĐS: 2 , 3 .  n  1! 6 b)  n  1!  72 .  n  1! ĐS: 8 . c)  n  n  1!  n  1!  1  5 .    5. n  2  n  1  n  3!4! 12  n  3 n  4 !2!  ĐS: 5 , 6 . d) An3  20n . ĐS: 6 . e) An5  18 An42 . ĐS: 10 . f) Pn 3  72 An5 Pn 5 . ĐS: 7 . An4 4 15 g)  .  n  2 !  n  1! ĐS: 3 , 4 , 5 . h) Axy 1 : Axy1 : C xy1  21: 60 :10 . ĐS:  x; y    7;3 . i) 2 Ayx  5C yx  90 .  x x 5 Ay  2C y  80 Bài 3. Cho n  * . Tìm max C2kn 1 . k  0;2 n 1 ĐS:  x; y    2;5 . ĐS: max C2kn 1  C2nn 1  C2nn11 . k  0;2 n 1 13 §2. Ứng dụng ba khái niệm cơ bản vào bài toán đếm Sau đây ta sẽ áp dụng ba khái niệm cơ bản vào bài toán đếm (tất nhiên vẫn sử dụng các quy tắc đếm). Nhờ đó, việc đếm được thực hiện đơn giản và chính xác hơn. A. CÁC VÍ DỤ Ví dụ 1. Bạn Ngọc có 12 cuốn sách khác nhau, trong đó có 2 cuốn sách Toán, 4 cuốn sách Văn và 6 cuốn sách Anh. Hỏi có bao nhiêu cách xếp tất cả các cuốn sách lên một kệ sách dài, nếu các cuốn sách cùng môn được xếp kề nhau? Giải.  Bước 1. Trước hết ta tính số cách xếp thứ tự từng loại sách. Vì có 3 loại sách nên số các sắp thứ tự loại sách là P3  3!  6 (cách).  Bước 2. Xếp sách vào kệ: ứng với mỗi phương án sắp xếp 3 loại sách, ta lại có  n2  P2  2! cách xếp 2 cuốn sách Toán,  n3  P4  4! cách xếp 4 cuốn sách Văn,  n4  P6  6! cách xếp 6 cuốn sách Anh. Như vậy, ứng với mỗi phương án sắp xếp 3 loại sách, ta lại có số cách sắp xếp 12 cuốn sách là 2!4!6!  34560 (cách). Tóm lại số các xếp thỏa mãn yêu cầu là 6  34560  207360 (cách). Ví dụ 2. Một bàn dài có hai dãy ghế đối diện nhau, mỗi dãy có 6 ghế. Người ta muốn xếp chỗ ngồi cho 6 học sinh trường A và 6 học sinh trường B vào bàn nói trên. Hỏi có bao nhiêu cách xếp trong mỗi trường hợp sau. a) Bất cứ 2 học sinh nào ngồi cạnh nhau hoặc đối diện nhau thì khác trường với nhau. b) Bất cứ 2 học sinh nào ngồi đối diện nhau thì khác trường với nhau. Giải. a)  Bước 1. Trước tiên ta xác định trong 12 vị trí, vị trí nào của học sinh trường A, vị trí nào của học sinh trường B. Rõ ràng để đảm bảo bất cứ 2 học sinh nào ngồi cạnh nhau hoặc đối diện nhau thì khác trường với nhau ta có các xếp như sau. Cách 1 Cách 2 A B A B A B B A B A B A B A B A B A A B A B A B  Bước 2. Ứng với mỗi cách đã xác định ở bước 1, ta xếp 12 học sinh vào chỗ.  Xếp 6 học sinh trường A vào 6 chỗ: có 6! cách.  Xếp 6 học sinh trường B vào 6 chỗ còn lại: có 6! cách. Theo quy tắc nhân thì số cách xếp thỏa mãn yêu cầu bài toán là 2  6!6!  1036800 (cách). 14 Ví dụ 3. Có bao nhiêu cách xếp 5 bạn nam và 4 bạn nữ thành một hàng ngang sao cho không có hai bạn nữ nào đứng cạnh nhau? Giải.   Bước 1. Xếp 5 bạn nam thành hàng ngang. Ta thấy có 5! cách làm như vậy. Bước 2. Xếp 4 bạn nữ. Ta thấy để việc xếp thỏa mãn yêu cầu bài toán thì phải xếp 4 bạn vào 6 vị trí như hình vẽ. (1) Nam (2) Nam (3) Nam (4) Nam (5) Nam (6) Như vậy, ứng với mỗi cách xếp 5 bạn nam có A64 cách xếp 4 bạn nữ. Tóm lại, số cách xếp là 5! A64  43200 (cách). Ví dụ 4. [ĐHB02] Cho đa giác đều A1 A2 ... An ( n  2 , n nguyên). Biết số tam giác có các đỉnh là 3 trong 2n điểm A1 , A2 , ..., An gấp 20 lần số hình chữ nhật có các đỉnh là 4 trong 2n điểm A1 , A2 , ..., An , tìm n . Giải.  Mỗi cách chọn ra 3 điểm trong 2n điểm rồi nối chúng lại cho ta một hình tam giác. Do 3 đó, số tam giác có đỉnh là 3 trong số 2n điểm là C2n .  Giả sử đa giác đều A1 A2 ... An nội tiếp đường tròn  O  , ABCD là hình chữ nhật có các   90  AC và BD đi đỉnh là 4 trong số 2n đỉnh của đa giác. Ta thấy  ABC  BCD qua  O  . Từ đây, ta suy ra cách tạo một hình chữ nhật có 4 đỉnh là bốn đỉnh của tứ giác: Chọn ra 2 đường chéo đi qua O từ n đường chéo đi qua O của đa giác. Bước này có Cn2 cách thực hiện. Từ 2 đường chéo vừa chọn ra, bao giờ ta cũng có đúng một cách nối các đầu mút đề được một hình chữ nhật. Vậy số hình chữ nhật có đỉnh là 4 trong số 2n điểm là Cn2 . Theo giả thiết thì  2n !  20 n !   2n  2  2n  1 2n  20 n  1 n   3! 2n  3 ! 2! n  2 ! 3  n  0  loaïi   2   n  1 2n  1 n  15  n  1 n   n  1  2n  16n   0   n  1  loaïi    n  8  thoûa maõn  C23n  20Cn2  . Vậy n  8 . Ví dụ 5. [ĐHB04] Trong một môn học, thầy giáo có 30 câu hỏi khác nhau gồm 5 câu hỏi khó, 10 câu hỏi trung bình và 15 câu hỏi dễ. Từ 30 câu hỏi đó, có thể lập được bao nhiêu đề kiểm 15 tra, mỗi đề gồm 5 câu hỏi khác nhau, sao cho trong mỗi đề nhất thiết phải có đủ 3 loại câu hỏi (khó, trung bình, dễ) và số câu hỏi dễ không ít hơn 2 ? Giải. Thầy giáo có 3 phương án sau đây để lập một đề thi thỏa mãn yêu cầu.  Phương án 1. Đề thi có 2 câu dễ, 1 câu trung bình, 2 câu khó. Theo quy tắc nhân, số cách thực hiện phương án này là C152 C101 C52 .  Phương án 2. Đề thi có 2 câu dễ, 2 câu trung bình, 1 câu khó. Theo quy tắc nhân, số cách thực hiện phương án này là C152 C102 C51 .  Phương án 3. Đề thi có 3 câu dễ, 1 câu trung bình, 1 câu khó. Theo quy tắc nhân, số 1 cách thực hiện phương án này là C153 C10 C51 . Vậy, theo quy tắc cộng, số đề kiểm tra lập được theo yêu cầu là n1  n2  n3  C152 C101 C52  C152 C102 C51  C153 C101 C51  56875 . Ví dụ 6. [ĐHB05] Một đội thanh niên tình nguyện có 15 người gồm 12 nam và 3 nữ. Hỏi có bao nhiêu cách phân công đội thanh niên đó về giúp đỡ ba tỉnh miền núi sao cho mỗi tỉnh có 4 nam và 1 nữ. Giải. Ta phân công như sau. Bước 1. Chọn thanh niên tình nguyện cho tỉnh thứ nhất. Theo quy tắc nhân thì bước này có số cách thực hiện là C124 C31 . Bước 2. Chọn thanh niên tình nguyện cho tỉnh thứ hai. Vì đã chọn 4 nam và 1 nữ ở bước 1 nên theo quy tắc nhân, số cách thực hiện bước này là C84C21 . Các thanh niên còn lại phân công đi giúp đỡ tỉnh thứ ba. Vậy theo quy tắc nhân thì số cách phân công là C124 C31C84C21  207900 . Ví dụ 7. [ĐHD06] Đội thanh niên xung kích của một trường phổ thông có 12 học sinh, gồm 5 học sinh lớp T, 4 học sinh lớp L và 3 học sinh lớp H. Cần chọn ra 4 học sinh đi làm nhiệm vụ sao cho 4 học sinh đó thuộc không quá 2 trong 3 lớp nói trên. Hỏi có bao nhiêu cách chọn như vậy? Giải. Nếu bỏ qua điều kiện 4 học sinh thuộc không quá 2 trong 3 lớp thì số cách chọn là C124 . Bây giờ ta đếm số cách chọn mà 4 học sinh đó bao gồm học sinh của cả 3 lớp. Để làm như vậy ta có sau phương án sau.  Phương án 1. Chọn 2 học sinh lớp T, 1 học sinh lớp L, 1 học sinh lớp H. Theo quy tắc nhân, số cách thực hiện phương án này là n2  C52C41C41 . 16