Tổ hợp và xác suất

Xác suất tổ hợp

Theo định nghĩa cổ điển, xác suất của biến cố A là P(A)=\dfrac{n(A)}{n(\Omega)}, trong đó n(\Omega) là số kết quả đồng khả năng và n(A) là số kết quả thuận lợi cho A. Khi lấy đồng thời (không phân biệt thứ tự) k phần tử từ tập n phần tử, mỗi cách lấy là một tổ hợp chập k, nên n(\Omega)=C_n^k; các kết quả thuận lợi cũng được đếm bằng tổ hợp, nên xác suất là tỉ số giữa hai tổ hợp.

Nếu trong n phần tử có m phần tử thuộc một loại, xác suất lấy được k phần tử đều thuộc loại đó là \dfrac{C_m^k}{C_n^k}. Đây là dạng thường gặp khi lấy ngẫu nhiên đồng thời vài vật từ một hộp có nhiều màu.

Với biến cố kiểu 'có ít nhất một phần tử thuộc loại nào đó' hoặc 'có cả hai loại', thường dễ đếm biến cố đối (tất cả thuộc cùng một loại) rồi dùng P(A)=1-P(\overline{A}).

Khi điều kiện liên quan đến tính chẵn lẻ của tổng, hai số có tổng chẵn khi và chỉ khi cùng tính chẵn lẻ; ta đếm từng trường hợp (cùng chẵn, cùng lẻ) rồi cộng lại theo quy tắc cộng.

Khi lập số có các chữ số đôi một khác nhau và có điều kiện về tính chẵn lẻ của các chữ số kề nhau, ta phân loại theo số lượng chữ số lẻ, xác định số cách đặt các chữ số lẻ thỏa điều kiện (không đứng cạnh nhau), rồi nhân với số cách xếp các chữ số còn lại.

Khi đếm số trong một đoạn thỏa điều kiện so sánh các chữ số, liệt kê theo từng giá trị của chữ số hàng chục rồi đếm các chữ số hàng đơn vị lớn hơn nó, sau đó cộng các trường hợp lại.

Khi nhiều phép chọn độc lập được thực hiện và điều kiện nói về số dư khi chia cho 3 của tổng, ta phân các số thành các lớp theo số dư, đếm các bộ có tổng số dư chia hết cho 3 theo tổ hợp của các lớp và số cách chọn trong mỗi lớp.

Khi đếm các tam giác tạo bởi các điểm trên hai tia chung gốc, ta đếm tất cả các bộ ba điểm rồi trừ đi các bộ ba thẳng hàng trên mỗi tia, chú ý không đếm trùng khi hai đường thẳng có chung điểm gốc.

Chỉnh hợp

Chỉnh hợp chập k của n phần tử là cách chọn k phần tử khác nhau từ n phần tử và sắp xếp chúng theo một thứ tự, ký hiệu A_n^k, với 0\le k\le n. Công thức: A_n^k=\dfrac{n!}{(n-k)!}=n(n-1)\cdots(n-k+1).

Điểm mấu chốt là thứ tự có quan trọng. Lập số tự nhiên gồm các chữ số khác nhau từ một tập chữ số là chỉnh hợp, vì đổi chỗ hai chữ số cho nhau cho một số khác. Ví dụ, số các số có hai chữ số khác nhau lập từ m chữ số khác nhau là A_m^2=m(m-1).

Khi phải chọn và xếp k phần tử khác nhau vào k vị trí được phân biệt với nhau, số cách là A_n^k; chẳng hạn chọn và xếp 6 phần tử từ 9 phần tử vào 6 vị trí có 9\cdot8\cdot7\cdot6\cdot5\cdot4=A_9^6 cách.

Tổ hợp chập k

Tổ hợp chập k của n phần tử là một tập con gồm k phần tử, không phân biệt thứ tự, ký hiệu C_n^k=\dfrac{n!}{k!\,(n-k)!} với 0\le k\le n. Các tính chất hay dùng: C_n^k=C_n^{n-k}, C_n^0=C_n^n=1.

Phân biệt với chỉnh hợp: khi chỉ chọn ra một nhóm (chọn đội, chọn ban) thì dùng tổ hợp; khi các vị trí có vai trò khác nhau (chủ tịch, phó chủ tịch) thì dùng chỉnh hợp, và số chỉnh hợp bằng số tổ hợp nhân với k!. Chọn 2 người từ 7 người không phân biệt thứ tự là C_7^2=21 cách.

