Đếm (Counting)¶

Đếm là tiền đề để tính xác suất — bạn phải biết có bao nhiêu kết quả trước khi có thể gán khả năng xảy ra. File này bao gồm quy tắc nhân và quy tắc cộng, giai thừa, hoán vị, tổ hợp, và hệ số nhị thức — các công cụ tổ hợp làm nền tảng cho lấy mẫu, băm và phân tích xác suất trong ML.

Trước khi tính xác suất, ta cần đếm số kết quả. Nếu bạn muốn biết cơ hội rút được bài thắng trong poker, trước hết bạn cần biết có bao nhiêu bộ bài khả dĩ và bao nhiêu trong số đó là bộ thắng. Đếm là cỗ máy làm cho xác suất trở nên chính xác.
Nguyên tắc đếm đơn giản nhất là quy tắc nhân (multiplication rule). Nếu một quyết định có \(m\) lựa chọn và một quyết định độc lập thứ hai có \(n\) lựa chọn, tổng số kết quả kết hợp là \(m \times n\).
Hãy hình dung việc mặc quần áo buổi sáng. Bạn có 3 áo và 4 quần. Mỗi áo có thể ghép với mỗi quần, cho bạn \(3 \times 4 = 12\) bộ trang phục khả dĩ.

Sơ đồ cây minh hoạ 3 áo nhân 4 quần bằng 12 bộ trang phục

Quy tắc nhân mở rộng cho bất kỳ số lượng lựa chọn nào. Nếu bạn cũng có 2 đôi giày, tổng số bộ trang phục trở thành \(3 \times 4 \times 2 = 24\). Mỗi lựa chọn độc lập mới nhân lên số lượng.
Quy tắc cộng (addition rule) xử lý các tình huống "hoặc". Nếu biến cố A có thể xảy ra theo \(m\) cách và biến cố B có thể xảy ra theo \(n\) cách, và chúng không thể xảy ra đồng thời (xung khắc lẫn nhau), tổng số cách là \(m + n\).
Giả sử bạn có thể đi từ thành phố X đến thành phố Y bằng ô tô (3 tuyến) hoặc bằng tàu (2 tuyến). Bạn không thể đi cả hai cùng lúc, vậy tổng số lựa chọn là \(3 + 2 = 5\).
Khi các biến cố chồng chéo, bạn cần trừ đi các kết quả bị đếm trùng. Nếu \(A\) và \(B\) có thể cùng xảy ra, số lượng là \(|A \cup B| = |A| + |B| - |A \cap B|\). Đây là nguyên lý bù-trừ (inclusion-exclusion principle), và nó sẽ xuất hiện lại khi ta thảo luận về quy tắc cộng trong xác suất.
Giai thừa (factorial) của một số nguyên không âm \(n\) là tích của tất cả các số nguyên dương đến \(n\):

\[n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\]

Hãy hình dung giai thừa như trả lời câu hỏi: có bao nhiêu cách sắp xếp \(n\) đối tượng phân biệt thành một hàng? Ba cuốn sách trên kệ có thể được sắp xếp theo \(3! = 3 \times 2 \times 1 = 6\) cách. Theo quy ước, \(0! = 1\).
Giai thừa tăng cực kỳ nhanh. \(10! = 3.628.800\) và \(20!\) đã vượt quá \(2.4 \times 10^{18}\). Sự tăng trưởng bùng nổ này là lý do tại sao tìm kiếm vét cạn trở nên bất khả thi trong các bài toán tổ hợp.
Hoán vị (permutation) là một cách sắp xếp có thứ tự các đối tượng. Khi bạn chọn \(r\) mục từ \(n\) đối tượng phân biệt và thứ tự quan trọng, số hoán vị là:

\[P(n, r) = \frac{n!}{(n - r)!}\]

