Máy tính giai thừa

Máy tính giai thừa - Tính n! kèm các bước

🔢 Tính giai thừa (n!) cho mọi số từ 0 đến 170. Xem phân tích từng bước, hoán vị, tổ hợp và các ứng dụng thực tế.

Giai thừa là gì?

Giai thừa của một số nguyên không âm n, ký hiệu là n!, là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng n. Nó biểu thị số cách sắp xếp n đối tượng phân biệt.

Công thức giai thừa

n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1

• 0! = 1 (theo định nghĩa)
• 1! = 1
• n! = n × (n-1)! (định nghĩa đệ quy)

Ví dụ giai thừa

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3,628,800
• 0! = 1 (trường hợp đặc biệt)
• 20! = 2,432,902,008,176,640,000

Vì sao 0! = 1?

Có đúng một cách sắp xếp 0 vật: “sắp xếp rỗng”. Định nghĩa này đảm bảo các công thức toán học (đặc biệt trong tổ hợp) hoạt động chính xác. Nó cũng nhất quán với công thức đệ quy: n! = n × (n-1)!, nên 1! = 1 × 0! nghĩa là 0! phải bằng 1.

Hoán vị

P(n,r) = n!/(n-r)!

Số cách sắp xếp r đối tượng từ n đối tượng phân biệt khi thứ tự quan trọng.

• Ví dụ: P(5,3) = 5!/(5-3)! = 120/2 = 60
• Ứng dụng: Vị trí trên bục trao giải (hạng 1, 2, 3)

Tổ hợp

C(n,r) = n!/(r!(n-r)!)

Số cách chọn r đối tượng từ n đối tượng phân biệt khi thứ tự không quan trọng.

• Ví dụ: C(5,3) = 5!/(3!×2!) = 120/(6×2) = 10
• Ứng dụng: Chọn số xổ số, chọn ủy ban

Số 0 tận cùng trong n!

Các số 0 tận cùng được tạo bởi thừa số 10 = 2 × 5. Vì luôn có nhiều thừa số 2 hơn 5, ta chỉ cần đếm thừa số 5:

Số 0 = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...

• 10! có 2 số 0 tận cùng
• 25! có 6 số 0 tận cùng
• 100! có 24 số 0 tận cùng

Ứng dụng thực tế

• Mật mã học: số lượng khóa mã hóa có thể
• Lập lịch: cách sắp xếp cuộc hẹn, nhiệm vụ, sự kiện
• Di truyền học: chuỗi DNA/protein có thể
• Xác suất: tính xác suất trong trò chơi, xổ số
• Khoa học máy tính: phân tích độ phức tạp thuật toán
• Sản xuất: sắp xếp dây chuyền sản xuất
• Logistics: bài toán tối ưu tuyến đường

Một số giá trị giai thừa nổi tiếng

• 52! ≈ 8.07 × 10⁶⁷ (xáo bài)
• 70! ≈ 1.2 × 10¹⁰⁰ (lớn hơn số nguyên tử trong vũ trụ ≈ 10⁸⁰)
• 100! ≈ 9.3 × 10¹⁵⁷ (158 chữ số!)
• 170! ≈ 7.3 × 10³⁰⁶ (giới hạn tối đa JavaScript)

Xấp xỉ Stirling

Với n lớn, việc tính giai thừa chính xác là không thực tế. Xấp xỉ Stirling:

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

Xấp xỉ này chính xác hơn khi n tăng. Với n = 10, sai số < 1%.

Tốc độ tăng của giai thừa

Giai thừa tăng nhanh hơn nhiều so với hàm mũ hay đa thức:

• Đa thức: n² = 100 khi n=10
• Hàm mũ: 2ⁿ = 1,024 khi n=10
• Giai thừa: n! = 3,628,800 khi n=10

Giai thừa kép

Giai thừa kép (n!!) nhân cách một số:

• n!! = n × (n-2) × (n-4) × ... × 2 hoặc 1
• 7!! = 7 × 5 × 3 × 1 = 105
• 8!! = 8 × 6 × 4 × 2 = 384

Giai thừa phụ (Derangements)

Giai thừa phụ !n đếm số hoán vị mà không phần tử nào nằm đúng vị trí ban đầu:

!n = n! × (1/0! - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ/n!)

Ví dụ: !3 = 2 (các cách sắp xếp ABC không chữ nào đúng chỗ: BCA, CAB)

Triển khai trong lập trình

Cách lặp:

function factorial(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}
            

Cách đệ quy:

function factorial(n) {
    if (n === 0 || n === 1) return 1;
    return n * factorial(n - 1);
}
            

💡 Mẹo: Khi tính hoán vị hoặc tổ hợp, hãy rút gọn các thừa số chung trước khi tính để tránh tràn số. Với C(100,2) = 100!/(2!×98!), hãy tính (100×99)/2 = 4,950 thay vì tính các giai thừa khổng lồ riêng rẽ!