Ước lượng giai thừa lớn đến mức nào?

Giai thừa là khái niệm quen thuộc với lập trình viên, nhưng ít ai biết cách ước lượng số chữ số của một giai thừa khổng lồ mà không cần máy tính. Bài viết giải thích công thức xấp xỉ từ hàm Gamma và công thức Stirling, kèm ví dụ thú vị về 52! — con số liên quan đến số cách xáo trộn một bộ bài.

Một ngày nọ, tôi tự hỏi 52! (giai thừa của 52) lớn đến mức nào, và điều đó dẫn tôi đến câu hỏi làm sao ước lượng được nó mà không cần máy tính hay máy tính bỏ túi. Hóa ra đằng sau việc ước lượng số chữ số của một giai thừa một cách tương đối chính xác lại là một phần toán học khá thú vị. Bài viết này bắt đầu bằng cách nêu ra cách ước lượng, và nếu bạn tò mò thì có thể đọc phần nền tảng toán học phía sau.

Công thức xấp xỉ cơ bản

Không dài dòng nữa, công thức xấp xỉ số chữ số của một giai thừa là:

Số chữ số của n! ≈ n × log₁₀(n/e) + 2

Lấy ví dụ với câu hỏi ban đầu của tôi, ta ước lượng cho 52!

52 chia cho e (hằng số Euler, xấp xỉ 2,718) được khoảng 20. Và log₁₀(20) xấp xỉ 1,3. Do đó ước lượng cho ra:

Số chữ số của 52! ≈ 52 × 1,3 + 2 ≈ 69

Đáp án thực tế là 68, vậy là rất sát! Với những ước lượng kiểu này — khi bạn đang xử lý những con số khổng lồ — việc lệch vài chữ số thường không phải vấn đề lớn.

Mẹo tính nhẩm log₁₀: hãy nhớ rằng log₁₀2 = 0,3 và log₁₀3 = 0,5, rồi dùng các quy tắc logarit để ước lượng các bội số khác.

Hàm Gamma — nền tảng của giai thừa

Hàm Gamma với số thực n > 0 được định nghĩa bằng tích phân:

Γ(n) = ∫₀^∞ x^(n−1) e^(−x) dx

Tích phân này không có biểu thức giải tích trong trường hợp tổng quát, nhưng nó có một tính chất cực kỳ hữu ích. Ta xét Γ(n+1):

Γ(n+1) = ∫₀^∞ x^n e^(−x) dx

Áp dụng tích phân từng phần với u = x^n và v = −e^(−x), ta thu được:

Γ(n+1) = n × Γ(n)

Ngoài ra, Γ(1) có lời giải giải tích đặc biệt:

Γ(1) = ∫₀^∞ e^(−x) dx = 1

Điều này giúp thiết lập lập luận quy nạp: Γ(2) = 1!, Γ(3) = 2!, Γ(4) = 3!, và tổng quát Γ(n+1) = n!. Nói cách khác, hàm Gamma chính là phép nội suy của giai thừa trên toàn bộ tập số thực dương. Dưới đây là đồ thị của hàm Gamma trên một khoảng nhỏ, lưu ý trục tung dùng thang logarit vì hàm này tăng cực nhanh:

Đồ thị hàm Gamma với trục tung thang logarit

Xấp xỉ Stirling

Có thể bạn đã từng gặp xấp xỉ Stirling:

n! ≈ √(2πn) × (n/e)^n

Đây là một xấp xỉ tuyệt vời, hoạt động khá tốt ngay cả với n nhỏ. Phần này sẽ tóm tắt ngắn gọn cách công thức Stirling được suy ra từ hàm Gamma.

Bắt đầu với n! = Γ(n+1) = ∫₀^∞ x^n e^(−x) dx, ta biến đổi tích phân một chút bằng cách viết lại x^n = e^(n ln x):

n! = ∫₀^∞ e^(n ln x) e^(−x) dx

Sau đó đổi biến x = ny, tức dx = n dy:

n! = n × e^(n ln n) × ∫₀^∞ e^(n(ln y − y)) dy

Các bước này giúp tích phân có dạng phù hợp để áp dụng phương pháp Laplace, cho phép xấp xỉ các tích phân xác định dạng:

∫ₐᵇ e^(n f(x)) dx ≈ √(2π / (n |f''(x₀)|)) × e^(n f(x₀))

Trong đó x₀ là điểm cực đại toàn cục của hàm f(x). Với trường hợp của chúng ta, f(x) = ln x − x. Có thể dễ dàng chứng minh hàm này khả vi hai lần và đạt cực đại toàn cục tại x₀ = 1. Hơn nữa:

f(x₀) = −1 và f''(x₀) = −1

Thay các giá trị này vào xấp xỉ Laplace, ta thu được:

n! ≈ n × e^(n ln n) × √(2π/n) × e^(−n) ≈ √(2πn) × e^(n(ln n − 1)) ≈ √(2πn) × (n/e)^n

Đây chính là công thức Stirling cần chứng minh.

Tính số chữ số từ xấp xỉ Stirling

Ta có thể tính số chữ số của n! bằng cách lấy logarit cơ số 10 của công thức Stirling:

Số chữ số của n! ≈ log₁₀(√(2πn) × (n/e)^n) ≈ log₁₀(√(2πn)) + n × log₁₀(n/e)

Lưu ý rằng số hạng thứ nhất không được nhân với n, do đó khi n tăng lên, nó sẽ ngày càng ít đáng kể hơn. Dù vậy, nó vẫn cộng thêm vài chữ số — nên bạn nên tính đến nó nếu muốn ước lượng chính xác hơn.

Công thức minh họa số chữ số của giai thừa

Cụ thể, số hạng này cộng thêm khoảng 2 chữ số miễn là n nhỏ hơn khoảng 1600, và có thể cộng hơn 2 chữ số sau mốc đó, nhưng không vượt quá 3 cho đến khi n đạt 160000. Không rõ ai lại muốn ước lượng số chữ số của 1600! (khoảng 4450 chữ số, nếu bạn tò mò), chứ chưa nói đến 160000!

Minh họa thêm về công thức ước lượng

Ý nghĩa với lập trình viên Việt Nam

Với anh em lập trình, hiểu về độ lớn của giai thừa không chỉ là bài toán lý thuyết. Nó giúp bạn nhận ra vì sao giai thừa là một trong những hàm tăng trưởng nhanh nhất, đứng sau hàm mũ. Trong phân tích thuật toán, các bài toán có độ phức tạp O(n!) gần như bất khả thi với n chỉ khoảng 15–20.

Chẳng hạn, thuật toán sắp xếp ngây thơ bằng cách thử mọi hoán vị có độ phức tạp chính xác là n!. Và ví dụ 52! mà tác giả nhắc đến chính là số cách xáo trộn một bộ bài 52 lá — con số khổng lồ đến mức trong thực tế gần như không bao giờ lặp lại. Mỗi lần bạn xáo bài, bạn đang tạo ra một thứ tự mà gần như chắc chắn chưa từng tồn tại trong lịch sử loài người.

Việc nắm được các công thức xấp xỉ như Stirling cũng rất hữu ích khi bạn cần kiểm tra nhanh kích thước ước lượng của dữ liệu, tính toán bộ đệm, hoặc đánh giá xem một thuật toán có khả thi về mặt bộ nhớ hay không — đặc biệt trong các bài toán về tổ hợp, mã hóa và khoa học dữ liệu.