Bỏ qua đến nội dung chính
Mục lục

Hoán vị, chỉnh hợp, tổ hợp: math.comb(), math.perm()

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 2/11 · Chương 4

Xác suất

  • 9 phút
  • Cơ bản
  • Python 3.14
  • Cập nhật

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.

python
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:

Ank=n(n−1)…(n−k+1)=n!(n−k)!A_n^k = n(n-1)\ldots(n-k+1) = \frac{n!}{(n-k)!}

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!:

Cnk=Ankk!=n!k! (n−k)!C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!\,(n-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.

python
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:

python
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ô.

python
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.

python
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: 0

Lầ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

  1. Sau import math, print(math.comb(6, 2)) in ra gì?

    • 30
    • 15
    • 12
    • 36
  2. Trong khung bẫy vé 6/45, vì sao math.perm(45, 6) gấp đúng 720 lần math.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
  3. 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
  4. Trong mô phỏng 20.000 lần quay, vì sao không lần nào trúng giải nhất?

    • Vì argsort khô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
Đúng hết lần đầu +15 XP

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.

python
def so_cach_chon(n, k, co_thu_tu):
    pass  # Viết thân hàm thay cho dòng này

Tó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ố đó; itertools liệ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ủ đề

hoán vị chỉnh hợp tổ hợp

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

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.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập