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

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

1

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 k n A

, 0! = 1 ! .( 1)....( 1) ( )!

k n

n A n n n k n k      

* 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 k n C ! !.( )!

k n

n C k n k  

* Chú ý: 1 1 1 , k n k k k k n n n n n C C C C C        6. Công thức nhị thức Niutơn:

0 1 1 ( ) ... ... n n n k n k k n n n n n n a b C a C a b C a b C b         

hay

0 ( )

n n k n k k n k a b C a b 

  

* 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 = k n k k n C a b  ( 0,1,...) k  Đâ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ì . k n k n n C C  

5/ 0 1 2 (1 1) ..... n n n n n n C C C      

6/ 0 = 0 1 (1 1) ... ( 1) ... ( 1) n k k n n n n n n C C C C        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 123 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ữ …