Hãy hình dung việc chọn chủ tịch, phó chủ tịch và thủ quỹ từ một câu lạc bộ gồm 10 người. Vai trò đầu tiên có 10 ứng viên, vai trò thứ hai có 9 người còn lại, vai trò thứ ba có 8 người. Điều đó cho \(P(10, 3) = 10 \times 9 \times 8 = 720\). Công thức xác nhận điều này: \(\frac{10!}{7!} = 720\).
Tổ hợp (combination) là một lựa chọn không có thứ tự. Khi bạn chọn \(r\) mục từ \(n\) và thứ tự không quan trọng, ta chia cho các cách sắp xếp dư thừa:

\[C(n, r) = \binom{n}{r} = \frac{n!}{r!(n - r)!}\]

Ký hiệu \(\binom{n}{r}\) được đọc là "n chọn r." Ý tưởng chính là mỗi tổ hợp tương ứng với \(r!\) hoán vị (\(r\) mục được chọn có thể được sắp xếp lại theo \(r!\) cách), vì vậy ta chia số hoán vị cho \(r!\).

So sánh cạnh nhau: hoán vị đếm tất cả các thứ tự, tổ hợp gộp các nhóm giống hệt nhau

Ví dụ: từ một nhóm 10 người, có bao nhiêu cách thành lập một ủy ban gồm 3 người? Thứ tự không quan trọng (không có chủ tịch hay phó chủ tịch, chỉ là thành viên), vì vậy ta dùng tổ hợp:

\[\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120\]

Cùng 10 người đó tạo ra 720 hoán vị nhưng chỉ 120 tổ hợp, bởi vì mỗi nhóm 3 người có \(3! = 6\) cách sắp xếp nội bộ.
Tổ hợp là trung tâm của xác suất. Hệ số nhị thức \(\binom{n}{r}\) đếm số cách để có chính xác \(r\) lần thành công trong \(n\) lần thử, là trái tim của phân bố nhị thức (sẽ được đề cập trong file 03).
Hãy cùng giải một bài toán ủy ban kinh điển kết hợp nhiều ý tưởng đếm khác nhau.
Bài toán: Một câu lạc bộ có 8 nam và 6 nữ. Có bao nhiêu cách thành lập một ủy ban gồm 5 người có đúng 3 nam và 2 nữ?
Bước 1: Chọn 3 nam từ 8.

\[\binom{8}{3} = \frac{8!}{3! \cdot 5!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56\]

Bước 2: Chọn 2 nữ từ 6.

\[\binom{6}{2} = \frac{6!}{2! \cdot 4!} = \frac{6 \times 5}{2 \times 1} = 15\]

Bước 3: Áp dụng quy tắc nhân. Mỗi cách chọn nam có thể ghép với mỗi cách chọn nữ:

\[56 \times 15 = 840 \text{ ủy ban}\]

Mô hình này — chia một bài toán đếm phức tạp thành các lựa chọn con độc lập và nhân chúng lại — là cách tiếp cận chuẩn trong tổ hợp.
Ngoài ra còn có hoán vị có lặp lại (permutations with repetition). Khi các mục có thể lặp lại, chọn \(r\) mục từ \(n\) loại cho \(n^r\) kết quả. Mã PIN 4 chữ số dùng các chữ số 0-9 có \(10^4 = 10.000\) khả năng. Mỗi vị trí có 10 lựa chọn, và quy tắc nhân xử lý phần còn lại.
Tổ hợp có lặp lại (combinations with repetition) (còn gọi là "sao và vạch") đếm số cách chọn \(r\) mục từ \(n\) loại khi được phép lặp lại và thứ tự không quan trọng:

\[\binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r!(n - 1)!}\]

Ví dụ: chọn 3 muỗng kem từ 4 hương vị (được phép lặp) cho \(\binom{4 + 3 - 1}{3} = \binom{6}{3} = 20\) lựa chọn.
Tóm tắt bộ công cụ đếm:

