Factorial Calculator

Faktorials begrepp

Faktorials är produkten av alla positiva heltal från 1 till n. Definitionen: n! = n × (n−1) × (n−2) × ... × 2 × 1. Specialfall: 0! = 1 av definition (inte beräkning) — detta krävs för kombinatoriska formeln att fungera konsekvent.

Faktorials växer extraordinärt snabbt — snabbare än någon polynom eller till och med de flesta exponentiella funktioner. 5! = 120; 10! = 3 628 800; 15! = 1 307 674 368 000; 20! ≈ 2,43 × 10^18; 100! ≈ 9,33 × 10^157. Talet 170! är ungefär 7,26 × 10^306, vilket är den största faktorials som kan representeras som en 64-bitars flyttalskombination (dubbel precision). Vårt kalkylator använder BigInt-aritmetik för exakta heltalsresultat upp till 170!

Den rekursiva definitionen av faktorials är: n! = n × (n−1)! för n > 0, med 0! = 1 som basfall. Denna rekursiva struktur gör faktorials till ett klassiskt introduktionsexempel i datavetenskap för att lära ut rekursion, dynamisk programmering och memoisering. Faktorials beräkning via iteration är också standard: initiera resultat = 1, sedan multiplicera med varje heltal från 2 till n.

Notationen "n!" infördes av Christian Kramp 1808 som en bekväm förkortning för den ofta förekommande produkten 1 × 2 × 3 × ... × n. Före detta användes olika noteringar. Idag är n! universellt erkänt över alla matematiska traditioner.

Faktorials i kombinatorik och sannolikhet

Faktorials är grunden för kombinatorik — den grenen av matematiken som handlar om räkning, ordningar och urval. Nästan varje räkningproblem i sannolikhet och statistik involverar faktorials.

Ordningar (ordnade anordningar): Antalet sätt att ordna n distinkta objekt i en rad är n! — kallad n-faktorialsordningar. Med 4 böcker på en hylla: 4! = 24 anordningar. Med 10 löpare i en tävling, antalet möjliga ordningar för 1:a, 2:a och 3:e plats är P(10,3) = 10!/(10−3)! = 10!/7! = 720.

Den delordningsformeln: P(n,r) = n!/(n−r)! räknar ordnade urval av r objekt från n. Den totala ordningsformeln n! är det specialfallet r = n.

Urval (obundna urval): C(n,r) = n!/(r!(n−r)!), även skrivet ⁿCᵣ eller "n välj r" eller som binomialkoefficienten. Detta räknar antalet sätt att välja r objekt från n där ordningen inte spelar någon roll. Från 52 kort, antalet 5-korts händer = C(52,5) = 52!/(5!×47!) = 2 598 960. Sannolikheten för att få ett riktigt flush = 4/2 598 960 ≈ 0,000154%.

Multinomialkoefficienter: n!/(n₁! × n₂! × ... × nₖ!) räknar anordningar av n objekt där n₁ är av typ 1, n₂ av typ 2 osv. Anordna bokstäverna i MISSISSIPPI: 11!/(1!×4!×4!×2!) = 34 650 olika anordningar.

Faktorials tabell: n! för n = 0 till 20

Här är den fullständiga faktorials tabellen för små värden av n. Att minnas de första 10 faktorials är användbart för snabba mental kombinatoriska beräkningar.

Den explosiva tillväxten är imponerande: från 10! = 3,6 miljoner till 20! = 2,4 kvintiljoner på bara 10 steg. Denna snabba tillväxt är varför faktorials dyker upp i talsserier (för att säkerställa konvergens) och i normaliseringsfaktorer för sannolikhetsfördelningar.

Stirlings approximation och stora faktorier

För stora n är det praktiskt taget omöjligt att beräkna exakta faktorier — 100! har 158 siffror. Stirlings approximation ger ett utmärkt värde: n! ≈ √(2πn) × (n/e)^n, där e ≈ 2,71828 är Eulers tal.

Stirlings approximation noggrannhet: för n=10, exakt = 3 628 800; Stirling ger ≈ 3 598 696, en felstörning på mindre än 1%. För n=100 är den relativa felstörningen under 0,1%. Ju större n, desto mer exakt blir approximationen — approximationens relativa felstörning är O(1/n).

Log-faktorierln(n!) = Σ ln(k) för k=1 till n (summa av logaritmer) är beräkningsmässigt viktigt. I statistik och maskininlärning används log-probabiliteter istället för råa sannolikheter för att undvika numerisk underflöde (flera små tal multipliceras tillsammans snabbt underflödar till 0 i flerdeciffrigt aritmetik). Log-gammafunktionen utvidgar detta till icke-heltal.

Gammafunktionen Γ(n) är den kontinuerliga utvidgningen av faktorier till alla komplexa tal utom icke-positiva heltal: Γ(n) = (n−1)! för positiva heltal. Detta förekommer i sannolikhetsfördelningar (Gamma-fördelning, Chi-squared-fördelning, Beta-fördelning) och många fysikaliska formler. Vissa räknare kan beräkna Γ(1,5) = √π/2 ≈ 0,886 — "faktorier" av 0,5.

Faktorier i sannolikhetsfördelningar

Många av de viktigaste sannolikhetsfördelningarna i statistik använder faktorier i sina formler, och kopplar rent kombinatoriskt till verkliga världens dataanalys.

Binomialfördelning: P(X = k) = C(n,k) × p^k × (1−p)^(n−k). Modellerar antalet framgångar i n oberoende försök med sannolikheten p varje gång. C(n,k) = n!/(k!(n−k)!) är kombinatoriskt koefficient. Summan över alla k av dessa termer är 1 (total sannolikhet).

