Máy tính tổ hợp

Công thức

C(n,k) = n! / (k! × (n − k)!)

Tương đương: C(n, k) = (n × (n−1) × … × (n−k+1)) / k!

Ví dụ đã hoạt động

• C(10, 3) = 120: số cách chọn 3 loại topping từ 10.
• C(52, 5) = 2.598.960: số bộ bài poker 5 lá từ một bộ bài tiêu chuẩn.
• C(49, 6) = 13.983.816: số tổ hợp của lượt quay chính trong Xổ số Quốc gia Vương quốc Anh.
• C(70, 5) × 25 = 302.575.350: số tổ hợp giải độc đắc Mega Millions (5 bóng chính từ 70 + 1 bóng Mega từ 25).
• C(100, 50) ≈ 1,01 × 10²⁹: số tập con bằng một nửa của một tập gồm 100 phần tử.

Tổ hợp và hoán vị

• Tổ hợp C(n, k): thứ tự không quan trọng. Chọn {A, B, C} cũng giống như chọn {C, B, A}.
• Hoán vị P(n, k): thứ tự quan trọng. {A, B, C} khác với {C, B, A}.
• Mối quan hệ: P(n, k) = C(n, k) × k!

Các lượt quay xổ số là tổ hợp (thứ tự các quả bóng không quan trọng). Vị trí về đích của một cuộc đua là hoán vị (vị trí thứ nhất, thứ hai, thứ ba đều quan trọng).

Tam giác Pascal

C(n, k) tạo thành tam giác Pascal khi được sắp xếp:

            1
           1 1
          1 2 1
         1 3 3 1
        1 4 6 4 1
       1 5 10 10 5 1
      1 6 15 20 15 6 1

Mỗi mục C(n, k) là tổng của hai mục ở trên nó: C(n-1, k-1) + C(n-1, k). Đối xứng: C(n, k) = C(n, n-k).

Thuộc tính

• C(n, 0) = C(n, n) = 1: chỉ có một cách chọn không có gì hoặc chọn tất cả.
• C(n, 1) = n: n cách chọn 1 mục.
• Tổng của hàng n: Σ C(n, k) từ k=0 đến n = 2ⁿ. Tổng số tập hợp con của một tập hợp n mục.
• Gậy khúc côn cầu: Σ C(i, k) từ i=k đến n = C(n+1, k+1).

Ứng dụng thực tế

• Tỷ lệ cược xổ số: 1/C(n,k) cho kết quả rút ra chính xác.
• Thiết kế lấy mẫu: chọn nhóm thử nghiệm từ tổng thể.
• Di truyền: đếm các kiểu gen có thể có của con cái.
• Lên lịch: các giải đấu vòng tròn cần có trận đấu C(đội, 2).
• Phân phối nhị thức: P(X = k) = C(n, k) × p^k × (1-p)^(n-k).
• Lựa chọn ủy ban: cách thành lập ủy ban gồm 5 trong số 20 thành viên = C(20, 5) = 15.504.

Số lớn: vẫn chính xác

Kết quả tăng rất nhanh: C(100, 50) đã có 30 chữ số. Máy tính giới hạn n ở mức 170, đủ bao phủ mọi nhu cầu thực tế như xổ số, ủy ban và lấy mẫu, và mọi đáp án luôn chính xác vì phép tính dùng số học số nguyên độ chính xác tùy ý thay vì dấu phẩy động.