1. Công thức với 3 tập hợp
* Công thức: \( n(A \cup B \cup C) = n(A) + n(B) + n(C) - [n(AB) + n(BC) + n(CA)] + n(ABC) \)
Trong đó: \( n(A), n(B), n(C) \): Số phần tử của từng tập hợp riêng lẻ.
\( n(AB), n(BC), n(CA) \): Số phần tử thuộc về giao của hai tập hợp
\( n(ABC) \): Số phần tử thuộc về giao của cả ba tập hợp
2. Công thức đếm
a) Công thức cơ bản
| Công thức | Đặc điểm | Số cách |
|---|---|---|
| Hoán vị | Sắp xếp \( n \) phần tử khác nhau | \( P_n = n! = 1.2.3 \dots n \) |
| Chỉnh hợp | Chọn ra \( k \) phần tử từ \( n \) phần tử và có sắp xếp thứ tự của \( k \) phần tử đó. | \( A_n^k = \frac{n!}{(n-k)!} \quad (0 \le k \le n) \) |
| Tổ hợp | Chọn \( k \) phần tử từ \( n \) phần tử và không thứ tự. | \( C_n^k = \frac{n!}{k!(n-k)!} \) |
b) Công thức nâng cao
| Công thức | Đặc điểm | Số cách |
|---|---|---|
| Hoán vị vòng quanh | Sắp xếp \( n \) phần tử thành một vòng tròn | \( Q_n = (n-1)! \) |
| Hoán vị lặp | Nếu trong \( n \) phần tử có \( n_1 \) phần tử loại 1, \( n_2 \) phần tử loại 2,... giống hệt nhau | \( P_n(n_1, \dots, n_k) = \frac{n!}{n_1! n_2! \dots n_k!} \) |
| Chỉnh hợp lặp | Chọn \( k \) phần tử từ \( n \) phần tử, trong đó mỗi phần tử có thể được chọn lại nhiều lần | \( F_n^k = n^k \) |
| Vách ngăn loại 1 | Chia \( n \) vật giống nhau cho \( k \) người (mỗi người ít nhất 1 vật) | \( C_{n-1}^{k-1} \) |
| Vách ngăn loại 2 | Chia \( n \) vật giống nhau cho \( k \) người (có thể có người không có) | \( C_{n+k-1}^{k-1} \) |
| Tổ hợp lặp | + Chọn \( k \) phần tử từ \( n \) loại (có lặp, không thứ tự) + Tìm số nghiệm nguyên không âm của \( x_1 + x_2 + \dots + x_n = k \) |
\( C_{n+k-1}^k \) |
| Bổ đề Kaplansky 1 (Dãy hàng ngang) |
Có \( n \) vật thể được sắp xếp thành một hàng ngang. Chọn ra \( k \) vật thể sao cho không có hai vật thể nào đứng cạnh nhau. | \( C_{n-k+1}^k \) (với \( n \ge 2k - 1 \)) |
| Bổ đề Kaplansky 2 (Dãy vòng tròn) |
Có \( n \) vật thể được sắp xếp thành một vòng tròn. Chọn ra \( k \) vật thể sao cho không có hai vật thể nào đứng cạnh nhau. | \( C_{n-k-1}^{k-1} + C_{n-k}^k = \frac{n}{n-k} C_{n-k}^k \) (với \( n \ge 2k \)) |
| Hoán vị sai | Một hoán vị của \( n \) phần tử trong một tập hợp sao cho không có phần tử nào xuất hiện ở vị trí ban đầu của nó. | \( D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \) |
c) Chứng minh các công thức nâng cao
* Hoán vị vòng quanh: \( Q_n = (n-1)! \)
Xếp \( n \) người vào một bàn tròn.
Bước 1: Cố định 1 phần tử bất kỳ vào một vị trí trên vòng tròn để làm "mốc".
Bước 2: Sau khi đã có mốc, \( n-1 \) phần tử còn lại sẽ được xếp vào \( n-1 \) chỗ trống còn lại theo kiểu hàng thẳng.
Bước 3: Số cách xếp \( n-1 \) phần tử vào hàng thẳng là: \( P_{n-1} = (n-1)! \).
* Hoán vị lặp: \( P_n(n_1, n_2, \dots, n_k) = \frac{n!}{n_1! n_2! \dots n_k!} \)
Xếp \( n \) đồ vật vào hàng ngang, trong đó có nhóm các vật giống hệt nhau.
+ Giả sử \( n \) phần tử này khác nhau hoàn toàn, ta có \( n! \) cách xếp.
+ Tuy nhiên, vì \( n_1 \) phần tử loại 1 giống hệt nhau, nên việc hoán đổi vị trí giữa chúng ( \( n_1! \) cách) không tạo ra cách xếp mới. Ta phải chia cho \( n_1! \).
+ Tương tự cho các nhóm còn lại.
* Chỉnh hợp lặp: \( F_n^k = n^k \)
Chọn \( k \) phần tử từ \( n \) phần tử, có sắp xếp và được phép chọn lại (lặp).
+ Vị trí thứ nhất: Có \( n \) cách chọn.
+ Vị trí thứ hai: Vẫn có \( n \) cách chọn (vì được lặp lại).
+ Vị trí thứ \( k \): Có \( n \) cách chọn.
Áp dụng quy tắc nhân: \( \underbrace{n.n \dots n}_{k} = n^k \).
* Vách ngăn loại 1 (Mỗi người ít nhất 1 vật): \( C_{n-1}^{k-1} \)
Bài toán vách ngăn loại 1 và loại 2 còn có tên gọi khác là Bài toán chia kẹo Euler.
Chia \( n \) viên kẹo giống nhau cho \( k \) học sinh sao cho "ai cũng có kẹo".
Trong hình vẽ, ngôi sao thể hiện cho các viên kẹo.
Xếp \( n \) viên kẹo thành một hàng ngang. Giữa \( n \) viên kẹo này có \( n-1 \) khoảng trống.
Để chia thành \( k \) phần (tương ứng \( k \) người), ta cần đặt vào đó \( k-1 \) cái vách ngăn.
Vì mỗi người phải có ít nhất 1 vật, nên mỗi khoảng trống chỉ được đặt tối đa 1 vách ngăn.
Bài toán trở thành: Chọn \( k-1 \) vị trí từ \( n-1 \) khoảng trống để đặt vách ngăn.
Số cách là: \( C_{n-1}^{k-1} \).
* Vách ngăn loại 2 (Có thể có người không có): \( C_{n+k-1}^{k-1} \)
Chia \( n \) vật giống nhau cho \( k \) người, có người có thể không nhận được gì.
Giả sử ta cho mỗi người mượn thêm 1 viên kẹo. Tổng số kẹo bây giờ là \( n+k \).
Bài toán trở thành: Chia \( n+k \) viên kẹo cho \( k \) người sao cho ai cũng có ít nhất 1 viên (để trả lại viên đã mượn và vẫn có thể còn hoặc hết kẹo).
Áp dụng công thức Vách ngăn loại 1 cho \( n+k \) vật và \( k \) người: \( C_{(n+k)-1}^{k-1} = C_{n+k-1}^{k-1} \).
* Tổ hợp lặp: \( C_{n+k-1}^k \)
Giả sử ta cần chọn \( k \) phần tử từ \( n \) loại phần tử khác nhau.
Điều này tương đương với việc chia \( k \) viên kẹo giống hệt nhau vào \( n \) chiếc hộp khác nhau (mỗi hộp đại diện cho một loại phần tử). Số kẹo trong mỗi hộp chính là số lần phần tử loại đó được chọn.
Ta có \( k \) viên kẹo đặt nằm ngang trên một hàng. Để chia \( k \) viên kẹo này thành \( n \) phần, ta cần dùng \( n-1 \) vách ngăn. Tổng số ký tự trong dãy bao gồm cả kẹo và vách ngăn là \( k + (n-1) \).
Bài toán bây giờ trở thành: Trong \( n+k-1 \) vị trí trống, ta chọn ra \( k \) vị trí để đặt các viên kẹo (các vị trí còn lại mặc định là vách ngăn).
Số cách chọn này chính là tổ hợp chập \( k \) của \( n+k-1 \): \( C_{n+k-1}^k \)
* Bổ đề Kaplansky 1 (Dãy hàng ngang): \( C_{n-k+1}^k \)
Chọn \( k \) vật từ \( n \) vật xếp hàng ngang sao cho không có 2 vật nào cạnh nhau.
Gọi \( k \) vật được chọn là các dấu "X" và \( n-k \) vật không được chọn là các dấu "O".
Xếp dấu "O" thành hàng ngang. Giữa chúng và hai đầu có tất cả \( (n-k)+1 \) khoảng trống.
Để \( k \) vật được chọn không cạnh nhau, ta phải đặt mỗi dấu "X" vào một khoảng trống khác nhau.
Bài toán trở thành: Chọn \( k \) vị trí từ \( n-k+1 \) khoảng trống.
Số cách là: \( C_{n-k+1}^k \).
* Bổ đề Kaplansky 2 (Dãy vòng tròn): \( \frac{n}{n-k} C_{n-k}^k \)
Chọn \( k \) vật từ \( n \) vật trên vòng tròn sao cho không có 2 vật nào cạnh nhau.
Đánh số các vật từ 1 đến \( n \).
+ Trường hợp 1: Vật số 1 được chọn. Vậy vật số 2 và vật số \( n \) không được chọn. Ta cần chọn thêm \( k-1 \) vật từ \( n-3 \) vật còn lại (từ số 3 đến \( n-1 \)) sao cho không cạnh nhau trên hàng thẳng.
Số cách: \( C_{(n-3)-(k-1)+1}^{k-1} = C_{n-k-1}^{k-1} \).
+ Trường hợp 2: Vật số 1 không được chọn. Ta cần chọn \( k \) vật từ \( n-1 \) vật còn lại (từ số 2 đến \( n \)) sao cho không cạnh nhau trên hàng thẳng. Số cách: \( C_{(n-1)-k+1}^k = C_{n-k}^k \).
Tổng số cách: \( C_{n-k-1}^{k-1} + C_{n-k}^k \). Sau khi biến đổi đại số, ta được công thức: \( \frac{n}{n-k} C_{n-k}^k \).
* Hoán vị sai: \( D_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right) = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \)
\( n \) lá thư bỏ vào \( n \) phong bì sao cho không lá nào đúng địa chỉ.
Tổng số cách xếp là \( n! \)
Gọi \( A_i \) là tập hợp các cách xếp mà lá thư \( i \) đúng địa chỉ.
Ta cần tìm số phần tử không thuộc bất kỳ tập \( A_i \) nào.
Theo nguyên lý bù trừ: \( D_n = n! - n(A_1 \cup A_2 \cup \dots \cup A_n) \)
\( = n! - \left[ \sum n(A_i) - \sum n(A_i \cap A_j) + \sum n(A_i \cap A_j \cap A_k) - \dots \right] \)
\( = n! - \left( C_n^1 (n-1)! - C_n^2 (n-2)! + C_n^3 (n-3)! - \dots + (-1)^{n-1} C_n^n 0! \right) \)
\( = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right) = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \)
d) Phân biệt 12 công thức đếm
| Nhóm đối tượng | Tên gọi | Khi nào dùng? (Từ khóa nhận diện) |
Công thức |
|---|---|---|---|
| Sắp xếp thứ tự (Lấy \( k=n \)) |
Hoán vị | Sắp xếp tất cả \( n \) vật khác nhau vào \( n \) chỗ. | \( P_n = n! \) |
| Hoán vị vòng quanh | Sắp xếp \( n \) vật thành một vòng tròn. | \( Q_n = (n-1)! \) | |
| Hoán vị lặp | Sắp xếp \( n \) vật nhưng có các nhóm giống hệt nhau. | \( P_n(n_1, n_2, \dots) = \frac{n!}{n_1! n_2! \dots} \) | |
| Hoán vị sai | Không có vật nào ở đúng vị trí ban đầu (xếp nhầm). | \( D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \) | |
| Chọn và xếp thứ tự | Chỉnh hợp | Chọn \( k \) vật từ \( n \) vật và có xếp thứ tự. | \( A_n^k = \frac{n!}{(n-k)!} \) |
| Chỉnh hợp lặp | Chọn \( k \) vật, có thứ tự, một vật có thể chọn lại. | \( F_n^k = n^k \) | |
| Chọn/chia và không xếp thứ tự | Tổ hợp | Chọn một nhóm \( k \) vật, không quan tâm thứ tự. | \( C_n^k = \frac{n!}{k!(n-k)!} \) |
| Vách ngăn (loại 1) | Chia \( n \) kẹo cho \( k \) trẻ, mỗi trẻ ít nhất 1 cái. | \( C_{n-1}^{k-1} \) | |
| Vách ngăn (loại 2) | Chia \( n \) kẹo cho \( k \) trẻ, có trẻ có thể không có. | \( C_{n+k-1}^{k-1} \) | |
| Tổ hợp lặp | Chọn \( k \) vật từ \( n \) loại, không thứ tự, có lặp. | \( C_{n+k-1}^k \) | |
| Chọn không kề nhau | Bổ đề Kaplansky 1 | Chọn \( k \) vật từ \( n \) vật hàng ngang không cạnh nhau. | \( C_{n-k+1}^k \) |
| Bổ đề Kaplansky 2 | Chọn \( k \) vật từ \( n \) vòng tròn không cạnh nhau. | \( \frac{n}{n-k} C_{n-k}^k \) |
Câu 6: Có bao nhiêu cách xếp 10 người thành một hàng ngang để chụp ảnh kỷ niệm?
Lời giải
Mỗi cách xếp thứ tự 10 người là một hoán vị của 10 phần tử.
Số cách xếp là: \( P_{10} = 10! = 3 \ 628 \ 800 \) (cách).
Câu 7: Có bao nhiêu cách xếp 10 người ngồi vào một bàn tròn có 10 ghế?
Lời giải
Vì đây là sắp xếp theo vòng tròn, ta cố định 1 người làm mốc, sau đó sắp xếp 9 người còn lại.
Số cách xếp là: \( Q_{10} = (10-1)! = 9! = 362 \ 880 \) (cách).
Câu 8: Trong 10 người có 5 người mặc áo đỏ, 3 người mặc áo xanh và 2 người mặc áo vàng (các áo cùng màu giống hệt nhau). Có bao nhiêu cách xếp 10 người này thành hàng ngang mà chỉ phân biệt qua màu áo?
Lời giải
Áp dụng công thức hoán vị lặp cho \( n=10 \) với các nhóm lặp lần lượt là 5, 3 và 2.
Số cách xếp là: \( P_{10}(5; 3; 2) = \frac{10!}{5! \ 3! \ 2!} = 2520 \) (cách).
Câu 9: 10 người đi dự tiệc và gửi 10 chiếc mũ ở tủ đồ. Khi ra về, nhân viên trả mũ một cách ngẫu nhiên. Có bao nhiêu trường hợp mà không ai nhận đúng chiếc mũ của mình?
Lời giải
Đây là bài toán hoán vị sai (xếp nhầm) của 10 phần tử.
Số cách là: \( D_{10} = 10! \sum_{k=0}^{10} \frac{(-1)^k}{k!} = 1 \ 334 \ 961 \) (cách).
Câu 10: Từ 10 người, cần bầu ra 1 Trưởng nhóm, 1 Thư ký và 1 Thủ quỹ. Hỏi có bao nhiêu cách chọn (biết mỗi người chỉ giữ một chức vụ)?
Lời giải
Chọn 3 người từ 10 người và có sắp xếp vào 3 vị trí chức vụ khác nhau.
Số cách chọn là: \( A_{10}^3 = \frac{10!}{(10-3)!} = 720 \) (cách).
Câu 11: Có 3 phần quà khác nhau (Giải Nhất, Nhì, Ba). Có bao nhiêu cách trao quà cho 10 người, biết rằng một người có thể nhận được nhiều hơn một giải?
Lời giải
Mỗi phần quà có 10 lựa chọn người nhận, và người đã nhận quà vẫn có thể được chọn lại (lặp).
Số cách trao là: \( F_{10}^3 = 10^3 = 1000 \) (cách).
Câu 12: Từ 10 người, chọn ra một nhóm 3 người để đi làm công tác tình nguyện. Hỏi có bao nhiêu cách?
Lời giải
Đây là chọn một tập con gồm 3 người từ 10 người mà không quan tâm thứ tự.
Số cách chọn là: \( C_{10}^3 = \frac{10!}{3!(10-3)!} = 120 \) (cách).
Câu 13: Có 20 chiếc vé xem phim giống hệt nhau chia cho 10 người sao cho ai cũng có ít nhất 1 vé. Có bao nhiêu cách chia?
Lời giải
Áp dụng bài toán vách ngăn loại 1 (chia \( n \) vật cho \( k \) người, mỗi người ít nhất 1).
Số cách chia là: \( C_{20-1}^{10-1} = C_{19}^9 = 92 \ 378 \) (cách).
Câu 14: Có 20 chiếc vé xem phim giống hệt nhau chia cho 10 người. Hỏi có bao nhiêu cách chia (có người có thể không nhận được vé nào)?
Lời giải
Áp dụng bài toán vách ngăn loại 2 (chia \( n \) vật cho \( k \) người, có thể nhận 0 vật).
Số cách chia là: \( C_{20+10-1}^{10-1} = C_{29}^9 = 10 \ 015 \ 005 \) (cách).
Câu 15: Có 10 loại nước giải khát khác nhau. Một nhóm bạn muốn mua 3 chai nước (có thể mua nhiều chai cùng một loại). Có bao nhiêu cách chọn?
Lời giải
Cách 1. Đây là bài toán chọn \( k=3 \) vật từ \( n=10 \) loại, có lặp và không tính thứ tự.
Số cách chọn là: \( C_{10+3-1}^3 = C_{12}^3 = 220 \) (cách).
Cách 2. Đề bài: Chọn 3 chai nước (có lặp) từ 10 loại khác nhau.
Áp dụng vách ngăn loại 2: \( C_{3+10-1}^{10-1} = C_{12}^9 = 220 \) (cách)
Câu 16: 10 người ngồi trên một hàng ngang gồm 10 ghế. Chọn ra 3 người sao cho không có 2 người nào ngồi cạnh nhau. Có bao nhiêu cách?
Lời giải
Áp dụng bổ đề Kaplansky 1 với \( n=10, k=3 \).
Số cách chọn là: \( C_{10-3+1}^3 = C_8^3 = 56 \) (cách).
Câu 17: 10 người ngồi quanh một bàn tròn. Chọn ra 3 người sao cho không có ai ngồi cạnh nhau. Có bao nhiêu cách?
Lời giải
Áp dụng bổ đề Kaplansky 2 với \( n=10, k=3 \).
Số cách chọn là: \( \frac{10}{10-3} C_{10-3}^3 = \frac{10}{7} C_7^3 = 50 \) (cách).
* Lưu ý 3: Ta thấy bản chất Công thức Vách ngăn loại 2 và Tổ hợp lặp là một.
Thí dụ, ta mua 5 quả từ 3 loại (táo, cam, mận), có loại quả có thể không mua.
+ Theo Tổ hợp lặp: Số loại \( n=3 \), số vật cần chọn \( k=5 \).
Số cách là \( C_{n+k-1}^k = C_{3+5-1}^5 = C_7^5 \)
+ Theo Vách ngăn loại 2: Số vật \( n=5 \), số ngăn (số loại) \( k=3 \).
Số cách là: \( C_{n+k-1}^{k-1} = C_{5+3-1}^{3-1} = C_7^2 = C_7^5 \)
\( C_7^5 \) nghĩa là: Trong 7 vị trí (5 kẹo + 2 vách), bạn chọn 5 chỗ để đặt kẹo.
\( C_7^2 \) nghĩa là: Trong 7 vị trí đó, bạn chọn 2 chỗ để đặt vách ngăn.
Dù ta chọn kẹo hay chọn vách trước thì kết quả cuối cùng vẫn giống nhau.
Để không bao giờ bị loạn giữa các loại công thức, ta chỉ cần nhớ:
|
Trong trường hợp "ai cũng có kẹo": Số cách = \( C_{V-1}^{L-1} \) Trong trường hợp "có thể có người không có kẹo": Số cách = \( C_{V+L-1}^{L-1} \) Trong đó: V : Số vật, L : Số loại/ ngăn/ người, L-1 : Số vách ngăn |
Để tránh nhầm lẫn, tài liệu này chỉ đề cập đến cách giải bằng công thức vách ngăn loại 2.
3. Xác suất cổ điển của biến cố
a) Định nghĩa xác suất cổ điển
Xác suất của biến cố \( A \) là \( P(A) = \frac{n(A)}{n(\Omega)} \)
Trong đó: \( P(A) \) là xác suất của biến cố \( A \)
\( n(A) \) là số phần tử của biến cố \( A \)
\( n(\Omega) \) là số phần tử của không gian mẫu
b) Tính chất
Tính chất 1: \( P(\emptyset) = 0 \); \( P(\Omega) = 1 \)
Tính chất 2: \( 0 \le P(A) \le 1 \) với mỗi biến cố \( A \);
Tính chất 3: \( P(\bar{A}) = 1 - P(A) \) với mỗi biến cố \( A \).
c) Công thức xác suất biến cố hợp giữa A và B
\( P(A \cup B) = P(A) + P(B) - P(A \cap B) \)
