Máy tính giai thừa / Hoán vị / Tổ hợp

Giai thừa

n! (đọc là 'n giai thừa') là tích của tất cả số nguyên dương từ 1 đến n. Vì vậy 5! = 1×2×3×4×5 = 120. Theo quy ước, 0! = 1 (tích rỗng).

Giai thừa tăng cực kỳ nhanh. 10! = 3.600.000, 20! = 2,4×10¹⁸, 100! có 158 chữ số. Số thực dấu phẩy động bị sai từ 21! (do giới hạn độ chính xác kép); chúng tôi sử dụng BigInt để có giá trị chính xác đến n=5000.

Hoán vị so với tổ hợp

Hoán vị P(n,k) = n! / (n−k)!: số cách chọn có thứ tự k phần tử từ n. P(5,2) = 20: chọn vị trí đầu từ 5, vị trí thứ hai từ 4 còn lại = 5×4 = 20.

Tổ hợp C(n,k) = n! / (k!(n−k)!): số cách chọn không có thứ tự. C(5,2) = 10: cùng lựa chọn nhưng {nhất, nhì} = {nhì, nhất} nên chia cho 2!. Công thức nổi tiếng 'chọn k từ n'.

Dùng hoán vị khi thứ tự quan trọng (thứ hạng cuộc đua, thứ tự mật khẩu). Dùng tổ hợp khi chỉ tập hợp được chọn là quan trọng (số xổ số, chọn ủy ban). C(n,k) ≤ P(n,k) luôn luôn; bằng nhau khi k=1.

Ứng dụng thực tế

Xác suất: xúc xắc, bài, tung đồng tiền. P(3 mặt sấp trong 5 lần tung) = C(5,3) × (1/2)⁵ = 10/32. Tổ hợp cho phép đếm các kết quả thuận lợi.

Thống kê: phân phối nhị thức dùng C(n,k). Lấy mẫu không hoàn lại dùng tổ hợp.

Khoa học máy tính: đếm tập con, phân tích độ phức tạp (ví dụ liệt kê k-clique là C(n,k)), thuật toán đồ thị.

Thực tế: xác suất xổ số (Vietlott 6/45: C(45,6) ≈ 8,1 triệu tổ hợp). Tổ hợp thực đơn nhà hàng: 'chọn 3 món phụ từ 8' là C(8,3) = 56 cách.