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

LÝ THUYẾT 1. Quy tắc cộng: Được phát biểu như sau: Nếu có: m1 cách chọn đối tượng x1, m2 cách chọn đối tượng x2, ….., mn cách chọn đối tượng xn và nếu cách chọn đối tượng xi không trùng với bất kì đối tượng xj nào thì có: m1 + m2 + … + mn cách chọn một trong các đối tượng đã cho. 2. Quy tắc nhân: Được phát biểu như sau: Nếu có: m1 cách chọn đối tượng x1, sau đó với mỗi cách chọn x1 có m2 cách chọn đối tuợng x2, sau đó với mỗi cách chọn x1, x2 như thế có m3 cách chọn đối tượng x3, …, cuối cùng với mỗi cách chọn x1, x2,…,xn-1 như thế có mn cách chọn xn, thì có: m1.m2….mn cách chọn dãy x1 x2,…, xn. 3. Hoán vị: Cho tập hợp A gồm n phần tử (n 1). Mỗi cách sắ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ử đó. * Số hoán vị của n phần tử kí hiệu là Pn, với Pn = n.(n 1).(n 2)…3.2.1 = n! 4. Chỉnh hợp: Cho tập A gồm n phần tử. Mỗi bộ phận k (0 k n) phần tử sắp thứ tự của tập A được gọi là một chỉnh hợp chập k của n phần tử của A. * Số chỉnh hợp chập k của n phần tử kí hiệu là , với , 0! = 1 * Chú ý: Mỗi chỉnh hợp chập n của n phần tử chính là một hoán vị của n phần tử đó. 5. Tổ hợp: Cho tập hợp A gồm n phần tử. Mỗi tập con gồm k (0 k n) phần tử của A được gọi là một tổ hợp chập k của n phần tử đã cho. * Số tổ hợp chập k của n phần tử kí hiệu là , với * Chú ý: 6. Công thức nhị thức Niutơn: hay * Các tính chất: 1/ Số các số hạng của công thức bằng n + 1. 2/ Tổng các số mũ của a và b trong mỗi số hạng bằng số mũ của nhị thức: (n k) + k = n. 3/ Số hạng tổng quát có dạng: Tn+1 = Đây là số hạng thứ k + 1 trong khai triển nhị thức (a+b)n 4/ Các hệ số nhị thức cách đều hai số hạng đầu và cuối bằng nhau vì . 5/ 6/ 0 = 7/ Tam giác Pascal. BÀI TẬP Bài 1: Muốn đạt chứng chỉ B mông tiếng Anh thì 1 thí sinh phải thi đồng thời 4 môn: viết, đọc hiểu, nghe, nói và mỗi môn phải trên 5 điểm. Trong đó môn viết có 12 đề, môn đọc hiểu có 14 đề, có 9 đề môn nghe và có 18 đề môn nói. Hỏi thí sinh có bao biêu cách chọn đề thi (đủ 4 môn)? ĐS: 27216 Bài 2: Cho tập hợp A = {1; 2; 3; 4; 5; 6; 7; 8; 9}. Từ tập A có thể lập được bao nhiêu số tự nhiên: a/ gồm 5 chữ số đôi một khác nhau và > 50000. ĐS: 1440 b/ gồm 6 chữ số đôi một khác nhau sao cho chữ số đứng ở vị trí thứ 3 chia hết cho 5 và chữ số đứng cuối lẻ. ĐS: 336 c/ có 5 chữ số đôi một khác nhau sao cho các số này không bắt đầu bằng 16 và chữ số đứng cuối không chia hết cho 5. ĐS: 1440 d/ lẻ có 5 chữ số đôi một khác nhau mà không chia hết cho 5. ĐS: 720 ĐS: e/ 1440 e/ có 6 chữ số đôi một khác nhau biết chữ số thứ 3 luôn lẻ. f/ có 6 chữ số đôi một kh nh sao cho chữ số đầu và cuối đều chẵn, chữ số 3 luôn có mặt đúng một lần. ĐS: 4320 g/ chẵn có 6 chữ số đmkn sao cho chữ số đứng đầu chẵn và chữ số 4 luôn có mặt đúng một lần. ĐS: 7920. h/ có 6 chữ số đmhn sao cho hai chữ số 1 và 3 không đứng cạnh nhau. ĐS: 18480. i/ có 7 chữ số đmkn sao cho chữ số 1, 2, 3 luôn đứng cạnh nhau. ĐS: 10800 j/ có 7 chữ số đmkn sao cho các số này chia hết cho 2 và không bắt đầu bởi . ĐS: 80460 k/ có 7 chữ số khác nhau sao cho các số này chia hết cho 5 và luôn có mặt không quá hai chữ số chẵn. ĐS: 125280 Bài 3: Cho tập hợp A = {0; 1; 2; …… ; 9}. Từ tập A có thể lập được bao nhiêu số tự nhiên: a/ có 5 chữ số đôi một khác nhau. ĐS: 27216. b/ lẻ có 5 chữ số đôi một khác nhau. ĐS: 13440. c/ có 6 chữ số đôi một khác nhau và các số này chia hết cho 5. ĐS: 28560 d/ chẵn gồm 5 chữ số đôi một khác nhau. ĐS: 13776. e/ lẻ gồm 6 chữ số đôi một khác nhau biết chữ số 2 luôn có mặt đúng một lần. ĐS: 37800 f/ lẻ gồm 5 chữ số đôi một khác nhau biết chữ số 3 luôn có mặt đúng một lần. ĐS: 7560 g/ chẵn gồm 6 chữ số đôi một khác nhau sao cho chữ số đứng ở vị trí thứ 3 không chia hết cho 5. ĐS: 26880 h/ có 6 chữ số đôi một khác nhau sao cho chữ số đứng đầu và cuối đều chẵn. ĐS: 26780 i/ có 5 chữ số đôi một khác nhau sao cho chữ số 1 và 3 luôn đứng cạnh nhau. ĐS: 2436 j/ có 6 chữ số đôi một khác nhau sao cho tống của chữ số đầu và chữ số cuối chia hết cho 5. ĐS: 21480 k/ có 5 chữ số đôi một khác nhau sao cho chữ số đứng đầu lẻ và chữ số đứng giữa chia hết cho 5. ĐS: 1344 l/ có 6 chữ số đmkn sao cho luôn có mặt chữ số 0 và 1. m/ có 5 chữ số đmkn sao cho có ít nhất hai chữ số chẵn. ĐS:l/ 21000 m/ 12120 n/ có 7 chữ số đmkn sao cho luôn có mặt chữ số 2, 4, 6, 8. p/ có 7 chữ số đmkn sao cho chữ số 1 luôn đứng trước chữ số 2. ĐS: n/ 93600 p/ 94920 r/ 259320 q/ có 6 chữ số đmkn sao cho luôn có mặt chữ số 1, 5, 9 và hai chữ số 1 và 5 luôn đứng cạnh nhau. ĐS: 7680 r/ có 7 chữ số đmkn sao cho chữ số ở vị trí thứ 4 không chia hết cho 4 và đồng thời luôn có mặt chữ số 1 và 4. Bài 4: 1/ Xếp 6 bạn Tuyết, Trang, Nam, Thảo, Linh, Nhân vào một ghế dài. Hỏi có bao nhiêu cách xếp nếu: a/ 6 người ngồi bất kì. ĐS: a/ 6! b/ 48 c/ 240 d/ … b/ Bạn Tuyết và Linh ngồi ở hai đầu ghế. c/ Bạn Tuyết và Linh luôn ngồi cạnh nhau. d/ Bạn Tuyết và Linh không thể ngồi cạnh nhau. 2/ Một bàn dài có hai dãy ghế đối diện nhau, mỗi dãy gồm 4 ghế. Người ta muốn xắp sếp chỗ ngồi cho 4 học sinh trường A và 4 học sinh trường B vào bàn nói trên. Hỏi có bao nhiêu cách sắp xếp trong mỗi trường hợp sau: a/ Bất kì hai học sinh nào nồi cạnh nhau hoặc đối diện nhau phải khác truờng với nhau. ĐS: 1152 b/ Bất kì hai học sinh nào ngồi đối diện nhau thì khác trường với nhau. ĐS: 9216 ĐS: 3/ 207360 3/ Một HS có 12 cuốn sách đôi một khác nhau trong đó có hai cuốn môn Toán, 4 cuốn môn Văn, 6 cuốn môn Anh văn. Hỏi có bao nhiêu cách sắp xếp tất cả cuốn sách đó trên một kệ dài, nếu mội cuốn sách này được xếp kề nhau. Bài 5: 1/ Một hộp đựng 5 viên bi xanh và 7 viên bi vàng. Hỏi có bao nhiêu cách lấy ra: a/ 6 viên bi bất kì. b/ 6 viên bi bất kì sao cho có 2 viên bi xanh và 4 viên bi vàng. ĐS: a/ 924 b/ 350 2/ Một hộp đựng 5 viên bi xanh, 6 viên bi đỏ, 4 viên bi vàng. Hỏi có bao nhiêu cách lấy ra: a/ 6 viên bi trong đó có 2 viên bi xanh và có ít nhất 2 viên bi vàng và phải có đủ 3 màu. ĐS: 1700 b/ 9 viên bi có đủ ba màu. ĐS: 4939 ĐS: 3/ 1200 3/ Có 5 con tem và 6 bì thư. Chọn ra 3 con tem để dán vào 3 bì thư, mỗi bì dán một con tem. Hỏi có bao nhiêu cách? 4/ Một hộp có 8 bi xanh, 5 bi đỏ, 3 bi vàng. Có bao nhiêu cách lấy ra 4 viên bi nếu: ĐS: a/784 b/ 400 a/ có đúng 2 bi xanh. b/ số bi xanh bằng số bi đỏ. c/ trong số bi lấy ra không có đủ 3 màu. ĐS: …. 5/ Có 6 cuốn sách khác nhau trong đó có cuốn "Giải tích ttổ hợp". Lấy có thứ tụ ra 4 cuốn. Có bao nhiêu cách lấy ra nếu: a/ phải có cuốn "Giải tích tổ hợp". ĐS: 240 b/ không có cuốn "Giải tích tổ hợp". ĐS: 120 6/ Một lớp có 10 HS nam và 15 HS nữ. Có bao nhiêu cách chọn ra đôi văn nghệ: a/ gồm 12 người. b/ gồm 13 người sao cho có ít nhất 10 HS nữ và phai có cả nam lẫn nữ. ĐS: a/ b/ 426335 Bài 6: Trong mặt phẳng cho đa giác đều 10 cạnh. Có bao nhiêu tam giác: a/ tạo thành từ các đỉnh của đa giác. ĐS: 120 b/ có đúng hai cạnh của đa giác. ĐS: 10 c/ có đúng một cạnh của đa giác. ĐS: 60 d/ không chứa cạnh nào của đa giác. ĐS: 50 Bài 7: 1/ Có 10 HS được chia làm 3 nhóm: nhóm 1 gồm có 3 HS, nhóm 2 có 4 HS, nhóm 3 có 3 HS. Có bao nhiêu cách chia như vậy? ĐS: 4200 2/ Có 48 HS được chia làm 4 tổ mỗi tổ gồm 12 HS. Hỏi có bao nhiêu cách chia như vậy? ĐS: ….. 3/ Cho tập hợp A gồm có 20 phần tử. a/ Có bao nhiêu tập hợp con của tập A? ĐS: 220. b/ Có bao nhiêu tập hợp con khác rỗng của A mà có phần tủ là số chẵn? ĐS: ….. Bài 8: 1/ Có 12 quyển sách khác nhau bao gồm 3 loại với số lượng bằng nhau. Có bao nhiêu cách sắp xếp chúng vào một kệ sách cùng một hiệu thì ở cùng một chỗ? ĐS: 82944 2/ Có 7 viên ngọc có máu sắc khác nhau. Hỏi có bao nhiêu cách xâu 7 viên ngọc thành 1 sợi dây chuyền đeo cổ. (360). 3/ Có 4 nam và 3 nữ. Hỏi có bao nhiêu cách xếp họ thành một hàng sao cho nam nữ ngồi xen kẽ với nhau. ĐS: 144. Bài 9: 1/ Cho tập A = {0, 1, 2, 3, 4}. Từ tập A có thể lập được bao nhiêu số có 7 chữ số sao cho chữ số 3 có mặt 3 lần, còn các chữ số khác có mặt 1 lần. 2/ Từ tập A = {1, 2, 3, 4, 5, 6} có thể lập được bao nhiêu số có 9 chữ số sao cho chữ số 3 có mặt 3 lần, chữ số 5 có mặt 3 lần còn các chữ số khác có mặt đúng một lần.