Poissonfördelning: P(X = k) = (λ^k × e^(−λ)) / k!. Modellerar antalet sällsynta händelser som inträffar i en fast tidsperiod när genomsnittsfrekvensen är λ. k! i täljaren normaliserar fördelningen. Används för: sjukhusinträffanden per timme, försäkringsanspråk per dag, mutationer per genomsnittlig replikation.

Normalfördelning och Stirlings approximation är djupt förbundna. Centrala gränsförmågan — att summan av oberoende slumpvariabler närmar sig en normalfördelning — kan bevisas med hjälp av Stirlings approximation av n!. Denna koppling mellan det diskreta (faktorier) och kontinuerliga (normalfördelning) världen är ett av de djupaste resultaten i sannolikhetsteori.

Födelsedagsproblemet: Sannolikheten att alla 23 personer i en rum har olika födelsedagar = 365!/(365−23)! ÷ 365^23 ≈ 49,3%. Så det finns en större än 50% chans att minst två delar samma födelsedag — ett berömt motintuitivt resultat som använder delvis permutationer.

Faktorials i talteori: avslutande nollor och Wilsons teorem

Faktorials interagerar rikligt med primtalsteori, vilket ger eleganta resultat om delbarhet och primdetektering.

Avslutande nollor i n!: Antalet avslutande nollor i n! är lika med antalet faktorer av 10, vilket är lika med antalet faktorer av 5 (eftersom faktorer av 2 är alltid mer talrika). Formeln: räkna = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ... (summa medan kraften av 5 ≤ n). För 100!: ⌊100/5⌋ + ⌊100/25⌋ = 20 + 4 = 24 avslutande nollor.

Legendres formel: Den högsta kraften av primtalet p som delar n! är ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... Detta berättar exakt primfaktoriseringen av n!, vilket är avgörande i talteori och kombinatorik.

Wilsons teorem: Ett heltal p > 1 är prim om och endast om (p−1)! ≡ −1 (mod p). För p=5: 4! = 24 ≡ 4 ≡ −1 (mod 5) ✓. För p=6 (komposit): 5! = 120 ≡ 0 (mod 6) ✗. Medan Wilsons teorem är vackert teoretiskt är det beräkningsmässigt opraktiskt för stora tal eftersom beräkningen av (p−1)! är exponentiellt dyr.

Faktorialsprim: Ett faktorialsprimtal är ett primtal av formen n! + 1 eller n! − 1. Exempel: 2! − 1 = 1 (inte prim), 3! − 1 = 5 (prim), 3! + 1 = 7 (prim), 4! − 1 = 23 (prim). Hitta stora faktorialsprimtal är ett aktivt forskningsområde inom rekreativ och beräkningsbaserad talteori.

Hur man använder denna faktorialsberäknare

Infoga ett icke-negativt heltal n (från 0 till 170) och klicka på Beräkna. Beräknaren returnerar den exakta faktorials värdet som ett fullständigt heltal med hjälp av JavaScripts BigInt för stora värden, undvika fluktuerande punktprecisitet som skulle förorena resultaten för n ≥ 19.

Noter:

• Ingång måste vara ett icke-negativt heltal. Beräknaren avrundar decimalingång till närmaste hela tal.
• Maximalt n = 170 för exakt beräkning (170! ≈ 7,26 × 10^306, precis inom dubbelprecision för visning).
• För n = 0 är resultatet 1 (av definitionen).
• För mycket stora faktorials (n > 100), är resultatet ett tal med 150+ siffror — visat i fullt av vår BigInt-implementering.
• För tillämpningar som kräver ln(n!), använd identiteten: ln(n!) = Σ ln(k) för k=1 till n.

Faktoriering i datavetenskap: Algoritmer och komplexitet

Faktoriering är intimt förbunden med beräkningskomplexitetsteori — studien av hur svåra problem är att lösa algoritmiskt. Förståelsen av faktoriering hjälper till att förklara varför vissa problem är "svåra" i ett exakt matematiskt mening.

Den resande sälsmannaproblemet (TSP) frågar: givet n städer och avstånd mellan varje par, hitta den kortaste rutten som besöker alla städer exakt en gång. En naiv bruteforce-ansats kontrollerar alla möjliga ordningar: (n−1)!/2 rutter (delar av 2 för symmetri, fixar startstaden). För n=20 städer: 19!/2 ≈ 6 × 10^16 rutter. Även vid 1 biljon rutter/sekund, skulle detta ta 60,000+ år. Denna faktoriella explosion är varför TSP är "NP-hård" och varför heuristiska algoritmer (istället för exakta lösningar) används i praktiken för stora instanser.

Sorteringsproblemet har faktoriella anslutningar också: n! är antalet möjliga ordningar av n element. Ett optimalt jämförande sorteringsalgoritm måste skilja mellan alla n! fall, kräver minst log₂(n!) jämförelser. Med Stirling's approximation, log₂(n!) ≈ n×log₂(n), varför det teoretiska minimiantalet jämförelser för sortering är O(n log n) — uppnådd av merge sort och heap sort.

I dynisk programmering, kan faktoriella underproblem memoeras: när du beräknar k!, kan du få (k+1)! = (k+1) × k! utan att omberäkna från grunden. Detta minskar kostnaden för att beräkna alla faktorier från 1 till n från O(n²) till O(n), en viktig optimering i tillämpningar som kräver många faktorieringsvärden såsom sannolikhetstabellgenerering.