Ba đỉnh bất kỳ của một đa giác lồi không thẳng hàng, nên số tam giác có ba đỉnh lấy từ các đỉnh của đa giác lồi bằng số tổ hợp chập 3 của số đỉnh.

Trong bài toán chọn vị trí cho các vật thuộc cùng một loại (ví dụ các bóng cùng màu được đặt vào một tập vị trí), số cách chọn k vị trí trong n vị trí là C_n^k; nếu các vật khác nhau thì mỗi cách còn nhân với số cách xếp các vật trong từng nhóm.

Hoán vị

Hoán vị của n phần tử khác nhau là cách sắp xếp cả n phần tử theo một thứ tự; số hoán vị là P_n=n!=n(n-1)\cdots 1, với quy ước 0!=1. Đây là trường hợp đặc biệt của chỉnh hợp khi k=n.

Xếp n người thành một hàng dọc có n! cách, vì vị trí đầu, vị trí thứ hai, … được chọn lần lượt, không lặp lại.

Lập số có đủ n chữ số khác nhau từ đúng n chữ số cho trước là hoán vị của n chữ số đó, nên có n! số.

Khi các phần tử được chia thành nhiều nhóm và mỗi nhóm được xếp vào một tập vị trí cố định, số cách bằng tích các giai thừa của số phần tử trong từng nhóm, vì hoán vị bên trong mỗi nhóm được tính độc lập theo quy tắc nhân.

Quy tắc nhân đếm

Quy tắc nhân: nếu một công việc gồm hai giai đoạn liên tiếp, giai đoạn thứ nhất có m cách và giai đoạn thứ hai có n cách không phụ thuộc vào giai đoạn thứ nhất, thì có m\cdot n cách thực hiện. Chẳng hạn chọn một nam và một nữ từ hai nhóm riêng biệt có số cách bằng tích số nam và số nữ.

Quy tắc cộng: nếu các trường hợp không giao nhau thì tổng số cách bằng tổng số cách của từng trường hợp. Khi một điều kiện chia thành nhiều trường hợp rời nhau, ta đếm từng trường hợp rồi cộng lại.

Khi chia một dãy n phần tử đã sắp thứ tự thành k đoạn liên tiếp không rỗng, số cách là C_{n-1}^{k-1}, vì chỉ cần chọn k-1 vị trí làm vách ngăn trong n-1 khoảng trống giữa các phần tử. Kết hợp với việc hoán vị các vật khác nhau, ta đếm được số cách xếp các vật vào các ngăn có thứ tự, mỗi ngăn không rỗng.

Mẫu số liệu ghép nhóm

Mẫu số liệu ghép nhóm gồm các nhóm [a_i;a_{i+1}) với tần số n_i; cỡ mẫu là n=\sum n_i. Để tìm tứ phân vị và trung vị, trước hết xác định nhóm chứa vị trí cần tìm nhờ tần số cộng dồn: vị trí của Q_1, Q_2, Q_3 lần lượt là \dfrac{n}{4}, \dfrac{n}{2}, \dfrac{3n}{4} tính theo thứ tự tăng dần của số liệu.

Nếu nhóm m chứa vị trí p, gọi C là tần số cộng dồn ngay trước nhóm m, h là độ rộng nhóm và n_m là tần số của nhóm m, thì giá trị cần tìm được nội suy là a_m+\dfrac{p-C}{n_m}\cdot h. Trung vị là M_e=a_m+\dfrac{\frac{n}{2}-C}{n_m}\cdot h và Q_3=a_m+\dfrac{\frac{3n}{4}-C}{n_m}\cdot h khi \frac{3n}{4} thuộc nhóm m.

Trung vị luôn thuộc nhóm đầu tiên có tần số cộng dồn đạt ít nhất \dfrac{n}{2}; để xác định nhóm chứa trung vị chỉ cần so sánh các tần số cộng dồn với \dfrac{n}{2}.

Xác suất có điều kiện

Xác suất của biến cố B khi biết biến cố A đã xảy ra (với P(A)>0) là P(B\mid A)=\dfrac{P(AB)}{P(A)}; suy ra P(AB)=P(A)\cdot P(B\mid A).

