Kalkulator Faktorial
Hitunglah faktorial dari setiap bilangan bulat non-negatif. n! = n x (n-1) x ... x 2 x 1.
Memahami Faktorial
Faktorial dari bilangan bulat non-negatif n, ditulis n!, adalah hasil perkalian dari semua bilangan bulat positif dari 1 sampai n. Definisi:n! = n x (n-1) x (n-2) x ... x 2 x 1Kasus khusus:0! = 1menurut definisi (bukan perhitungan) -- ini diperlukan agar rumus kombinatorial bekerja secara konsisten.
Faktorial tumbuh sangat cepat - lebih cepat dari fungsi polinomial atau bahkan sebagian besar fungsi eksponensial. 5! = 120; 10! = 3,628,800; 15! = 1,307,674,368,000; 20! ~ 2.43 x 10^18; 100! ~ 9.33 x 10^157. Bilangan 170! adalah sekitar 7,26 x 10^306, yang merupakan faktorial terbesar yang dapat direpresentasikan sebagai bilangan titik-bergerak 64-bit (presisi ganda). Kalkulator kami menggunakan aritmatika BigInt untuk hasil bilangan bulat yang tepat hingga 170!
Definisi rekursif dari faktorial adalah: n! = n x (n-1)! untuk n > 0, dengan 0! = 1 sebagai kasus dasar. Struktur rekursif ini membuat faktorial menjadi contoh pengenalan klasik dalam ilmu komputer untuk mengajarkan rekursi, pemrograman dinamis, dan memoisasi. Perhitungan faktorial melalui iterasi juga standar: inisialisasi hasil = 1, kemudian kalikan dengan setiap bilangan bulat dari 2 hingga n.
Notasi "n!" diperkenalkan oleh Christian Kramp pada tahun 1808 sebagai singkatan yang nyaman untuk produk yang sering terjadi 1 x 2 x 3 x ... x n. Sebelum ini, berbagai notasi lain digunakan.
Faktorial dalam Kombinatorika dan Probabilitas
Faktorial adalah landasan dari kombinatorik -- cabang matematika yang berhubungan dengan penghitungan, pengaturan, dan pemilihan. Hampir setiap masalah penghitungan dalam probabilitas dan statistik akhirnya melibatkan faktorial.
Permutasi (penataan berurutan):Jumlah cara untuk mengatur n objek berbeda berturut-turut adalah n! - disebut permutasi n-faktor. Dengan 4 buku di rak: 4! = 24 pengaturan. Dengan 10 pelari dalam perlombaan, jumlah urutan yang mungkin untuk tempat pertama, kedua, dan ketiga adalah P10, 3 = 10! / 10-3! = 10! / 7! = 720.
Rumus permutasi parsial: P ((n,r) = n!/ ((n-r)! menghitung pilihan terurut dari r item dari n. Rumus permutasi total n! adalah kasus khusus r = n.
Kombinasi (pilihan tidak teratur):C ((n,r) = n!/(r!(n-r)!), juga ditulis nCr atau "n pilih r" atau sebagai koefisien binomial. Ini menghitung jumlah cara untuk memilih r item dari n di mana urutan tidak penting. Dari 52 kartu, jumlah tangan 5-kartu = C ((52,5) = 52!/(5!x47!) = 2,598,960. Probabilitas mendapatkan royal flush = 4/2,598,960 ~ 0,000154%.
Koefisien Multinomial:n!/(n1! x n2! x ... x nk!) menghitung susunan dari n item di mana n1 adalah tipe 1, n2 tipe 2, dll. Menyusun huruf dalam MISSISSIPPI: 11!/(1!x4!x4!x2!) = 34.650 susunan yang berbeda.
| Rumus | Ekspresi | Contoh |
|---|---|---|
| n! (semua pengaturan) | n x (n-1) x ... x 1 | 5! = 120 |
| P ((n,r) permutasi | Tidak! / (n-r)! | P ((10,3) = 720 |
| C ((n,r) kombinasi | / (r!n-r)!) | C(10,3) = 120 |
| Multinomial | n! / (n1! n2! ... nk!) | MISS: 4!/(1!3!) = 4 |
Tabel Faktorial: n! untuk n = 0 sampai 20
Berikut adalah tabel faktorial lengkap untuk nilai kecil dari n. Memori 10 faktorial pertama berguna untuk perhitungan kombinatorik mental yang cepat.
| n | n! | Kira-kira |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
| 3 | 6 | 6 |
| 4 | 24 | 24 |
| 5 | 120 tahun | 120 tahun |
| 6 | 720 tahun | 720 tahun |
| 7 | 5.040 | 5 ribu |
| 8 | 40.320 | 40 ribu |
| 9 | 362.880 | 363 ribu |
| 10 | 3.628.800 | 3,6 juta |
| 12 | 479.001.600 | 479 juta |
| 15 | 1.307.674.368.000 | 1,3 triliun |
| 20 | 2.432.902.008.176.640.000 | 2,4 x 10^18 |
Pertumbuhan eksplosif mencolok: dari 10! = 3,6 juta menjadi 20! = 2,4 quintillion hanya dalam 10 langkah. Pertumbuhan cepat ini adalah mengapa faktorial muncul dalam penyebut deret Taylor (menjamin konvergensi) dan dalam faktor normalisasi distribusi probabilitas.
Perkiraan Stirling dan Faktorial Besar
Untuk n besar, menghitung faktorial yang tepat tidak praktis -- 100! memiliki 158 digit.Perkiraan Stirlingmemberikan perkiraan yang sangat baik: n! ~ √(2πn) x (n/e) ^ n, di mana e ~ 2.71828 adalah bilangan Euler.
Akurasi perkiraan Stirling: untuk n = 10, tepat = 3.628.800; Stirling memberikan ~ 3.598.696, kesalahan kurang dari 1%. Untuk n = 100, kesalahan relatif adalah di bawah 0,1%.
Log-faktor ln ((n!) = Σ ln ((k) untuk k = 1 sampai n (jumlah logaritma) adalah penting secara komputasi. Dalam statistik dan pembelajaran mesin, log-probabilitas digunakan bukan probabilitas mentah untuk menghindari underflow numerik (mengkalikan banyak bilangan kecil bersama-sama dengan cepat underflows ke 0 dalam aritmatika titik-bergerak). Fungsi log-gamma memperluas ini ke argumen non-integer.
ItuFungsi gammaΓ(n) adalah perpanjangan kontinu dari faktorial untuk semua bilangan kompleks kecuali bilangan bulat non-positif: Γ(n) = (n-1)! untuk bilangan bulat positif. Ini muncul dalam distribusi probabilitas (distribusi Gamma, distribusi Chi-kuadrat, distribusi Beta) dan banyak rumus fisika. Beberapa kalkulator dapat menghitung Γ(1.5) = √π/2 ~ 0.886 - "faktorial" dari 0.5.
Faktor dalam Distribusi Probabilitas
Banyak distribusi probabilitas yang paling penting dalam statistik menggunakan faktorial dalam rumus mereka, menghubungkan kombinasi murni dengan analisis data dunia nyata.
Distribusi binomial:P ((X = k) = C ((n,k) x p^k x (1-p) ^ ((n-k). Memodelkan jumlah keberhasilan dalam n percobaan independen dengan probabilitas p masing-masing. C ((n,k) = n!/(k!(n-k)!) adalah koefisien kombinatorial.
Distribusi Poisson:P ((X = k) = (λ^k x e^(-λ)) / k!. Model jumlah kejadian langka yang terjadi dalam interval tetap ketika tingkat rata-rata adalah λ. K! dalam penyebut menormalkan distribusi. Digunakan untuk: kedatangan rumah sakit per jam, klaim asuransi per hari, mutasi per replikasi genom.
Distribusi normalTeorema Limit Pusat - bahwa jumlah variabel acak independen mendekati distribusi normal - dapat dibuktikan dengan menggunakan pendekatan Stirling dari n! Hubungan antara dunia diskrit (faktor) dan kontinu (distribusi normal) adalah salah satu hasil terdalam dalam teori probabilitas.
Masalah ulang tahun:Probabilitas bahwa semua 23 orang di sebuah ruangan memiliki ulang tahun yang berbeda = 365!/(365-23)! ÷ 365^23 ~ 49.3%. Jadi ada lebih dari 50% kemungkinan bahwa setidaknya dua orang memiliki ulang tahun yang sama -- hasil kontraintuitif yang terkenal yang menggunakan permutasi parsial.
Faktorial dalam Teori Bilangan: Trailing Zeros dan Teorema Wilson
Faktorial berinteraksi secara kaya dengan teori bilangan prima, menghasilkan hasil yang elegan tentang divisibilitas dan deteksi prima.
Mengikuti nol dalam n:Jumlah nol akhir dalam n! sama dengan jumlah faktor 10, yang sama dengan jumlah faktor 5 (karena faktor 2 selalu lebih banyak). Rumus: count = n/5 + n/25 + n/125 + ... (jumlah sementara pangkat 5 <= n). Untuk 100!: 100/5 + 100/25 = 20 + 4 = 24 nol akhir.
Rumus Legendre:Potensi tertinggi dari p prima membagi n! adalah n/p + n/p2 + n/p3 + ... Ini memberi tahu Anda faktorisasi prima yang tepat dari n!, yang penting dalam teori bilangan dan kombinatorik.
Teorema Wilson:Suatu bilangan bulat p > 1 adalah bilangan prima jika dan hanya jika (p-1)! -1 (mod p). Untuk p=5: 4! = 24 4 -1 (mod 5) . Untuk p=6 (komposit): 5! = 120 0 (mod 6) . Sementara teorema Wilson indah secara teoritis, secara komputasi tidak praktis untuk bilangan besar karena komputasi (p-1)! secara eksponensial mahal.
Bilangan prima faktorial:Suatu bilangan prima faktorial adalah bilangan prima dari bentuk n! + 1 atau n! - 1. Contoh: 2! - 1 = 1 (bukan bilangan prima), 3! - 1 = 5 (nombor prima), 3! + 1 = 7 (nombor prima), 4! - 1 = 23 (nombor prima).
Cara Menggunakan Kalkulator Faktorial Ini
Masukkan bilangan bulat non-negatif n (dari 0 sampai 170) dan klik Hitung. Kalkulator mengembalikan nilai faktorial yang tepat sebagai bilangan bulat penuh menggunakan JavaScript's BigInt untuk nilai besar, menghindari ketidakakuratan floating-point yang akan merusak hasil untuk n >= 19.
Catatan:
- Input harus menjadi bilangan bulat non-negatif. Kalkulator memotong input desimal ke bilangan bulat terdekat.
- Maksimum n = 170 untuk perhitungan yang tepat (170! ~ 7,26 x 10^306, hanya dalam kisaran presisi ganda untuk tampilan).
- Untuk n = 0, hasilnya adalah 1 (menurut definisi).
- Untuk faktorial yang sangat besar (n > 100), hasilnya adalah angka dengan 150+ digit -- ditampilkan secara penuh oleh implementasi BigInt kami.
- Untuk aplikasi yang membutuhkan ln ((n!), gunakan identitas: ln ((n!) = Σ ln ((k) untuk k = 1 ke n.
Pertanyaan yang Sering Diajukan
Mengapa 0! = 1?
Dengan definisi dan konvensi matematika: 0! = 1 memastikan rumus kombinatorial bekerja secara konsisten. C ((n,0) = n! / ((0! x n!) = 1, yang berarti ada persis 1 cara untuk memilih 0 item (tidak melakukan apa-apa). Tanpa definisi ini, setiap rumus menggunakan C ((n,0) akan membutuhkan kasus khusus. Konvensi produk kosong (produk dari istilah nol = 1) memberikan alasan yang sama.
Berapa faktorial dari bilangan negatif?
Faktorial tidak terdefinisi untuk bilangan bulat negatif. Relasi rekursif n! = n x (n-1)! akan memberikan 0! = 1/(-1)! = 0! pada n=0, tetapi 0! = 1, dan (-1)! akan menjadi 1/(0!) = 1, dan (-2)! = 1/((-1) x(-1)!) = tidak terdefinisi (pembagian dengan nol pada n=0). Fungsi Gamma memperluas faktorial ke bilangan real positif tetapi memiliki kutub (singularitas tidak terdefinisi) pada semua bilangan bulat non-positif.
Berapa banyak angka nol di akhir 100!?
24 nol terakhir. Hitung faktor 5: 100/5 + 100/25 = 20 + 4 = 24. (Tidak ada istilah 100/125 karena 125 > 100.) Karena faktor 2 selalu lebih banyak dari faktor 5, jumlah nol terakhir sama dengan hitungan 5s dalam faktorisasi prima dari n!.
Apa faktorial terbesar yang dapat dihitung oleh kalkulator?
Kalkulator floating-point standar maksimal sekitar 170! (~ 7,26 x 10^306, hanya dalam kisaran presisi ganda IEEE 754). Di luar 170!, floating-point memberikan Infinity. Kalkulator kami menggunakan JavaScript BigInt untuk perhitungan bilangan bulat yang tepat hingga 170!, menampilkan string digit penuh tanpa perkiraan apa pun.
Bagaimana faktorial digunakan dalam probabilitas?
Faktorial mendasari permutasi P ((n,r) = n! / ((n-r)! dan kombinasi C ((n,r) = n! / ((r! ((n-r)!). Ini menghitung jumlah cara untuk mengatur atau memilih item, membentuk dasar perhitungan probabilitas. Mereka muncul dalam distribusi binomial, distribusi Poisson, dan banyak rumus statistik lainnya.
Apa perkiraan Stirling?
Perkiraan Stirling: n! ~ √(2πn) x (n/e) ^n. Untuk n=10: tepat = 3.628.800; Stirling memberikan ~ 3.598.696 (kesalahan <1%). Untuk n=100: kesalahan <0,1%. Bentuk log: ln(n!) ~ nxln(n) - n + 1⁄2xln(2πn) sangat berharga dalam statistik untuk bekerja dengan probabilitas log tanpa menghitung faktorial yang sangat besar.
Apa hubungan antara faktorial dan fungsi Gamma?
Fungsi Gamma Γ(n) memuaskan Γ(n) = (n-1)! untuk bilangan bulat positif. Ini memperluas faktorial untuk semua bilangan kompleks (kecuali bilangan bulat non-positif). Γ(1/2) = √π ~ 1.7725, sehingga kita dapat mengatakan (-1/2)! = √π dengan konvensi. Fungsi Gamma muncul dalam distribusi probabilitas (Gamma, Beta, Chi-kuadrat), pemrosesan sinyal, dan mekanika kuantum.
Bagaimana faktorial berhubungan dengan segitiga Pascal?
Setiap entri dalam segitiga Pascal adalah koefisien binomial C ((n,r) = n! / ((r! ((n-r)!). Baris n dari segitiga Pascal berisi C ((n,0), C ((n,1), ..., C ((n,n). Setiap entri adalah jumlah dari dua entri di atasnya (aturan Pascal: C ((n,r) = C ((n-1,r-1) + C ((n-1,r))), yang dapat diverifikasi dari rumus faktorial. Segitiga Pascal mengenkode penghitungan kombinatorial menggunakan faktorial.
Apa teorema Wilson?
Teorema Wilson: p adalah bilangan prima jika dan hanya jika (p-1)! -1 (mod p). Untuk p=7: 6! = 720 = 102x7 + 6 6 -1 (mod 7) . Untuk p=8 (komposit): 7! = 5040 = 630x8 + 0 0 -1 (mod 8) . Cantik secara teoritis, tetapi tidak praktis untuk pengujian primalitas sejak komputasi (p-1)! untuk p besar adalah komputasi yang melarang.
Apa yang n! mewakili dalam jumlah pengaturan?
n! adalah jumlah cara yang berbeda untuk mengatur n item unik dalam satu baris (permutasi). Dengan 3 item {A, B, C}: 3! = 6 pengaturan: ABC, ACB, BAC, BCA, CAB, CBA. Dengan 10 item: 10! = 3.628.800 pengaturan - lebih dari 3 juta pemesanan hanya 10 hal. Dengan 52 kartu: 52! ~ 8 x 10^67, sebuah angka yang sangat besar yang menunjukkan mengapa deck kartu yang dikocok pada dasarnya tidak pernah dalam urutan yang sama dua kali dalam sejarah.
Faktorial dalam Ilmu Komputer: Algoritma dan Kompleksitas
Faktorial berhubungan erat dengan teori kompleksitas komputasi -- studi tentang betapa sulitnya masalah untuk dipecahkan secara algoritmik. Memahami faktorial membantu menjelaskan mengapa masalah tertentu "sulit" dalam arti matematis yang tepat.
ItuMasalah Penjual Perjalanan (TSP)bertanya: diberikan n kota dan jarak antara masing-masing pasangan, cari rute terpendek mengunjungi semua kota persis sekali. Naif brute-force pendekatan memeriksa semua kemungkinan pemesanan: (n-1)!/2 rute (membagi dengan 2 untuk simetri, memperbaiki kota awal). Untuk n = 20 kota: 19!/2 ~ 6 x 10 ^ 16 rute. Bahkan pada 1 triliun rute / detik, ini akan memakan waktu 60.000 + tahun. Ledakan faktorial ini adalah mengapa TSP adalah "NP-hard" dan mengapa algoritma heuristik (bukan solusi yang tepat) digunakan dalam praktek untuk contoh besar.
Itumasalah menyortirmemiliki hubungan faktorial juga: n! adalah jumlah pemesanan yang mungkin dari n elemen. Algoritma penyortiran berbasis perbandingan yang optimal harus membedakan antara semua n! kasus, membutuhkan setidaknya log2 ((n!) perbandingan. Dengan perkiraan Stirling, log2 ((n!) ~ nxlog2 ((n), itulah mengapa perbandingan minimum teoritis untuk penyortiran adalah O ((n log n) - dicapai dengan menyatu menyortir dan menyortir tumpukan.
In pemrograman dinamisHal ini mengurangi biaya komputasi semua faktorial dari 1 ke n dari O ((n2) ke O ((n), sebuah optimasi kunci dalam aplikasi yang membutuhkan banyak nilai faktorial seperti generasi tabel probabilitas.