Tính hoán vị, chỉnh hợp và giai thừa với số học chính xác tùy ý, xử lý giá trị hàng nghìn chữ số mà không tràn.
Tổ hợp là gì?
Tổ hợp là nhánh toán học đếm các sắp xếp và lựa chọn của các tập hữu hạn. Ba khối xây dựng — giai thừa, hoán vị và chỉnh hợp — cùng nhau trả lời gần như mọi câu hỏi "có bao nhiêu cách...?", từ đếm bàn bài poker và xác suất xổ số đến thời gian chạy thuật toán và cấu trúc mã di truyền. Mỗi cái được tính từ những cái khác qua biểu thức giai thừa ngắn, nên một máy tính duy nhất bao quát cả lĩnh vực.
Hoán vị (nPr)
Hoán vị là một sắp xếp mà thứ tự quan trọng. Số cách có thứ tự để chọn r phần tử từ n phần tử khác nhau là nPr = n! / (n − r)!. Tương đương: bạn có n lựa chọn cho vị trí đầu, n−1 cho vị trí hai, ..., n−r+1 cho vị trí thứ r — tích của r số nguyên giảm dần bắt đầu từ n.
nPr = n! / (n - r)!
Ví dụ: sắp xếp 3 chữ cái chọn từ {A, B, C, D} cho 4P3 = 4!/1! = 24 bộ ba có thứ tự (ABC, ABD, ACB, ACD, ...). Ví dụ đời thực phổ biến: có bao nhiêu cách 5 con ngựa về 3 vị trí đầu trong một cuộc đua? Trả lời: 5P3 = 60.
Chỉnh hợp (nCr)
Chỉnh hợp (hay tổ hợp chập r của n trong tiếng Việt) là một lựa chọn mà thứ tự không quan trọng. Số cách chọn r phần tử từ n là nCr = n! / (r! × (n − r)!). Cũng viết là C(n,r) hay "n chọn r" và bằng nPr chia cho r! — phần r! loại bỏ các thứ tự giữa các phần tử được chọn.
nCr = n! / (r! × (n - r)!)
Ví dụ: chọn 3 chữ cái từ {A, B, C, D} cho 4C3 = 4 lựa chọn ({A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}). Đời thực: một xổ số chọn 6 số từ 49 có 49C6 = 13.983.816 vé có thể, nên xác suất trúng độc đắc với một vé là khoảng 1 trên 14 triệu.
Giai thừa (n!)
Giai thừa của n là tích của tất cả các số nguyên dương đến n: n! = 1 × 2 × 3 × ... × n, với quy ước 0! = 1 (tích rỗng). Nó đếm số thứ tự của n phần tử khác nhau và xuất hiện như khối xây dựng cơ bản của cả nPr và nCr.
n! = n × (n - 1) × (n - 2) × ... × 2 × 1
Giai thừa tăng nhanh hơn bất kỳ đa thức hay hàm mũ đơn giản nào. 10! = 3.628.800, 20! = 2.432.902.008.176.640.000, và 70! ≈ 1,2 × 10¹⁰⁰. Vượt 170!, double IEEE-754 tràn — máy tính này dùng BigInt nên giá trị chính xác được bảo toàn cho mọi đầu vào bạn có thể chờ.
Ứng dụng của Tổ hợp
Tổ hợp có ứng dụng rộng rãi trong nhiều lĩnh vực:
- Xác suất & Thống kê: đếm bàn bài poker, nghịch lý sinh nhật, lấy mẫu không hoàn lại
- Khoa học máy tính: đếm đường đi, độ phức tạp thuật toán, xác suất xung đột hash, mã sửa lỗi
- Mật mã: ước lượng không gian khóa, độ mạnh mật khẩu, khả thi của brute-force
- Lý thuyết trò chơi: đếm trạng thái, phân tích nước đi tối ưu, đánh giá cây quyết định
- Sinh học và Hóa học: tổ hợp gen, đồng phân phân tử, cấu trúc bậc hai RNA
- Vận trù học: lập lịch, định tuyến, đóng gói, sơ đồ thi đấu
Câu hỏi thường gặp
Quy tắc duy nhất: thứ tự có quan trọng không? Nếu có, dùng hoán vị. Nếu không, dùng chỉnh hợp. Hoán vị đếm các sắp xếp: vị trí 1/2/3 trong một cuộc đua, ba chữ cái đầu của một mật khẩu, thứ tự diễn thuyết tại hội nghị. Chỉnh hợp đếm các lựa chọn: 5 quân bài nào trong bàn poker của bạn, 3 người nào trong một ủy ban, 6 số nào trúng xổ số. Quan hệ: nPr = nCr × r! — mỗi chỉnh hợp r phần tử có r! cách xếp thứ tự, và hoán vị đếm tất cả. Ví dụ: chọn 2 chữ cái từ {A,B,C,D}. Chỉnh hợp: {A,B}, {A,C}, {A,D}, {B,C}, {B,D}, {C,D} = 6. Hoán vị: thêm AB và BA, AC và CA, ... vậy 12. nP2 = 4!/2! = 12; nC2 = 4!/(2!·2!) = 6. Lưu ý 12 = 6 × 2! = 6 × 2. Khi nghi ngờ, viết một ví dụ nhỏ bằng tay để kiểm tra AB và BA tính giống hay khác trong bài toán của bạn.
Vì chọn r phần tử để gộp vào về mặt toán học giống hệt với chọn n−r phần tử để loại ra. Mỗi lựa chọn r phần tử xác định duy nhất một tập bù gồm n−r phần tử bị loại, và ngược lại, nên hai số đếm phải bằng nhau. Cho 10 người chọn ủy ban 3 người, C(10,3) = 120. Tương đương, bạn đang chọn 7 người không vào ủy ban, và C(10,7) = 120 — cùng con số. Tính đối xứng này cũng thấy trong công thức: C(n,r) = n!/(r!(n−r)!) không đổi khi đổi r và n−r. Hệ quả thực tế là tính toán: để tính C(100, 97), đừng lặp 97 lần — tính C(100, 3) thay vào đó, cùng giá trị mà chỉ 3 phép nhân. Tam giác Pascal thể hiện đối xứng này như gương trái-phải của mỗi hàng, và định lý nhị thức (a+b)^n = Σ C(n,k) a^(n−k) b^k dùng đối xứng để biểu diễn mọi khai triển ở dạng nhỏ hơn trong hai dạng tương đương.
Tam giác Pascal là mảng các hệ số nhị thức sắp xếp sao cho mỗi hàng n chứa C(n,0), C(n,1), ..., C(n,n). Hàng 0 chỉ là 1; hàng 1 là 1 1; hàng 2 là 1 2 1; hàng 3 là 1 3 3 1; v.v. Pattern được sinh bởi truy hồi C(n,k) = C(n−1, k−1) + C(n−1, k) — mỗi mục bên trong là tổng của hai mục bên trên. Lý lẽ tổ hợp: để chọn k phần tử từ n, hoặc phần tử thứ n được bao gồm (rồi chọn k−1 từ n−1 còn lại) hoặc bị loại (rồi chọn k từ n−1 còn lại). Tam giác được nghiên cứu độc lập ở nhiều nền văn hóa — Trung Quốc (Dương Huy, 1261), Ba Tư (Al-Karaji, khoảng 1000), Ấn Độ (chú giải Halayudha cho Pingala, khoảng 950) và Pháp (Blaise Pascal, 1654) — và xuất hiện khắp nơi, từ định lý nhị thức đến fractal (tam giác Sierpinski là Pascal mod 2), số Catalan và dãy Fibonacci (tổng các đường chéo cạn).
Lặp lại lật ngược các công thức. Khi cho phép lặp, số sắp xếp có thứ tự của r phần tử từ n lựa chọn là n^r — với mỗi trong r ô, bạn độc lập chọn bất kỳ trong n phần tử. Ví dụ: mã PIN 4 chữ số trên 10 chữ số = 10^4 = 10.000. Số lựa chọn không thứ tự có lặp ("đa tập") là C(n + r − 1, r) — công thức "sao và vạch". Ví dụ: phân phối 5 kẹo giống nhau cho 3 trẻ em là C(5+3−1, 5) = C(7,5) = 21. Không lặp dùng nPr và nCr chuẩn. Ma trận quyết định nhanh: thứ tự quan trọng + lặp → n^r; thứ tự quan trọng + không lặp → nPr; thứ tự không quan trọng + không lặp → nCr; thứ tự không quan trọng + lặp → C(n+r−1, r). Nhầm lẫn bốn trường hợp này là nguồn lỗi xác suất phổ biến nhất trong đề thi và phỏng vấn lập trình.
Trong một phòng chỉ 23 người, xác suất có ít nhất hai người chung sinh nhật vượt 50%; với 70 người vượt 99,9%. Điều này làm hầu hết mọi người sốc vì trực giác đòi 365/2 ≈ 180 người. Mẹo là chúng ta không hỏi "có ai chung sinh nhật với tôi không" (cần ~180 người) mà hỏi "có cặp nào trong phòng chung sinh nhật không" — và số cặp tăng bậc hai như C(n,2). Với 23 người có 253 cặp, mỗi cặp xác suất ~1/365 trùng, cho khoảng 253/365 ≈ 69% — gần giá trị chính xác. Tính toán chính xác dùng phần bù: P(tất cả khác) = 365/365 × 364/365 × 363/365 × ... × (365−n+1)/365, và P(có ít nhất một cặp trùng) = 1 − P(tất cả khác). Cùng cấu trúc tổ hợp này là lý do xung đột hash xuất hiện sau khoảng √N hash trên hash N-bit (tấn công gọi là tấn công sinh nhật trong mật mã), và lý do MD5 (128-bit) không còn được coi là chống xung đột ở 2^64 ≈ 18 tỷ tỷ mẫu.
Hầu hết xổ số chọn một tập nhỏ các số từ một pool lớn hơn. Xác suất trúng tất cả là 1 chia cho số lượng tổ hợp có thể, vốn là tổ hợp vì thứ tự không quan trọng. Lotto 6/49 (Canada, Tây Ban Nha): C(49,6) = 13.983.816 — khoảng 1 trên 14 triệu. Powerball (Mỹ): chọn 5 từ 69 bóng trắng và 1 từ 26 đỏ, vậy C(69,5) × 26 = 11.238.513 × 26 = 292.201.338 — khoảng 1 trên 292 triệu. EuroMillions: C(50,5) × C(12,2) = 139.838.160. Cơ hội trúng bất kỳ giải nào tốt hơn nhiều vì hầu hết xổ số trả giải nhỏ hơn cho trùng một phần (ví dụ 3 số trong 6). Cho Lotto 6/49, xác suất trùng chính xác 3 trong 6 là C(6,3) × C(43,3) / C(49,6) ≈ 1 trong 57. Lý do lợi thế nhà cái lớn không phải tỷ lệ độc đắc, mà là quỹ giải: xổ số thường chỉ trả 50–60% doanh thu dưới dạng giải, phần còn lại đi vào vận hành, thuế và quỹ thiện nguyện.
C(n, 0) bằng 1 vì có đúng một cách không chọn gì — lựa chọn rỗng. Trực giác đúng và cũng bị ép buộc bởi công thức: C(n, 0) = n! / (0! × n!) = 1, với 0! = 1 theo quy ước. C(n, n) bằng 1 vì có đúng một cách chọn tất cả — toàn bộ tập. Công thức cho C(n, n) = n! / (n! × 0!) = 1. Các trường hợp biên này quan trọng cho định lý nhị thức: (1 + x)^n = Σ C(n, k) x^k gồm cả số hạng hằng (k = 0, hệ số C(n,0) = 1) và số hạng đầu (k = n, hệ số C(n,n) = 1). Cũng khớp với đối xứng C(n, k) = C(n, n−k) — chọn 0 để gồm vào giống hệt chọn cả n để loại ra. Cả hai đầu mọi hàng tam giác Pascal đều là 1, và tổng các hàng bằng 2^n vì đó là tổng số tập con của một tập n phần tử.
Máy tính này dùng BigInt cho chính xác tùy ý nên không có giới hạn cố định — chỉ giới hạn thực tế. Cổ chai là phép nhân các số nguyên rất lớn, BigInt làm trong khoảng O((chữ số)^1,58) với thuật toán Karatsuba. Cho giai thừa: 100! có 158 chữ số, tính trong vài mili giây; 1000! có 2568 chữ số, mất phần giây; 100000! có 456.574 chữ số, mất vài giây; 1.000.000! có 5.565.709 chữ số, có thể mất một hai phút và vài trăm MB bộ nhớ. Cho chỉnh hợp và hoán vị, kết quả thường nhỏ hơn nhiều so với n! nhờ rút gọn trong công thức, nên C(1000, 5) = 8,25 × 10¹² là tức thì dù 1000! khổng lồ. Cho mục đích thống kê, xấp xỉ Stirling log(n!) ≈ n ln(n) − n + 0,5 ln(2πn) cho log của bất kỳ giai thừa nào trong O(1) — hữu ích cho tính entropy, log-likelihood và các chỉ số thông tin không cần từng chữ số.
Tính toán
Toán học
Có góp ý? Báo lỗi, đề xuất tính năng, hoặc chia sẻ suy nghĩ — chúng tôi đọc tất cả
MáY TíNH TOáN HọC32
WUTOOLS