Tình huống	Công thức
Có thứ tự, không lặp (hoán vị)	\(P(n,r) = \frac{n!}{(n-r)!}\)
Không thứ tự, không lặp (tổ hợp)	\(\binom{n}{r} = \frac{n!}{r!(n-r)!}\)
Có thứ tự, có lặp	\(n^r\)
Không thứ tự, có lặp	\(\binom{n+r-1}{r}\)

Mọi phép tính xác suất liên quan đến các kết quả có khả năng như nhau đều dùng công thức \(P(\text{biến cố}) = \frac{\text{kết quả thuận lợi}}{\text{tổng kết quả}}\). Đếm cho ta cả hai con số. Với nền tảng này, chúng ta đã sẵn sàng để hình thức hóa chính xác suất trong file tiếp theo.

Bài tập lập trình (dùng CoLab hoặc notebook)¶

Tính \(P(10, 3)\) và \(\binom{10}{3}\) bằng cả công thức giai thừa và tính trực tiếp. Kiểm tra rằng số hoán vị luôn gấp \(r!\) lần số tổ hợp.

import jax.numpy as jnp
from math import factorial

n, r = 10, 3

perm = factorial(n) // factorial(n - r)
comb = factorial(n) // (factorial(r) * factorial(n - r))

print(f"P({n},{r}) = {perm}")
print(f"C({n},{r}) = {comb}")
print(f"P / C = {perm // comb} (should equal {r}! = {factorial(r)})")

Giải bài toán ủy ban (3 nam từ 8, 2 nữ từ 6) bằng lập trình và kiểm tra bằng cách liệt kê tất cả các ủy ban hợp lệ.

from itertools import combinations
from math import factorial

def comb_count(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))

# Formula approach
men_ways = comb_count(8, 3)
women_ways = comb_count(6, 2)
print(f"Formula: {men_ways} × {women_ways} = {men_ways * women_ways}")

# Enumeration approach
men = [f"M{i}" for i in range(1, 9)]
women = [f"W{i}" for i in range(1, 7)]
count = sum(1 for _ in combinations(men, 3) for _ in combinations(women, 2))
print(f"Enumeration: {count}")

Đếm xem có bao nhiêu mật khẩu 4 ký tự có thể tạo từ 26 chữ cái thường (được phép lặp). Sau đó đếm số mật khẩu không có ký tự nào lặp lại.

from math import factorial

n = 26
r = 4

with_rep = n ** r
without_rep = factorial(n) // factorial(n - r)

print(f"With repetition:    {with_rep:>10,}")
print(f"Without repetition: {without_rep:>10,}")
print(f"Fraction with repeats: {1 - without_rep/with_rep:.2%}")

Mô phỏng bài toán ngày sinh: trong một nhóm \(k\) người, xác suất có ít nhất hai người trùng ngày sinh là bao nhiêu? Vẽ đồ thị xác suất cho \(k = 1\) đến \(60\) và tìm điểm nó vượt qua 50%.

import jax
import jax.numpy as jnp
import matplotlib.pyplot as plt

def birthday_prob_exact(k):
    """Probability of at least one shared birthday in group of k."""
    p_no_match = 1.0
    for i in range(k):
        p_no_match *= (365 - i) / 365
    return 1 - p_no_match

ks = list(range(1, 61))
probs = [birthday_prob_exact(k) for k in ks]

plt.figure(figsize=(8, 4))
plt.plot(ks, probs, color="#3498db", linewidth=2)
plt.axhline(y=0.5, color="#e74c3c", linestyle="--", alpha=0.7, label="50%")
cross = next(k for k, p in zip(ks, probs) if p >= 0.5)
plt.axvline(x=cross, color="#e74c3c", linestyle="--", alpha=0.7)
plt.xlabel("Group size (k)")
plt.ylabel("P(at least one shared birthday)")
plt.title(f"Birthday Problem (crosses 50% at k={cross})")
plt.legend()
plt.grid(alpha=0.3)
plt.show()