Chương 1 Tổ hợp và Xác suất Trong chương này đưa ra các kiến thức cơ bản về lý thuyết Tổ hợp và Xác suất: phép đếm, hoán vị, tổ hợp, tính chất của tổ hợp, biến cố, xác suất của biến cố, các quy tắc tính xác suất. Bên cạnh những kiến thức đó là những ví dụ về những bài toán thực tế ứng với từng đơn vị kiến thức. Nội dung của chương chủ yếu được hình thành từ các tài liệu [1], [3], [5], [7] và [8]. Quy tắc cộng Nếu có m1 cách chọn đối tượng a1 , m2 cách chọn đối tượng a2 ,.
, mn cách chọn đối tượng an , trong đó cách chọn đối tượng ai (1 ≤ i ≤ n) không phụ thuộc vào bất kì cách chọn đối tượng aj nào (1 ≤ j ≤ n, n X i 6= j), thì sẽ có mk cách chọn đối tượng a1 , hoặc a2 ,. k=1 Để vận dụng có hiệu quả, ta chuyển thể quy tắc này sang ngôn ngữ tập hợp như sau: Cho n tập hợp Ak (1 ≤ k ≤ n) với |Ak | = mk và ∀i, j (1 ≤ i, j ≤ n) Ai ∩ Aj = ∅, khi i 6= j. Khi đó số cách chọn a1 , hoặc a2 ,. , hoặc an sẽ [n n [ Xn bằng số cách chọn phần tử a thuộc Ak và bằng | Ak | = |Ak |.
([3]) Cho tập A = {0; 1; 2; 3; 4; 5} có thể lập được bao 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com nhiêu số có bốn chữ số khác nhau từ tập A và trong mỗi số nhất thiết phải có chữ số 1? Lời giải. Gọi số phải tìm là abcd (a, b, c, d ∈ A; a 6= 0). Vì trong số abcd nhất thiết phải có chữ số 1, nên ta xét các tập A1 , A2 , A3 , A4 là tập các số dạng 1bcd, a1cd, ab1d, abc1 tương ứng. Xét A1 khi lập số 1bcd có: b ∈ A \ {1} có 5 cách chọn.
Bởi vậy, số khả năng lập các số 1bcd là 5. i) Xét A2 khi lập số a1cd có: a ∈ A \ {0, 1} có 4 cách chọn. Bởi vậy, số khả năng lập các số 1bcd là 4. Tương tự, ta có |A3 | = |A4 | = 48.
ii) Vì các số thuộc các dạng khác nhau đều khác nhau, nên ∀i, j (1 ≤ i, j ≤ 4; i 6= j) đều có A1 ∩ Aj = ∅. Bởi vậy, số các số cần tìm được tính bằng quy tắc cộng, nghĩa là bằng |A1 | + |A2 | + |A3 | + |A4 | = 60 + 48 + 48 + 48 = 204. Quy tắc nhân Cho n đối tượng a1 , a2 ,. Nếu có m1 cách chọn đối tượng a1 và với mỗi cách chọn a1 có m2 cách chọn đối tượng a2 , sau đó với mỗi cách chọn a1 , a2 có m3 cách chọn a3 ,.
Cuối cùng với mỗi cách chọn a1 , a2 ,. , an−1 có mn cách chọn đối tượng an. Như vậy sẽ có m1 .mn cách chọn các đối tượng a1 , rồi a2 , rồi a3 ,. Tương tự đối với quy tắc cộng, ta cũng chuyển quy tắc nhân sang dạng ngôn ngữ tập hợp như sau: Giả sử có n tập hợp Ak (1 ≤ k ≤ n) với |Ak | = mk.
Khi đó, số cách 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com chọn (S) bộ gồm n phần tử (a1 , a2 ,. , an ) với ai ∈ Ai (1 ≤ i ≤ n) sẽ là n Y S = |A1 × A2 × · · · × An | = m1 × m2 × · · · × mn = mk. Một bàn dài có hai dãy ghế đối diện nhau, mỗi dãy có 6 chỗ ngồi. Người ta 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 trên.
Hỏi có bao nhiêu cách xếp chỗ ngồi trong mỗi trường hợp sau: i) Bất kì 2 học sinh ngồi cạnh nhau hoặc đối diện nhau thì khác trường. ii) Bất kì 2 học sinh ngồi đối diện nhau thì khác trường. Đánh số các ghế theo hình vẽ sau i) Hai học sinh ngồi cạnh nhau hoặc đối diện nhau thì khác trường. Vậy số cách xếp 2 học sinh ngồi cạnh hoặc đối diện phải khác trường là 12.
ii) Hai học sinh ngồi đối diện thì phải khác trường. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Vậy số cách xếp hai học sinh ngồi đối diện phải khác là 12. Quy tắc trừ Cho A là một tập hữu hạn và B là tập con của A, B là phần bù của B trong A thì ta có |B| = |A − B| = |A| − |B|. Thật vậy, A = B ∪ B và B ∩ B = ∅ nên theo quy tắc cộng ta có |A| = |B| + |B|.
Từ đó suy ra |B| = |A| − |B|. Hoán vị không lặp Định nghĩa 1. Cho một tập hợp gồm n (n ≥ 1) phần tử. Mỗi cách sắp xếp n phần tử này theo một thứ tự nào đó (mỗi phần tử có mặt đúng một lần) được gọi là một hoán vị của n phần tử đã cho.
Kí hiệu số hoán vị của n phần tử bằng Pn. Ta có công thức Pn = n! = n(n − 1). Với năm chữ số 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm năm chữ số khác nhau? Lời giải. Vì số cần lập có năm chữ số khác nhau, mỗi chữ số xuất hiện trong từng số cần lập đúng một lần, nên mỗi số cần lập là một hoán vị 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com của năm số đã cho.
Bởi vậy, số các số có thể lập bằng số hoán vị của năm phần tử, tức là P5 = 5! = 120. Hoán vị có lặp Định nghĩa 1. Hoán vị trong đó mỗi phần tử xuất hiện ít nhất một lần được gọi là hoán vị lặp. Số hoán vị lặp của n phần tử thuộc k loại, mà các phần tử loại i (1 ≤ i ≤ k) xuất hiện ni lần được kí hiệu là P (n1 , n2 , ., nk ) và được tính bằng công thức n! P (n1 , n2 ,.
nk ! Thậy vậy, xét một hoán vị có lặp của n phần tử thuộc loại k , mà các phần tử loại i (1 ≤ i ≤ k) xuất hiện ni lần. Nếu ta thay thế tất cả các phần tử giống nhau bằng những phần tử khác nhau, thì số hoán vị khác nhau của n phần tử giống nhau mà ta có thể lập được từ hoán vị có lặp đang xét theo quy tắc nhân bằng n1 !n2 !. Làm như vậy cho mỗi hoán vị có lặp của n phần tử thuộc loại k , mà các phần tử loại i (1 ≤ i ≤ k) xuất hiện ni , ta sẽ tìm được tất cả n! hoán vị của n phần tử khác nhau. Do đó ta có đẳng thức P (n1 , n2 ,.
Từ đó suy ra n! P (n1 , n2 ,. ([3]) Với các chữ số 0, 1, 2, 3, 4, 5 có thể lập được bao nhiêu số gồm chín chữ số, trong đó mỗi chữ số 0, 1, 2, 3 xuất hiện đúng một lần, chữ số 4 xuất hiện đúng hai lần và chữ số 5 xuất hiện đúng ba lần? Lời giải. Xét một số x tùy ý, x = 140525345 và kí hiệu vị trí các chữ số của x một cách hình thức, ta có: x = a1 a2 a3 a4 a5 a6 a7 a8 a9 (trong đó a1 6= 0 và các vị trí còn lại thỏa mãn yêu cầu bài toán). Khi đó, mỗi số x tương ứng với một hoán vị của chín phần tử a1 , a2 , a3 , a4 , a5 , a6 , a7 , a8 , a9.
9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Số các hoán vị khác của chín phần tử ai (1 ≤ i ≤ 9) là 9! do a2 = a8 = 4, nên khi đổi chỗ a2 và a8 cho nhau, thì hoán vị a1 a2 a3 a4 a5 a6 a7 a8 a9 vẫn chỉ cho số x. Tương tự, đổi chỗ hai trong ba phần tử a4 , a6 , a9 cho nhau vẫn chỉ cho ta số x. Như vậy, khi ta thực hiện 2! hoán vị a2 , a8 và 3! hoán vị a4 , a6 , a9 , ta chỉ được một số cần tìm x. Vậy số các số có thể lập được là 9! S= = 30240.
Mặt khác, theo công thức trên, số hoán vị có lặp của n! hai phần tử của n phần tử là (k, n − k) bằng · k!(n − k)! Số này chính là Cnk (tổ hợp chập k của n phần tử đã cho). Vậy số hoán vị có lặp của hai phần tử của n phần tử là k, (n − k) bằng tổ hợp chập k của n phần tử. Thật vậy, chứng minh đẳng thức này không dựa vào công thức hoán vị có lặp của n phần tử thuộc k loại, mà các phần tử thuộc loại k (0 ≤ k ≤ n) xuất hiện nk lần. Một hoán vị có lặp của hai phần tử của n phần tử là (k, n − k) được tạo thành bởi k phần tử và n − k phần tử.
Nó hoàn toàn xác định bởi cách chọn vị trí của phần tử thứ nhất. Vì tổng số vị trí bằng k + n − k = n, và phần tử thứ nhất chiếm k vị trí, nên có thể chọn các vị trí theo Cnk cách. ([8]) Có bao nhiêu cách đặt 2 đèn xanh và 4 đèn đỏ thành một hàng? Lời giải. Mỗi cách đặt 2 đèn xanh và 4 đèn đỏ thành một hàng là một hoán vị có lặp của hai phần tử của 6 phần tử là (2, 4).
Vậy số cách đặt 2 đèn và 4 đèn thành một hàng bằng số hoán vị lặp hai phần tử của 6 phần tử là (2, 4) và bằng 6.2 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Vậy có 15 cách đặt hai đèn xanh và bốn đèn đỏ thành một hàng. Hoán vị vòng quanh Định nghĩa 1. Cho n phần tử, số hoán vị vòng quanh của n phần tử khác nhau (Qn ) được tính bằng công thức Qn = (n − 1)!. ([8]) Một hội nghị bàn tròn có năm nước tham gia: Anh có 3 đại biểu, Pháp có 5 đại biểu, Đức có 2 đại biểu, Nhật có 3 đại biểu và Mỹ có 4 đại biểu.
Hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho các đại biểu sao cho 2 người cùng quốc tịch ngồi cùng nhau? Lời giải. Đầu tiên ta sắp xếp khu vực cho đại biểu từng nước. Ta mời một phái đoàn nào đó ngồi vào chỗ trước. Khi đó, bốn phái đoàn còn lại có 4! cách sắp xếp.