Với biến cố đối trong điều kiện A, ta có P(\overline{B}\mid A)=1-P(B\mid A). Đây là điểm dễ nhầm khi đề cho tỉ lệ 'không' trong một nhóm đã chọn.

Khi dữ liệu cho dưới dạng bảng hai chiều (số phần tử có hoặc không có từng dấu hiệu), P(B\mid A) bằng số phần tử thuộc cả A và B chia cho số phần tử của A, không chia cho tổng số phần tử của toàn bộ bảng.

Nếu A và \overline{A} tạo thành một hệ đầy đủ thì P(B)=P(B\mid A)P(A)+P(B\mid \overline{A})P(\overline{A}) (công thức xác suất toàn phần). Với tỉ lệ cho trước theo từng điều kiện, ta dùng công thức này để tính xác suất trung gian rồi áp dụng định nghĩa xác suất có điều kiện.

Khai triển nhị thức Newton

Công thức nhị thức Newton: (a+b)^n=\sum_{k=0}^{n}C_n^k\,a^{n-k}b^k, số hạng tổng quát là T_{k+1}=C_n^k a^{n-k}b^k. Trong (ax+b)^n, số hạng chứa x^m ứng với k=n-m, có hệ số C_n^{m}\,a^m b^{n-m}; dấu của hệ số phụ thuộc vào dấu của b được lũy thừa.

Khi biểu thức là tổng hoặc tích của nhiều khai triển, hệ số của x^m bằng tổng các hệ số của x^m từ từng phần. Đặc biệt, hệ số của x^m trong x\cdot P(x) bằng hệ số của x^{m-1} trong P(x).

Số đặc trưng mẫu số liệu

Số trung bình của mẫu x_1,\dots,x_n là \bar{x}=\dfrac{1}{n}\sum x_i; với số liệu có tần số n_i thì \bar{x}=\dfrac{1}{n}\sum n_i x_i. Phương sai là s^2=\dfrac{1}{n}\sum n_i(x_i-\bar{x})^2, bằng \overline{x^2}-\bar{x}^2; độ lệch chuẩn là căn bậc hai của phương sai.

Trong bài toán về giá cả, nếu tổng tiền mỗi ngày bằng tổng của số lượng nhân với đơn giá và đơn giá không đổi, ta lập hệ phương trình tuyến tính theo các đơn giá từ các ngày đã biết, giải hệ để tìm đơn giá rồi tính số tiền cho ngày chưa biết; phương trình còn lại dùng để kiểm tra nghiệm.

Biến cố độc lập

Hai biến cố A và B độc lập khi việc A xảy ra hay không không làm thay đổi xác suất của B; khi đó P(AB)=P(A)\cdot P(B) và P(B\mid A)=P(B).

Lưu ý: hai biến cố xung khắc (không thể cùng xảy ra) với xác suất dương thì không độc lập, vì P(AB)=0\neq P(A)P(B). Nếu A và B độc lập thì A và \overline{B} cũng độc lập.

Xác suất có điều kiện

Xác suất có điều kiện của biến cố A khi đã biết biến cố B xảy ra, ký hiệu P(A\mid B), được định nghĩa với P(B)>0 bởi P(A\mid B)=\dfrac{P(A\cap B)}{P(B)}. Khi biết B đã xảy ra, không gian mẫu thu hẹp lại thành các kết quả thuộc B, nên mẫu số là P(B) chứ không phải 1.

Với các kết quả đồng khả năng, công thức trên có dạng P(A\mid B)=\dfrac{n(AB)}{n(B)}: lấy số kết quả thuộc B làm mẫu và số kết quả thuộc cả A lẫn B làm tử. Ví dụ: trong nhóm 20 người có 8 người biết bơi, trong đó 5 người là nữ; chọn ngẫu nhiên một người trong số biết bơi thì xác suất người đó là nữ bằng \dfrac{5}{8}. Cách đếm này cũng áp dụng khi điều kiện là tính chất của cặp đã lấy, chẳng hạn “hai viên khác màu”.

Khi lấy liên tiếp không hoàn lại, kết quả lần sau phụ thuộc lần trước. Sau mỗi lần lấy, tổng số phần tử còn lại giảm đi 1; nếu lần đầu lấy ra phần tử không thuộc loại X thì số phần tử loại X không đổi, nên xác suất lần sau lấy được loại X bằng số phần tử loại X chia cho tổng còn lại.