Hoán vị, chỉnh hợp, tổ hợp: math.comb(), math.perm()
Bài 2/11 · Chương 4
Xác suất
- 9 phút
- Cơ bản
- Python 3.14
- Cập nhật
Trong bài này · 12
Hoán vị, chỉnh hợp, tổ hợp là ba cách đếm mà không liệt kê: hoán vị xếp cả n phần tử, chỉnh hợp chọn k phần tử có kể thứ tự, tổ hợp chọn k phần tử không kể thứ tự. Bạn cần chúng mỗi khi tính xác suất mà không gian mẫu quá lớn để đếm tay, như số cách chọn sáu số của một tờ vé 6/45.
Cần biết trước: xác suất là gì, itertools và bảng hàm math.
Quy tắc nhân: đếm từng bước một
Quán cà phê chi nhánh Huế cho khách chọn một đồ uống trong bốn món, một loại bánh trong ba loại, và cỡ ly vừa hay lớn. Một phần ăn là ba lựa chọn liên tiếp, và mỗi lựa chọn không làm đổi số cách của lựa chọn sau, nên số phần ăn là tích: 4 × 3 × 2 = 24. Đó là quy tắc nhân (rule of product). Khi việc chia thành các trường hợp không chồng nhau (đồ uống nóng hoặc đồ uống lạnh), bạn cộng số cách của từng trường hợp: quy tắc cộng.
import itertools
do_uong = ["Cà phê sữa", "Bạc xỉu", "Trà đào", "Sinh tố bơ"]
banh = ["Bánh mì", "Croissant", "Bánh flan"]
co_ly = ["Vừa", "Lớn"]
phan_an = list(itertools.product(do_uong, banh, co_ly))
print(len(phan_an), len(do_uong) * len(banh) * len(co_ly))
print(phan_an[0])
print(phan_an[-1])KẾT QUẢ
24 24
('Cà phê sữa', 'Bánh mì', 'Vừa')
('Sinh tố bơ', 'Bánh flan', 'Lớn')Liệt kê bằng itertools.product() và nhân ba độ dài cho cùng 24. Liệt kê chỉ cần để kiểm; khi số cách lên tới hàng triệu, bạn nhân.
Công thức hoán vị, chỉnh hợp, tổ hợp
Lan, Minh, Hà, Tùng, Vy là năm bạn trong tổ. Ba câu hỏi khác nhau ở chỗ thứ tự có làm ra một cách mới hay không:
Xếp cả năm bạn vào một hàng ghế: hoán vị (permutation) của 5, có 5! = 5 × 4 × 3 × 2 × 1 = 120 cách.
Chọn hai bạn làm tổ trưởng và tổ phó: chỉnh hợp chập 2 của 5. (Lan, Minh) khác (Minh, Lan).
Chọn hai bạn đi trực nhật: tổ hợp (combination) chập 2 của 5. {Lan, Minh} và {Minh, Lan} là một cách.
Chỉnh hợp chập k của n là tích k số đi xuống từ n, theo quy tắc nhân:
Trong đó:
n(n): số phần tử để chọn;k(k): số phần tử được chọn, từ 0 đến n.n! (
math.factorial(n)): tích 1 × 2 × … × n, quy ước 0! = 1.Aₙᵏ (
math.perm(n, k)): số chỉnh hợp chập k của n.
Tổ hợp bỏ thứ tự đi: mỗi nhóm k người được đếm k! lần trong chỉnh hợp, nên chia cho k!:
Trong đó:
k! (
math.factorial(k)): số thứ tự xếp được của một nhóm k phần tử.Cₙᵏ (
math.comb(n, k)): số tổ hợp chập k của n.
SGK Toán 10 (chương trình 2018) dùng đúng ký hiệu này, viết số hoán vị là Pₙ = n!; sách tiếng Anh hay viết C(n, k) và đọc "n chọn k".
Tính tay hai câu hỏi về tổ năm bạn, k = 2:
Bước | Việc | Kết quả |
|---|---|---|
1 | Chọn tổ trưởng: 5 cách; còn 4 bạn cho tổ phó | A = 5 × 4 = 20 |
2 | Mỗi cặp hai bạn được đếm 2! = 2 lần ở bước 1 | 2 |
3 | Chia | C = 20 / 2 = 10 |
Khối dưới tính đúng như bảng bằng vòng lặp, không thư viện. Sửa n và k rồi bấm Chạy để đếm cho tổ của bạn.
n, k = 5, 2
chinh_hop = 1
for i in range(k):
chinh_hop *= n - i
print("Nhân thêm", n - i, "được", chinh_hop)
giai_thua_k = 1
for i in range(1, k + 1):
giai_thua_k *= i
print("A =", chinh_hop, " k! =", giai_thua_k)
print("C =", chinh_hop // giai_thua_k)KẾT QUẢ
Nhân thêm 5 được 5
Nhân thêm 4 được 20
A = 20 k! = 2
C = 10Đổi n, k = 5, 2 thành n, k = 6, 3 rồi chạy lại: dòng cuối in C = 20.
Đếm bằng math.perm(), math.comb() và itertools
Module math có sẵn ba hàm: math.factorial(n), math.perm(n, k) (chỉnh hợp; math.perm(n) là hoán vị) và math.comb(n, k) (tổ hợp). itertools.permutations() và itertools.combinations() liệt kê chính các cách chọn, để bạn thấy chúng. Cùng tổ năm bạn:
import itertools
import math
to = ["Lan", "Minh", "Hà", "Tùng", "Vy"]
print(math.factorial(5), math.perm(5))
print(math.perm(5, 2), math.comb(5, 2))
cap_co_thu_tu = list(itertools.permutations(to, 2))
cap_khong_thu_tu = list(itertools.combinations(to, 2))
print(len(cap_co_thu_tu), len(cap_khong_thu_tu))
print(cap_co_thu_tu[:2])
print(cap_khong_thu_tu[:2])KẾT QUẢ
120 120
20 10
20 10
[('Lan', 'Minh'), ('Lan', 'Hà')]
[('Lan', 'Minh'), ('Lan', 'Hà')]Số 20 và 10 khớp bảng tính tay. permutations có cả ('Lan', 'Minh') lẫn ('Minh', 'Lan') ở phía sau; combinations chỉ giữ một. Trong Excel: PERMUT(5, 2) và COMBIN(5, 2).
Xác suất trúng giải 6/45 bằng tổ hợp
Máy quay sáu số khác nhau trong 45 số; mọi bộ sáu số đồng khả năng, nên Ω có C(45, 6) kết quả. Trúng giải nhất là đúng một bộ, nên xác suất là 1 / C(45, 6). Trúng đúng k số thì theo quy tắc nhân: chọn k số trong sáu số của bạn, và 6 − k số còn lại trong 39 số bạn không tô.
import math
omega = math.comb(45, 6)
print(f"Số bộ sáu số: {omega:,}")
print(f"Giải nhất: 1 / {omega:,}")
for k in [3, 4, 5, 6]:
thuan_loi = math.comb(6, k) * math.comb(39, 6 - k)
print(k, "số:", f"{thuan_loi / omega:.7%}")KẾT QUẢ
Số bộ sáu số: 8,145,060
Giải nhất: 1 / 8,145,060
3 số: 2.2440596%
4 số: 0.1364631%
5 số: 0.0028729%
6 số: 0.0000123%Trúng đúng 3 số khoảng 2,2%, giải nhất khoảng 0,0000123%. Mô phỏng kiểm được con số 2,2%: khối dưới cho 20.000 lần quay, mỗi lần xáo 45 số bằng argsort của một hàng số ngẫu nhiên, lấy sáu số đầu. Rồi khối đếm số trùng với tờ vé 1, 2, 3, 4, 5, 6.
import math
import numpy as np
rng = np.random.default_rng(28)
xao = np.argsort(rng.random((20_000, 45)), axis=1)
ket_qua = xao[:, :6] + 1
so_trung = (ket_qua <= 6).sum(axis=1)
print("Mô phỏng, trúng đúng 3:", round((so_trung == 3).mean(), 4))
ly_thuyet = math.comb(6, 3) * math.comb(39, 3) / math.comb(45, 6)
print("Công thức:", round(ly_thuyet, 4))
print("Số lần trúng giải nhất:", int((so_trung == 6).sum()))KẾT QUẢ
Mô phỏng, trúng đúng 3: 0.0212
Công thức: 0.0224
Số lần trúng giải nhất: 0Lần chạy này cho tần suất trúng 3 số lệch công thức khoảng một phần nghìn. Không lần quay nào trúng giải nhất: với xác suất một phần tám triệu, 20.000 lần quay gần như chắc chắn ra số 0. Biến cố hiếm như vậy phải tính bằng đếm. Đổi default_rng(28) thành default_rng(6) để thấy tần suất trúng 3 số đổi chút ít.
Kiểm tra nhanh
Sau
import math,print(math.comb(6, 2))in ra gì?30151236
Trong khung bẫy vé 6/45, vì sao
math.perm(45, 6)gấp đúng 720 lầnmath.comb(45, 6)?- Vì 45 số có 720 cách xếp
- Vì
math.perm()đếm cả bộ có số trùng nhau - Vì mỗi bộ sáu số được chỉnh hợp đếm 6! = 720 lần, một lần cho mỗi thứ tự
- Vì máy quay số theo thứ tự tăng dần
Những việc nào đếm bằng tổ hợp?
- Chọn ba bạn đi trực nhật trong tổ năm bạn
- Chọn tổ trưởng và tổ phó trong tổ năm bạn
- Chọn sáu số cho một tờ vé 6/45
- Xếp năm bạn vào năm ghế một hàng
Trong mô phỏng 20.000 lần quay, vì sao không lần nào trúng giải nhất?
- Vì
argsortkhông bao giờ đưa số 1 đến 6 lên đầu - Vì xác suất trúng giải nhất chỉ khoảng một phần tám triệu, quá nhỏ so với 20.000 lần
- Vì hạt giống 28 là hạt giống không may
- Vì xác suất trúng giải nhất bằng 0
- Vì
Bài tập
Đếm số cách chọn có và không kể thứ tự
Bạn viết hàm đếm cho một công cụ chia ca trực nhật. n là số người (n >= 0), k là số người được chọn (k >= 0, có thể lớn hơn n), co_thu_tu là True khi người được chọn nhận vai khác nhau. Viết thân hàm so_cach_chon(n, k, co_thu_tu) bằng quy tắc nhân: số chỉnh hợp khi co_thu_tu là True, số tổ hợp khi là False.
Không dùng math.comb(), math.perm(), math.factorial() hay module itertools.
Trả về: số cách chọn, một int (bằng 0 khi k > n).
Ví dụ so_cach_chon(5, 2, True) cho 20, so_cach_chon(5, 2, False) cho 10.
def so_cach_chon(n, k, co_thu_tu):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Quy tắc nhân: việc làm qua nhiều bước liên tiếp thì số cách là tích số cách của từng bước.
Hoán vị xếp cả n phần tử (n!), chỉnh hợp chọn k có thứ tự (n!/(n − k)!), tổ hợp chọn k không thứ tự (chia thêm k!).
math.perm(n, k),math.comb(n, k),math.factorial(n)cho đúng ba số đó;itertoolsliệt kê các cách để kiểm.Dùng chỉnh hợp khi thứ tự không quan trọng làm số cách lớn gấp k! lần mà Python không báo.
Xác suất trúng giải nhất 6/45 là 1 / C(45, 6) = 1 / 8.145.060; biến cố hiếm như vậy tính bằng đếm, không đo được bằng một mô phỏng nhỏ.
Câu hỏi thường gặp
Công thức tổ hợp dùng trong xác suất thế nào?
Tổ hợp đếm cả |Ω| lẫn |A| khi phép thử là chọn một nhóm không kể thứ tự; rồi bạn chia như trong bài xác suất là gì. Ví dụ trúng đúng 3 số của vé 6/45 là C(6, 3) · C(39, 3) / C(45, 6), khoảng 2,2%.
Phân biệt chỉnh hợp và tổ hợp thế nào cho nhanh?
Đổi chỗ hai phần tử đã chọn: ra một cách khác thì là chỉnh hợp (tổ trưởng và tổ phó), vẫn là cách cũ thì là tổ hợp (nhóm trực nhật). Hoán vị là chỉnh hợp chọn đủ cả n.
Hàm math.comb() trong Python có từ phiên bản nào?
math.comb() và math.perm() có từ Python 3.8, nên mọi bản Python hiện hành đều có. Bài bảng hàm math liệt kê chúng cạnh factorial(), gcd() và các hàm số học khác.
Có chỉnh hợp lặp, tổ hợp lặp trong Python không?
Có: chỉnh hợp lặp chập k của n là nᵏ cách, liệt kê bằng itertools.product(..., repeat=k) như hai con xúc xắc; tổ hợp lặp liệt kê bằng itertools.combinations_with_replacement(). Bài itertools dạy các hàm này.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.