Kiến thức trọng tâm môn Toán Lớp 11 - Chương 2: Tổ hợp và xác suất

Nội dung text: Kiến thức trọng tâm môn Toán Lớp 11 - Chương 2: Tổ hợp và xác suất

1. chương 2 tổ hợp và xác suất A. Kiến thức cần nhớ I. hai quy tắc đếm cơ bản 1. Quy tắc cộng Quy tắc cộng: Giả sử một công việc có thể tiến hành theo một trong k phương án A 1, A2, , Ak. Nếu: ▪ Phương án A1 có thể làm bằng n1 cách. ▪ Phương án A2 có thể làm bằng n2 cách. ▪ ▪ Phương án Ak có thể làm bằng nk cách. Khi đó, có công việc có thể thực hiện theo n1 + n2 + + nk cách. Biểu diễn dưới dạng tập hợp: Quy tắc cộng thường được phát biểu bằng ngôn ngữ tập hợp như sau: 1. Nếu A, B là hai tập hữu hạn, không giao nhau, thì: A  B = A + B. 2. Nếu A1, A2, , Ak là k tập hữu hạn, từng đôi một không giao nhau, thì: A1  A2   Ak = A1 + A2 + + Ak. 3. Nếu A, B là là hai tập hữu hạn và A  B, thì: 10 k k  C10x  = B \ A = B A. k 0 2. Quy tắc nhân Quy tắc nhân: Giả sử một công việc A bao gồm k công đoạn A1, A2, , Ak. Nếu: ▪ Công đoạn A1 có thể làm bằng n1 cách. ▪ Công đoạn A2 có thể làm bằng n2 cách. ▪ ▪ Công đoạn Ak có thể làm bằng nk cách. Khi đó, có công việc có thể thực hiện theo n1.n2 nk cách. Biểu diễn quy tắc nhân dưới dạng tập hợp: Quy tắc nhân thường được phát biểu bằng ngôn ngữ tập hợp như sau: Nếu A1, A2, , Am là các tập hữu hạn, khi đó số phần tử của tích Đề các của các tập này bằng tích của số các phần tử của mọi tập thành phần. Để liên hệ với quy tắc nhân hãy nhớ là việc chọn một phần tử của tích Đề các A1 A2 Am được tiến hành bằng cách chọn lần lượt một phần tử của A1 một phần tử của A2, , một phần tử của Am. Theo quy tắc nhân ta nhận được đẳng thức:  A1 A2 Am =  A1 .  A2  Am. 83
2. 3. Nguyên lý bù trừ Khi hai công việc có thể được làm đồng thời, chúng ta không thể dùng quy tắc cộng để tính số cách thực hiện nhiệm vụ gồm cả hai việc. Cộng số cách làm mỗi việc sẽ dẫn đến sự trùng lặp, vì những cách làm cả hai việc sẽ được tính hai lần . Để tính đúng số cách thực hiện nhiệm vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả hai việc. Đó là nguyên lý bù trừ. Biểu diễn dưới dạng tập hợp: Chúng ta có thể phát biểu nguyên lý bù trừ bằng ngôn ngữ tập hợp như sau: Cho A1, A2 là các tập hợp. Gọi T1 là việc chọn một phần tử của A1 còn T2 là việc chọn một phần tử của A2. ▪ Có  A1 cách làm việc T1 ▪ Có  A2 cách làm việc T2. Số cách làm hoặc T1 hoặc T2 bằng tổng số cách làm việc T1 và số cách làm việc T2 trừ đi số cách làm cả hai việc. Vì có A1  A2 cách làm hoặc T1 hoặc T2, và có A1  A2 cách làm cả hai việc T1 và T2 nên chúng ta có: A1  A2 A1 A2 A1  A2 . II. hoán vị, chỉnh hợp và tổ hợp 1. hoán vị Định nghĩa 1: Cho tập hợp A, gồm n phần tử (n 1). Một 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ử đó. Định lí 1: Nếu kí hiệu số hoán vị của n phần tử là Pn, thì ta có: Pn = n! = 1.2.3 (n 1).n. 2. chỉnh hợp Định nghĩa 2: Cho tập hợp A gồm n phần tử. Một bộ gồm k (1 k n) phần tử sắp thứ tự của tập hợp A được gọi là một chỉnh hợp chập k của n phần tử của A.  Nhận xét: 1. Hai chỉnh hợp khác nhau khi và chỉ khi: hoặc có ít nhất một phần tử của chỉnh hợp này mà không là phần tử của chỉnh hợp kia, hoặc các phần tử của hai chỉnh hợp giống nhau nhưng được sắp xếp theo thứ tự khác nhau. 2. Bộ k phần tử có kể thứ tự được hiểu như sau: giả sử a, b là hai bộ k phần tử của tập E a = (a1, a2, , ak) và b = (b1, b2, , bk) ▪ a, b được coi là có kể thứ tự nếu: a = b ai = bi, i = 1,k . ▪ a, b được coi là không kể thứ tự nếu: a = b mỗi ai trùng với một bj nào đó i, j = 1,k . 84
3. k Định lí 2: Nếu kí hiệu số chỉnh hợp chập k của n phần tử là An , thì ta có: k An = n.(n 1) (n – k + 1).  Chú ý: k 1. Ta có thể viết An theo cách khác: n ! Ak n(n 1)(n 2) (n k 1) n (n-k) ! 2. Nếu k = n thì: n n! n! A = = = n! = Pn. n 0! 1 Như vậy, một chỉnh hợp n chập n được gọi là một hoán vị của n phần tử. Từ đó, suy ra: n k n k An = An . An k , với mọi 1 k n. Kết quả này được phát biểu là " Số các hoán vị của n phần tử phân biệt bằng số các chỉnh hợp n chập r của các phần tử đó, nhân với số các hoán vị của (n r) phần tử còn lại ". 3. tổ hợp Định nghĩa 3: Cho tập hợp A gồm n phần tử. Một tập con của E, gồm k phần tử phân biệt (1 k n), được gọi là một tổ hợp chập k của n phần tử của A. k Định lí 3: Nếu kí hiệu số tổ hợp chập k của n phần tử là Cn , thì ta có: Ak n(n 1) (n k 1) Ck = n = , (1) n k! k! 0 với 0 k n và quy ước Cn = 1. Từ kết quả của định lí 3 suy ra: n! 1. Ck = , với 0 k n. (2) n k!(n k)! k n k 2. Cn = Cn , với 0 k n. (3) k k k 1 3. Cn = Cn 1 + Cn 1 , với 0 k n. (4) III. nhị thức niu tơn 1. Công thức Nhị thức Newton ở lớp 8 chúng ta đã được làm quen với các hằng đẳng thức: 2 2 2 0 2 0 0 1 2 1 1 2 0 2 (a + b) = a + 2ab + b = C2 a b + C2 a b + C2 a b , 3 3 2 2 3 0 3 0 0 1 3 1 1 2 3 2 2 3 0 3 (a + b) = a + 3a b + 3ab + b = C3 a b + C3 a b + C3 a b + C3 a b . 85
4. Tổng quát: Với mọi cặp số a, b và mọi số n nguyên dương, ta có: n 0 n 1 n 1 2 n 2 2 n 1 n 1 n n (a + b) = Cn a + Cn a b + Cn a b + + Cn ab + Cn b (1) n k n k k = Cna .b . k 0 Công thức trên được gọi là công thức nhị thức Niu tơn (gọi tắt là nhị thức Niu tơn) Nhận xét công thức nhị thức niutơn 1. Số các số hạng ở bên phải của công thức bằng n + 1, n là số mũ của nhị thức ở vế trái. 2. Tổng các số mũ của a và b trong mỗi số hạng bằng n. 3. Số hạng tổng quát có dạng: k n k k Tk + 1 = Cn a b , với k = 0, 1, , n. đó là số hạng thứ k + 1 trong sự khai triển của nhị thức (a + b)n. n k k k Như vậy, với yêu cầu "Tìm hệ số của a b " thì cầu trả lời là Cn . 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 Cn = Cn , 0 k n. Một số dạng đặc biệt Dạng 1: Thay a = 1 và b = x vào (1), ta được: n 0 1 2 2 n 1 n 1 n n (1 + x) = Cn + Cn x + Cn x + + Cn x + Cn x . (2) Dạng 2: Thay a = 1 và b = x vào (1), ta được: k n 0 1 2 n 2 kCn k nCn n (1 x) = Cn Cn x + Cn x + ( 1) x + + ( 1) x . (3) Khi đó: ▪ Thay x = 1 vào (2), ta được: 0 1 2 n n Cn + Cn + Cn + + Cn = 2 . ▪ Thay x = 1 vào (3), ta được: n 0 1 2 n Cn Cn Cn + Cn + ( 1) = 0. 2. tam giác Pascal Các hệ số của khai triển Niutơn của nhị thức (a + b)n có thể được sắp xếp thành tam giác sau đây (gọi là tam giác Pascal): n = 0 1 n = 1 1 1 n = 2 1 2 1 n = 3 1 3 3 1 n = 4 1 4 6 4 1 n = 5 1 5 10 10 5 1 n = 6 1 6 15 20 15 6 1 Như vậy, dựa vào bảng ta có: 1 3 2 C4 = C4 = 4, C4 = 6. 1 2 2 k k 1 k 1 C5 + C5 = C6 (chúng ta đã từng được biết Cn + Cn = Cn 1 ). 86
5. IV. biến cố và xác suất của biến cố 1. Không gian xác suất Định nghĩa: (Phép thử ngẫu nhiên và không gian mẫu): a. Một phép thử ngẫu nhiên (gọi tắt là phép thử) là một thí nghiệm hay một hành động mà: ▪ Có thể lặp đi lặp lại nhiều lần trong các điều kiện giống nhau. ▪ Kết quả của nó không dự đoán trước được. ▪ Có thể xác định được tập hợp tất cả các kết quả có thể xảy ra của phép thử đó. Phép thử thường được kí hiệu bởi chữ T. b. Tập hợp tất cả các kết quả có thể xảy ra của phép thử được gọi là không gian mẫu của phép thử và được kí hiệu bởi chữ  (đọc là ô mê ga). 2. biến cố Định nghĩa: (Biến cố liên quan đến phép thử): Một biến cố A liên quan tới phép thử T được mô tả bởi một tập con A nào đó của không gian mẫu  của phép thử đó. Biến cố A xảy ra khi và chỉ khi kết quả của T thuộc tập A. Mỗi phần tử của A được gọi là một kết quả thuận lợi cho A. ▪ Biến cố chắc chắn là biến cố luôn xảy ra khi thực hiện phép thử T. Biến cố chắc chắn được mô tả bởi tập  và được kí hiệu là . ▪ Biến cố không thể là biến cố không bao giờ xảy ra khi phép thử T được thực hiện. Biến cố không được mô tả bởi tập  và được kí hiệu là . 3. xác suất của biến cố Định nghĩa cổ điển của xác suất: Giả sử phép thử T có không gian mẫu  là tập hợp hữu hạn và các kết quả của T là đồng khả năng. Nếu A là một biến cố liên quan tới phép thử T và  A là tập hợp các kết quả thuận lợi A thì xác suất của A là một số, kí hiệu là P(A) được xác định bởi công thức: |  | P(A) = A , (1) |  | trong đó A và  lần lượt là số phần tử của tập A và .  Chú ý: 1. Từ định nghĩa trên suy ra: ▪ 0 P(A) 1. ▪ P() = 1 và P() = 0. 2. Việc tính xác suất của biến cố A được thực hiện theo các bước: Bước 1. Thực hiện hai phép đếm: ▪ Đếm số phần tử của không gian mẫu , tức là đếm số kết quả có thể của phép thử T. ▪ Đếm số phần tử của tập A, tức là đếm số kết quả thuận lợi cho A. Bước 2. Sử dụng công thức (1) để tính P(A). 87
6. Định nghĩa thống kê của xác suất: Xét phép thử T và biến cố A liên quan tới phép thử đó. Ta tiến hành lặp đi lặp lại N phép thử T và thống kê xem biến cố A xuất hiện bao nhiêu lần. ▪ Số lần xuất hiện biến cố A được gọi là tần số của A trong N lần thực hiện phép thử T. ▪ Tỉ số giữa tần số của A với số N được gọi là tần suất của A trong N lần thực hiện phép thử T. Khi số lần thử N càng lớn thì tần xuất của A càng gần với một số xác định, số đó được gọi là xác suất của A theo nghĩa thống kê. V. các quy tắc tính xác suất 1. quy tắc cộng xác suất Định nghĩa biến cố hợp: Cho hai biến cố A và B cùng liên quan đến một phép thử T. Biến cố "A hoặc B xảy ra", kí hiệu là AB, được gọi là hợp của hai biến cố A và B. Nếu gọi: ▪ A là tập hợp mô tả các kết quả thuận lợi cho A, ▪ B là tập hợp mô tả các kết quả thuận lợi cho B, thì tập hợp các kết quả thuận lợi cho AB là AB. Một cách tổng quát: Cho k biến cố A1, A2, , Ak cùng liên quan đến một phép thử T. Biến cố "Có ít nhất một trong các biến cố A1, A2, , Ak xảy ra", kí hiệu là A1 A2 Ak, được gọi là hợp của k biến cố đó. Định nghĩa biến cố xung khắc: Cho hai biến cố A và B cùng liên quan đến một phép thử T. Hai biến cố A và B được gọi là xung khắc nếu biến cố này xảy ra thì biến cố kia không xảy ra. Hai biến cố A và B là xung khắc nếu và chỉ nếu AB = . Quy tắc cộng xác suất: 1. Nếu hai biến cố A và B xung khắc thì xác suất để A hoặc B xảy ra là: P(AB) = P(A) + P(B). 2. Cho k biến cố A1, A2, , Ak đôi một xung khắc với nhau thì xác suất để ít nhất một trong các biến cố A1, A2, , Ak xảy ra là: P(A1A2 Ak) = P(A1) + P(A2) + + P(Ak). Định nghĩa biến cố đối: Cho biến cố A khi đó biến cố "không xảy ra A", kí hiệu là A , được gọi là biến cố đối của A.  Chú ý: Hai biến cố đối nhau là hai biến cố xung khắc. Tuy nhiên điều ngược lại không đúng. 88
7. Định lí: Cho biến cố A. Xác suất của biến cố đối A là P( A ) = 1 P(A). 2. quy tắc nhân xác suất Định nghĩa biến cố giao: Cho hai biến cố A và B cùng liên quan đến một phép thử T. Biến cố "cả A và B cùng xảy ra", kí hiệu là AB, được gọi là giao của hai biến cố A và B. Nếu gọi A và B lần lượt là tập hợp mô tả các kết quả thuận lợi cho A và B thì tập hợp các kết quả thuận lợi cho AB là AB. Một cách tổng quát: Cho k biến cố A1, A2, , Ak cùng liên quan đến một phép thử T. Biến cố "tất cả k biến cố A1, A2, , Ak đều xảy ra", kí hiệu là A1A2Ak, được gọi là giao của k biến cố đó. Định nghĩa biến cố độc lập: Cho hai biến cố A và B cùng liên quan đến một phép thử T. Hai biến cố A và B được gọi là độc lập với nhau nếu việc xảy ra hay không xảy ra của biến cố này không làm ảnh hưởng tới việc xảy ra hay không xảy ra của biến cố kia. Một cách tổng quát: Cho k biến cố A1, A2, , Ak cùng liên quan đến một phép thử T. k biến cố này được gọi là độc lập với nhau nếu việc xảy ra hay không xảy ra của mỗi biến cố không làm ảnh hưởng tới việc xảy ra hay không xảy ra của các biến cố còn lại.  Nhận xét: Nếu hai biến cố A, B độc lập với nhau thì A và B ; A và B; A và B cũng độc lập với nhau. Quy tắc nhân xác suất: 1. Nếu hai biến cố A và B độc lập với nhau thì xác suất để A và B xảy ra là: P(AB) = P(A).P(B). 2. Cho k biến cố A1, A2, , Ak độc lập với nhau thì: P(A1A2Ak) = P(A1).P(A2).P(Ak). VI. biến ngẫu nhiên rời rạc 1. Khái niệm biến ngẫu nhiên rời rạc Định nghĩa: Đại lượng X được gọi là một biến ngẫu nhiên rời rạc nếu nó nhận giá trị bằng số thuộc một tập hữu hạn nào đó, và giá trị ấy là ngẫu nhiên, không dự đoán trước được. 2. phân bố xác suất của biến ngẫu nhiên rời rạc Giả sử X là một biến ngẫu nhiên rời rạc nhận các giá trị {x1, x2, , xn}. Khi đó bảng phân bố xác suất của biến ngẫu nhiên rời rạc X có dạng: X x1 x2 xn P p1 p2 pn trong đó P(X = xk) = pk với k = 1, 2, , n.  Lưu ý: Trong bảng trên luôn có p1 + p2 + + pn = 1. 89
8. 3. kì vọng Định nghĩa: Cho X là một biến ngẫu nhiên rời rạc với tập giá trị là {x1, x2, , xn}. Kì vọng của X, kí hiệu là E(X) là một số được tính theo công thức: n E(X) = x1p1 + x2p2 + + xnpn =  xk .pk , k 1 trong đó pk = P(X = xk) với k = 1, 2, , n. ý nghĩa: E(X) là một con số cho ta một ý niệm về độ lớn trung bình của X. Vì thế kì vọng E(X) còn được gọi là giá trị trung bình của X. 4. phương sai và độ lệch chuẩn Định nghĩa: Cho X là một biến ngẫu nhiên rời rạc với tập giá trị là {x1, x2, , xn}. a. Phương sai của X, kí hiệu là V(X) là một số được tính theo công thức: n 2 V(X) = (xk ) .pk , k 1 trong đó pk = P(X = xK) với k = 1, 2, , n và  = E(X). b. Căn bậc hai của phương sai, kí hiệu là (X) được gọi là độ lệch chuẩn của X. Ta có: (X) = V(X) . ý nghĩa: V(X) là một số không âm, nó cho ta một ý niệm về mức độ phân tán các giá trị của X xung quanh giá trị trung bình. Phương sai càng lớn thì độ phân tán này cành lớn. B Phương pháp giải các dạng toán liên quan Đ1. Hai quy tắc đếm cơ bản Dạng toán 1: Sử dụng các quy tắc để thực hiện bài toán đếm số phương án Phương pháp áp dụng 1. Để sử dụng quy tắc cộng trong bài toán đếm, ta thực hiện theo các bước: Bước 1: Phân tách các phương án thành k nhóm độc lập với nhau: H1, H2, , Hk. Bước 2: Nếu: ▪ H1 có n1 cách khác nhau. ▪ Hk có nk cách khác nhau. Bước 3: Khi đó, ta có tất cả n1 + + nk phương án. 2. Để sử dụng quy tắc nhân trong bài toán đếm, ta thực hiện theo các bước: 90
9. Bước 1: Phân tách một hành động H thành k công việc nhỏ liên tiếp: H1, , Hk. Bước 2: Nếu ta có: ▪ n1 cách khác nhau để thực hiện H1. ▪ Một khi thực hiện xong H1, , Hk 1, ta có nk cách thực hiện Hk. Bước 3: Khi đó ta có tất cả: n1 nk cách để thực hiện hành động H. 3. Trong nhiều trường hợp chúng ta cần kết hợp cả hai quy tắc để thực hiện bài toán đếm. Thí dụ 1. Trong một trường THPT, khối 11 có 280 học sinh nam và 325 học sinh nữ. a. Nhà trường cần chọn một học sinh ở khối 11 đi dự dạ hội của học sinh thành phố. Hỏi nhà trường có bao nhiêu cách chọn ? b. Nhà trường cần chọn hai học sinh trong đó có một nam và một nữ đi dự trại hè của học sinh thành phố. Hỏi nhà trường có bao nhiêu cách chọn ?  Giải a. Để chọn một trong số 280 + 325 = 605 em đi dự dạ hội của học sinh thành phố ta có ngay 605 cách chọn. b. Ta thấy: ▪ Có 280 cách chọn một em nam. ▪ Có 325 cách chọn một em nữ. Vậy, có tất cả: 280 325 = 91000 cách chọn một nam và một nữ đi dự trại hè. Thí dụ 2. Có 5 con đường nối 2 thành phố X và Y, có 4 con đường nối 2 thành phố Y và Z. Muốn đi từ X đến Z thì phải qua Y. a. Hỏi có bao nhiêu cách chọn đường đi từ X đến Z ? b. Có bao nhiêu cách chọn đường đi và về từ X đến Z rồi về lại X bằng những con đường khác nhau?  Giải a. Nhận xét rằng: ▪ Có 5 cách chọn đường đi từ X đến Y. ▪ Tiếp theo, có 4 cách chọn đường đi từ Y đến Z. Do đó, có tất cả: 5 4 = 20 cách chọn đường đi từ X đến Z qua Y. b. Theo kết quả câu a) có 20 cách chọn đường đi. Khi trở về: ▪ Từ Z đến Y chỉ còn 3 con đường để chọn, do đó có 3 cách. ▪ Tiếp theo, từ Y về lại X chỉ còn 4 cách chọn. 91
10. Do đó, có tất cả: 3 4 = 12 cách chọn đường đi về từ Z đến X qua Y. Vậy, có tất cả: 20 12 = 240 cách chọn đường đi và về trên tuyến X  Z qua thành phố Y bằng những con đường khác nhau. Thí dụ 3. Mỗi người sử dụng hệ thống máy tính đều có mật khẩu dài từ sáu tới tám ký tự, trong đó mỗi ký tự là một chữ hoa hay chữ số. Mỗi mật khẩu phải chứa ít nhất một chữ số. Hỏi bao nhiêu mật khẩu ?  Giải Gọi P là tổng số mật khẩu có thể và P6, P7, P8 tương ứng là số mật khẩu dài, 6, 7, 8 ký tự. Theo quy tắc cộng ta có: P = P6 + P7 + P8. Bây giờ chúng ta sẽ tính P6, P7, P8. ▪ Tính trực tiếp P6 sẽ rất khó. Để tìm P6 dễ hơn ta tính số các xâu dài 6 ký tự là các chữ in hoa hoặc chữ số, rồi bớt đi số các xâu dài 6 ký tự là các chữ in hoa và không chứa chữ số nào. Theo quy tắc nhân số các xâu dài 6 ký tự là 366 và số các xâu không chứa các chữ số là 266. Vì vậy: 6 6 P6 = 36 – 26 = 1867866560. ▪ Hoàn toàn tương tự ta có: 7 7 P7 = 36 – 26 = 70332353920. 8 8 P8 = 36 – 26 = 2612282842 880. Vậy, ta được: P = P6 + P7 + P8 = 2684 483063360. Dạng toán 2: Sử dụng các quy tắc để thực hiện bài toán đếm số các số hình thành từ tập A Phương pháp áp dụng 1. Sử dụng quy tắc nhân để thực hiện bài toán đếm số các số gồm k chữ số hình thành từ tập A, ta thực hiện theo các bước: Bước 1: Một số gồm k chữ số hình thành từ tập A có dạng: 1 k , với i A, i = 1,k và 1 0. Bước 2: Đếm số cách chọn cho các i, i = 1,k (không nhất thiết phải theo thứ tự), giả sử bằng ni. Bước 3: Khi đó, số các số gồm k chữ số phân biệt hình thành từ tập A bằng: n1.n2 nk. 2. Sử dụng quy tắc cộng và quy tắc nhân để thực hiện bài toán đếm số các số hình thành từ tập A, ta thực hiện theo các bước: Bước 1: Chia tập các số cần đến thành các tập con H1, H2, độc lập với nhau (không giao nhau). 92
11. Bước 2: Sử dụng quy tắc nhân đến số phần tử của các tập H1, H2, , giả sử bằng k1, k2, Bước 3: Khi đó, số các số hình thành từ tập A bằng: k1 + k2 + . Thí dụ 1. Có bao nhiêu số tự nhiên có hai chữ số mà hai chữ số của nó đều chẵn ?  Giải Một số gồm 2 chữ số có dạng: 1 2 , với i A = {0, 2, 4, 6, 8} và 1 0. Trong đó: ▪ 1 được chọn từ tập A\{0} (có 4 phần tử) nên có 4 cách chọn. ▪ 2 được chọn từ tập A (có 5 phần tử) nên có 5 cách chọn. Như vậy, ta có: 4 5 = 20 số. Thí dụ 2. Cho tập A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. a. Từ tập A có thể lập được bao nhiêu số gồm có 9 chữ số khác nhau ? b. Từ tập A có thể lập được bao nhiêu số gồm có 9 chữ số khác nhau và chia hết cho 5 ? c. Từ tập A có thể lập được bao nhiêu số chẵn gồm có 9 chữ số khác nhau ?  Giải Một số 9 chữ số phân biệt được ký hiệu: = a1a 2 a9 , với a1 E , i = 1,9 và ai aj, i j. a. Ta có ngay a1, a2, , a9 là một bộ phân biệt thứ tự được chọn từ A, do đó nó là một hoán vị của 9 phần tử. Vậy, từ A có thể lập được: P9 = 9! = 36280 số thoả mãn điều kiện đầu bài. b. Số chia hết cho 5, do đó: ▪a 9 = 5, tức là có 1 cách chọn. ▪a 1, a2, , a8 là một bộ phân biệt thứ tự được chọn từ A\{5} do đó nó là một hoán vị của 8 phần tử, do đó có P8 cách chọn. Theo quy tắc nhân, số các số gồm 9 chữ số phân biệt và chia hết cho 5 hình thành từ tập A, bằng: 1.P8 = 40320 số. c. Số là số chẵn, do đó: ▪a 9 {2, 4, 6, 8}, tức là có 4 cách chọn. ▪a 1, a2, , a8 là một bộ phân biệt thứ tự được chọn từ A\{a9} do đó nó là một hoán vị của 8 phần tử, do đó có P8 cách chọn. Theo quy tắc nhân, số các số chẵn gồm 9 chữ số phân biệt hình thành từ tập A, bằng: 93
12. 4.P8 = 161280 số. Thí dụ 3. Cho tập A = {0, 1, 2, 3}. a. Có thể lập được bao nhiêu số gồm 3 chữ số hình thành từ tập A. b. Có thể lập được bao nhiêu số gồm 3 chữ số khác nhau hình thành từ tập A.  Giải a. Một số gồm 3 chữ số hình thành từ tập A có dạng 1 2 3 , với i A, i = 1,3 . Trong đó: ▪ 1 được chọn từ tập A\{0} (có 3 phần tử) nên có 3 cách chọn. ▪ 2 được chọn từ tập A (có 4 phần tử) nên có 4 cách chọn. ▪ 3 được chọn từ tập A (có 4 phần tử) nên có 4 cách chọn. Khi đó, số các số gồm 3 chữ số hình thành từ tập A bằng: 3.4.4 = 48 số. b. Một số gồm 3 chữ số phân biệt hình thành từ tập A có dạng: 1 2 3 , với i A, i = 1,3 và i j, i j. Trong đó: ▪ 1 được chọn từ tập A\{0} (có 3 phần tử) nên có 3 cách chọn. ▪ 2 được chọn từ tập A\{ 1} (có 3 phần tử) nên có 3 cách chọn. ▪ 3 được chọn từ tập A\{ 1, 2} (có 2 phần tử) nên có 2 cách chọn. Khi đó, số các số gồm 3 chữ số phân biệt hình thành từ tập A bằng: 3.3.2 = 18 số.  Chú ý: Ví dụ tiếp theo minh hoạ cho quy tắc cộng mở rộng. Thí dụ 4. Lớp toán rời rạc có 25 sinh viên giỏi tin học, 13 sinh viên giỏi toán và 8 sinh viên giỏi cả toán và tin học. Hỏi trong lớp này có bao nhiêu sinh viên, nếu mỗi sinh viên hoặc giỏi toán hoặc giỏi tin học giỏi cả hai môn ?  Giải Gọi A là tập các sinh viên giỏi tin học và B là tập các sinh viên giỏi toán học. Khi đó A ∩ B là tập các sinh viên giỏi cả toán và tin học. Vì mỗi sinh viên trong lớp hoặc giỏi toán giỏi tin hoặc giỏi cả hai môn, nên ta suy ra số sinh viên trong lớp là A  B . Do vậy: A  B A B A  B = 25 + 13 – 8 = 30. Thí dụ 5. Bao nhiêu số nguyên không lớn hơn 1000 chia hết cho 7 hoặc 11?  Giải Gọi A số nguyên không lớn hơn 1000 chia hết cho 7, và B là tập các số nguyên không lớn hơn 1000 chia hết cho 11. Khi đó A  B là tập các số nguyên không lớn 94
13. hơn 1000 chia hết cho 7 hoặc 11 và A∩B là tập các số nguyên không lớn hơn 1000 chia hết cho cả 7 và 11. Ta biết, trong số các số nguyên không lớn hơn 1000 có ▪ 1000/ 7 số nguyên chia hết cho 7 ▪ 1000/11 chia hết cho 11. ▪ Vì 7 và 11 là hai số nguyên tố cùng nhau nên số nguyên chia hết cho cả 7 và 11 là số nguyên chia hết cho 7.11. Số các số này là 1000/(7.11) . Từ đó suy ra: 1000 1000 1000 A  B A B A  B = 7 11 7.11 =142 + 90 – 12 = 220. Vậy, có 220 số nguyên không lớn hơn 1000 chia hết cho 7 hoặc 11. Đ2. Hoán vị, chỉnh hợp và tổ hợp Dạng toán 1: Thực hiện bài toán đếm Phương pháp áp dụng 1. Để nhận dạng một bài toán đếm có sử dụng hoán vị của n phần tử, chúng ta thường dựa trên các dấu hiệu đặc trưng sau: ▪ Tất cả n phần tử đều có mặt. ▪ Mỗi phần tử chỉ xuất hiện một lần. ▪ Có phân biệt thứ tự giữa các phần tử. 2. Để nhận dạng một bài toán đếm có sử dụng chỉnh hợp chập k của n phần tử, chúng ta thường dựa trên các dấu hiệu đặc trưng sau: ▪ Phải chọn k phần tử từ n phần tử cho trước. ▪ Có phân biệt thứ tự giữa k phần tử được chọn. 3. Để nhận dạng một bài toán đếm có sử dụng tổ hợp chập k của n phần tử, chúng ta thường dựa trên các dấu hiệu đặc trưng sau: ▪ Phải chọn k phần tử từ n phần tử cho trước. ▪ Không phân biệt thứ tự giữa k phần tử được chọn. Thí dụ 1. Cho tập A = {3, 4, 5, 6, 7}. a. Từ A có thể lập được bao nhiêu số gồm 5 chữ số phân biệt ? b. Tính tổng S của tất cả các số được tạo ra trong câu a).  Giải a. Mỗi số gồm 5 chữ số phân biệt hình thành từ tập A ứng với chỉ một hoán vị của 5 phần tử của tập A, và ngược lại. Vậy, số các số hình thành từ tập A bằng: P5 = 5! = 720 số. b. Nhận xét rằng " ứng với mỗi số N thuộc tập hợp này, luôn tồn tại một và chỉ một số N’ sao cho tổng N + N’ = 111110 ". Do đó, có tất cả 95
14. 720 = 360 cặp số (N, N’) mà tổng bằng 111110. 2 Vậy, tổng S của tất cả các số tạo bởi hoán vị đã cho bằng: S = 111110 x 360 = 39999600.  Nhận xét: Qua thí dụ trên chúng ta đã làm quen được với dạng toán "Sử dụng hoán vị để thực hiện bài toán đếm". Yêu cầu đặt ra ở đây với các em học sinh là hãy định hướng khi nào sử dụng hoán vị để giải. Thí dụ 2. Có n quả cầu trắng và n quả cầu đen, đánh dấu theo các số 1, 2, 3, , n. Có bao nhiêu cách sắp xếp các quả cầu này thành dãy sao cho 2 quả cầu cùng màu không nằm cạnh nhau ?  Giải Ta thấy ngay, có 2 khả năng: ▪ Các quả cầu trắng chiếm các vị trí lẻ, còn các quả cầu đen chiếm các vị trí chẵn. ▪ Các quả cầu trắng chiếm các vị trí chẵn, còn các quả cầu đen chiếm vị trí lẻ. Trong mỗi trường hợp: có n! cách sắp xếp các quả cầu trắng (hoặc đen) nghĩa là có (n!)2 cách sắp xếp. Vậy số cách sắp xếp các quả cầu sao cho 2 quả cầu cùng màu không nằm cạnh nhau là 2(n!)2. Thí dụ 3. Tìm số hoán vị của n phần tử trong đó có 2 phần tử a và b không đứng cạnh nhau.  Giải Trước hết, ta có số hoán vị của n phần tử là: Pn = n! Trong đó kể cả số hoán vị mà 2 phần tử a và b đứng cạnh nhau. Ta đi xem có bao nhiêu cách chọn cặp (a, b) đứng cạnh nhau và dễ thấy rằng: ▪ Với b đứng bên phải a, khi đó ta có thể chọn cho a tất cả (n 1) vị trí từ vị trí đầu tiên đến vị trí thứ (n 1). ▪ Với a đứng bên phải b, cũng có (n 1) cách chọn. Do đó có 2(n 1) cách chọn cặp (a, b) đứng cạnh nhau. ứng với mỗi trường hợp chọn cặp (a, b), ta có (n 2)! cách sắp xếp (n 2) vật còn lại vào (n 2) vị trí còn lại. Do đó, có tất cả: 2(n 1)(n 2)! = 2(n 1)! hoán vị n vật mà trong đó có 2 phần tử a và b đứng cạnh nhau. Suy ra, số hoán vị của n phần tử trong đó 2 phần tử a và b không đứng cạnh nhau là: n! 2(n 1)! = (n 2)(n 1)!. áp dụng: Số các số gồm 5 chữ số khác nhau trong đó 2 chữ số 1 và 2 không đứng cạnh nhau là: 96
15. 5! 2.4! = 120 48 = 72 số.  Chú ý: 1. Thí dụ trên đã minh hoạ cho hoán vị tròn. Ta phát biểu bài toántổng quát: "Mời n người khách ngồi vào xung quanh một bàn tròn. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi ?" Khi đó: ▪ Mời người khách danh dự vào chỗ danh dự. ▪ Còn lại (n 1) người khách ngồi tuỳ ý vào (n 1) vị trí còn lại. Vậy, ta có: (n 1)! cách sắp xếp. 2. Để minh hoạ cho hoán vị có lặp lại, ta xét: Có n vật sắp xếp vào n vị trí và trong số n vật này có: ▪n 1 vật giống nhau, ▪n 2 vật khác giống nhau, ▪ ▪n k vật khác lại giống nhau. Số cách sắp xếp n vật nào vào n chỗ là: n! . n1 !n2 ! nk ! Thí dụ 4. Với các chữ số 0, 1, 2, 3, 4, 5 ta có thể lập được bao nhiêu số gồm 8 chữ số trong đó chữ số 1 có mặt 3 lần, mỗi chữ số khác có mặt đúng 1 lần?  Giải Đây là số hoán vị 8 vật trong đó có 3 vật giống nhau (3 chữ số 1). Do đó, số các 8! số thoả mãn là . 3! Trong đó, kể cả những số có chữ số 0 tận cùng bên trái. Số các số này có thể xem 7! là số hoán vị 7 vật có 3 vật được lặp lại . 3! Do đó, số các số gồm 8 chữ số được viết từ các chữ số 0, 1, 2, 3, 4, 5 trong đó chữ số 1 có mặt 3 lần, mỗi chữ số còn lại có mặt đúng 1 lần là: 8! 7! 8.7! 7! 7.7! 7.4.5.6.7 5880 số. 3! 3! 3! 3! Thí dụ 5. Có bao nhiêu số tự nhiêu có 6 chữ số và chia hết cho 5 ?  Giải Một số gồm 6 chữ số phân biệt hình thành từ tập A = {0, 1, , 9} có dạng: a1a 2a3a 4a5a6 , với ai A, i = 1,6 và a1 0. Để số tìm được phải chia hết cho 5, ta thấy: ▪a 6 {0, 5} có 2 cách chọn. 97
16. ▪a 1 0 có 9 cách chọn. ▪ Tiếp theo, với các vị trí a2, a3, a4, a5 đều có 10 cách chọn. Như vậy, ta được: 2 9 104 = 1800000 số. Thí dụ 6. Cho tập A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Từ tập A có thể lập được bao nhiêu số có 6 chữ số khác nhau và mỗi số chứa chữ số 5 ? Trong các số đó, có bao nhiêu số không chia hết cho 5 ?  Giải Một số gồm 6 chữ số phân biệt hình thành từ tập A có dạng: a1a 2a3a 4a5a6 , với ai A, i = 1,6 và i j, i j. Để số tìm được phải có mặt chữ số 5, ta thấy: ▪ 5 { a1, a2, a3, a4, a5, a6} có 6 cách chọn. ▪ Tiếp theo, mỗi bộ số dành cho năm vị trí còn lại ứng với một chỉnh hợp chập 5 của các phần tử của tập A\{ 5} có 8 phần tử. 5 có A8 cách chọn. Như vậy, ta được: 5 6. A8 = 40320 số. 5 Trong các số trên, những số chia hết cho 5 khi a6 = 5, tức là ta có A8 số. Vậy, số các số tìm thấy không chia hết cho 5 là: 5 5 5 6 A8 A8 = 5 A8 = 33600 số. Thí dụ 7. Cho tập A = {0, 1, 2, 3, 4, 5}. Từ tập A có thể lập được bao nhiêu số chẵn, mỗi số gồm 5 chữ số khác nhau ?  Giải Một số gồm 5 chữ số phân biệt hình thành từ tập A có dạng: a1a 2a3a 4a5 , với ai A, i = 1,5 và i j, i j. Để số tìm được là số chẵn, điều kiện là a5 {0, 2, 4}. Ta đi xét hai khả năng: Khả năng 1: Nếu a5 = 0 có 1 cách chọn. Khi đó, mỗi bộ (a1, a2, a3, a4) ứng với một chỉnh hợp chập 4 của các phần tử của 4 tập A\{0} (có 5 phần tử) nên có A5 cách chọn. 4 Như vậy, trong khả năng này, ta được 1. A5 số. Khả năng 2: Nếu a5 { 2, 4} có 2 cách chọn. Tiếp theo: ▪a 1 được chọn từ tập A\{0, a5} (có 4 phần tử) nên có 4 cách chọn. ▪ Mỗi bộ (a2, a3, a4) ứng với một chỉnh hợp chập 3 của các phần tử của tập A\{ 3 a5, a1} (có 4 phần tử) nên có A4 cách chọn. 3 Như vậy, trong khả năng này, ta được 2.4. A4 số. 98
17. Khi đó, số các số chẵn gồm 5 chữ số phân biệt hình thành từ tập A bằng: 4 3 1. A5 + 2.4. A4 = 120 + 192 = 312 số. Thí dụ 8. Cho tập A = {0, 1, 2, 3, 4, 5, 6}. Từ tập A có thể lập được bao nhiêu được bao nhiêu số gồm 5 chữ số khác nhau và trong đó phải có mặt chữ số 5 ?  Giải Một số gồm 5 chữ số phân biệt hình thành từ tập A có dạng: a1a 2a3a 4a5 , với ai A, i = 1,5 và i j, i j. Để số tìm được phải có mặt chữ số 5, ta đi xét hai khả năng: Khả năng 1: Nếu a1 = 5 có 1 cách chọn. Khi đó, mỗi bộ (a2, a3, a4, a5) ứng với một chỉnh hợp chập 4 của các phần tử của tập A\{5} có 6 phần tử. 4 có A6 cách chọn. 4 Như vậy, trong khả năng này, ta được 1. A6 số. Khả năng 2: Nếu 5 { a2, a3, a4, a5} có 4 cách chọn. Tiếp theo: ▪a 1 được chọn từ tập A\{0, 5} - có 5 phần tử có 5 cách chọn. ▪ Mỗi bộ số dành cho ba vị trí còn lại ứng với một chỉnh hợp chập 3 của các phần tử của tập A\{ 5, a1} có 5 phần tử. 3 có A5 cách chọn. 3 Như vậy, trong khả năng này, ta được 4.5.A5 số. Khi đó, số các số gồm 5 chữ số phân biệt trong đó có chữ số 5 hình thành từ tập A bằng: 4 3 1. A6 + 4.5. A5 = 6.5.4.3 + 20.5.4.3 = 1560 số.  Chú ý: Khi đã nắm bắt được bản chất của vấn đề chúng ta có thể trình bày một bài toán đếm theo những lập luận đơn giản hơn. Thí dụ 9. Cho tập A = {0, 1, 2, 3, 4, 5, 6, 7}. a. Từ tập A có thể lập được bao nhiêu số gồm 5 chữ số khác nhau mà mỗi số luôn có mặt hai chữ số 1 và 7 ? b. Trong các số tìm được ở câu a) có bao nhiêu số mà hai chữ số 1 và 7 đứng kề nhau, chữ số 1 bên trái chữ số 7 ?  Giải 99
18. Một số gồm 5 chữ số phân biệt hình thành từ tập A có dạng: a1a 2a3a 4a5 , với ai A, i = 1,5 và i j, i j. a. Nhận xét rằng: 2 ▪ Có A5 cách chọn chữ số 1 và chữ số 7 vào 5 vị trí. ▪ Có 5 cách chọn chữ số tận cùng bên trái (loại các chữ số 0, 1 và 7). 2 ▪ Có A5 cách chọn 2 trong 5 chữ số còn lại vào 2 vị trí còn lại. Do đó, số các số phải tìm là: 2 2 A5 . 5. A5 = 4.5.5.20 = 2000 số. b. Nhận xét rằng " Số cách chọn 2 chữ số 1 và 7 đứng kề nhau, mà chữ số 1 đứng bên trái chữ số 7, trong 1 dãy có 5 vị trí là 4 cách ". Ta sẽ xét 2 khả năng sau: Khả năng 1: Chữ số 1 đứng tận cùng bên trái (hàng chục ngàn) lúc đó chữ số 7 sẽ đứng ở hàng ngàn. Mỗi bộ số dành cho ba vị trí còn lại ứng với một chỉnh hợp chập 3 của các phần tử 3 của tập A\{ 1, 7} (có 6 phần tử) nên có A6 cách chọn. 3 Như vậy, trong khả năng này, ta được 1. A6 số. Khả năng 2: Chữ số 1 đứng ở vị trí khác, tức là có thể ở vị trí hàng ngàn, hàng trăm, hàng chục có 3 cách chọn. Tiếp theo: ▪a 1 được chọn từ tập A\{0, 1, 5} (có 5 phần tử) nên có 5 cách chọn. ▪ Mỗi bộ số dành cho hai vị trí còn lại ứng với một chỉnh hợp chập 2 của các phần 2 tử của tập A\{ 1, 7, a1} (có 5 phần tử) nên có A5 cách chọn. 2 Như vậy, trong khả năng này, ta được 3.5. A5 số. Khi đó, số các số cần tìm bằng: 3 2 1. A6 + 3.5. A5 = 420 số. Thí dụ 10. Cho tập A = {0, 2, 4, 6, 8}. Từ tập A có thể lập được bao nhiêu số gồm 3 chữ số khác nhau ?  Giải Ta có thể lựa chọn một trong hai cách trình bày sau: Cách 1: Sử dụng quy tắc nhân kết hợp với khái niệm chỉnh hợp. Một số gồm 3 chữ số phân biệt hình thành từ tập A có dạng: a1a 2a3 , với ai A, i = 1,3 và i j, i j. Trong đó: ▪a 1 được chọn từ tập A\{0} - có 4 phần tử có 4 cách chọn. ▪ Mỗi bộ (a2, a3) ứng với một chỉnh hợp chập 2 của các phần tử của tập A\{a1} 2 có 4 phần tử có A4 cách chọn. 100