Faktoriell kalkulator

Forstå Factorials

Faktorialen av et ikke-negativt heltall n, skrevet n!, er produktet av alle positive heltall fra 1 til n. Definisjonen:n! = n x (n-1) x (n-2) x ... x 2 x 1Spesiell sak:0! = 1per definisjon (ikke beregning) - dette er nødvendig for at kombinatoriske formler skal fungere konsekvent.

Faktorialer vokser ekstraordinært raskt - raskere enn noen polynomial eller selv de fleste eksponentielle funksjoner. 5! = 120; 10! = 3,628,800; 15! = 1,307,674,368,000; 20! ~ 2,43 x 10^18; 100! ~ 9,33 x 10^157.

Den rekursive definisjonen av faktoriale er: n! = n x (n-1)! for n > 0, med 0! = 1 som basisfall. Denne rekursive strukturen gjør faktoriale en klassisk introduksjonseksempel i datavitenskap for undervisning rekursion, dynamisk programmering, og memoisering. Faktorial beregning via iterasjon er også standard: initialisere resultat = 1, deretter multiplisere med hvert heltall fra 2 til n.

Notasjonen "n!" ble introdusert av Christian Kramp i 1808 som en praktisk forkortelse for det hyppig forekommende produktet 1 x 2 x 3 x ... x n. Før dette ble ulike andre notasjoner brukt.

Faktorialer i kombinatorikk og sannsynlighet

Faktorial er hjørnesteinen i kombinatorikk - den grenen av matematikk som omhandler telning, arrangementer og valg.

Permutasjoner (ordnede ordninger):Antall måter å arrangere n forskjellige objekter på en rad er n! - kalt n-faktoriske permutasjoner. Med 4 bøker på en hylle: 4! = 24 arrangementer. Med 10 løpere i et løp, er antall mulige ordninger for 1., 2. og 3. plass P10,(3) = 10!/(10-3)! = 10!/7! = 720.

Den partielle permutasjonsformelen: P ((n,r) = n! / ((n-r)! teller ordnede valg av r elementer fra n. Den totale permutasjonsformelen n! er det spesielle tilfellet r = n.

Kombinasjoner (uavhengige valg):C ((n,r) = n!/(r!(n-r)!), også skrevet nCr eller "n velger r" eller som binomialkoeffisienten. Dette teller antall måter å velge r elementer fra n hvor rekkefølgen ikke spiller noen rolle. Fra 52 kort, antall 5-kort hender = C ((52,5) = 52!/(5!x47!) = 2,598,960. Sannsynligheten for å bli behandlet en kongelig flush = 4/2,598,960 ~ 0,000154%.

Multinomielle koeffisienter:n!/(n1! x n2! x ... x nk!) teller arrangementer av n elementer der n1 er av type 1, n2 av type 2, etc. Arrangering av bokstavene i MISSISSIPPI: 11!/(1!x4!x4!x2!) = 34,650 forskjellige arrangementer.

Faktortabellen: n! for n = 0 til 20

Her er den komplette faktoriale tabellen for små verdier av n. Å huske de første 10 faktoriale er nyttig for raske mentale kombinatoriske beregninger.

Den eksplosive veksten er slående: fra 10! = 3,6 millioner til 20! = 2,4 quintillion i bare 10 trinn.

Stirlings tilnærming og store faktoriale

For store n, beregning nøyaktige faktoriale er upraktisk - 100! har 158 sifre.Stirlings tilnærminggir et utmerket estimat: n! ~ √(2πn) x (n/e) ^ n, hvor e ~ 2.71828 er Eulers tall.

Nøyaktighet av Stirlings tilnærming: for n=10, nøyaktig = 3.628.800; Stirling gir ~ 3.598.696, en feil på mindre enn 1%. For n=100, er den relative feilen under 0,1%.

Den log-faktoriske ln ((n!) = Σ ln ((k) for k = 1 til n (summen av logaritmer) er beregningsmessig viktig. I statistikk og maskinlæring brukes log-sannsynligheter i stedet for rå sannsynligheter for å unngå numerisk understrøm (multiplikere mange små tall sammen raskt understrømmer til 0 i flytende punkt aritmetikk).

DenGammafunksjonΓ(n) er den kontinuerlige utvidelsen av faktoriale til alle komplekse tall unntatt ikke-positive heltall: Γ(n) = (n-1)! for positive heltall. Dette vises i sannsynlighetsfordelinger (Gamma-fordeling, Chi-kvadratfordeling, Beta-fordeling) og mange fysikkformler. Noen kalkulatorer kan beregne Γ(1.5) = √π/2 ~ 0.886 - "faktoriale" av 0.5.

Faktorialer i sannsynlighetsfordelinger

Mange av de viktigste sannsynlighetsfordelingene i statistikk bruker faktoriale i sine formler, som forbinder ren kombinatorikk med dataanalyse i den virkelige verden.

Binomialfordeling:P ((X = k) = C ((n,k) x p^k x (1-p) ^ ((n-k). Modellerer antall suksesser i n uavhengige forsøk med sannsynlighet p hver. C ((n,k) = n!/(k!(n-k)!) er den kombinatoriske koefficienten. Summen over alle k av disse vilkårene er lik 1 (total sannsynlighet).

Poisson-fordeling:P(X = k) = (λ^k x e^(-λ)) / k!.Modellerer antall sjeldne hendelser som oppstår i et fast intervall når gjennomsnittsfrekvensen er λ. K! i nevneren normaliserer fordelingen. Brukes for: sykehusankomster per time, forsikringskrav per dag, mutasjoner per genomreplikasjon.

Normalfordelingog Stirlings tilnærming er dypt forbundet. Den sentrale begrensningsteoremet - at summer av uavhengige tilfeldige variabler nærmer seg en normal fordeling - kan bevises ved hjelp av Stirlings tilnærming av n! Denne forbindelsen mellom diskrete (faktoriske) og kontinuerlige (normal fordeling) verdener er en av de dypeste resultatene i sannsynlighetsteorien.

Fødselsdagsproblem:Sannsynligheten for at alle 23 personer i et rom har forskjellige fødselsdager = 365!/(365-23)! ÷ 365^23 ~ 49.3%. Så det er en større enn 50% sjanse for at minst to deler en fødselsdag - et berømt kontraintuitivt resultat som bruker delvis permutasjoner.

Faktorial i tallteori: Trailing Zeros og Wilsons teorem

Faktorial interagerer rikt med primtallteori, og gir elegante resultater om delbarhet og primdeteksjon.

Følgende nuller i n:Antall etterfølgende nuller i n! er lik antall faktorer av 10, som er lik antall faktorer av 5 (siden faktorer av 2 er alltid mer rikelig). Formelen: count = n/5 + n/25 + n/125 + ... (sum mens makt av 5 <= n). For 100!: 100/5 + 100/25 = 20 + 4 = 24 etterfølgende nuller.

Legendres formel:Den høyeste potens av prim p dividert med n! er n/p + n/p2 + n/p3 + ... Dette forteller deg den eksakte primfaktorisering av n!, som er viktig i tallteori og kombinatorikk.

Wilsons teorem:Et heltall p > 1 er primt hvis og bare hvis (p-1)! -1 (mod p). For p=5: 4! = 24 4 -1 (mod 5). For p=6 (kompositt): 5! = 120 0 (mod 6). Mens Wilsons teorem er vakkert teoretisk, er det beregningsmessig upraktisk for store tall siden beregning (p-1)! er eksponentielt dyrt.

Faktorielle primtal:Et faktorelt primtall er et primtall av formen n! + 1 eller n! - 1. Eksempler: 2! - 1 = 1 (ikke primtall), 3! - 1 = 5 (primtall), 3! + 1 = 7 (primtall), 4! - 1 = 23 (primtall).

Hvordan bruke denne faktorkalkulatoren

Skriv inn et ikke-negativt heltall n (fra 0 til 170) og klikk på Beregne. Kalkulatoren returnerer den eksakte faktoriale verdien som et fullt heltall ved hjelp av JavaScript's BigInt for store verdier, og unngår flytende-punkt-upprecisjon som vil ødelegge resultater for n >= 19.

Merknader:

• Input må være et ikke-negativt heltall. Kalkulatoren trunkerer desimal input til nærmeste heltall.
• Maksimalt n = 170 for nøyaktig beregning (170! ~ 7.26 x 10^306, bare innenfor dobbelt presisjonsområde for visning).
• For n = 0 er resultatet 1 (per definisjon).
• For veldig store faktoriale (n > 100), er resultatet et tall med 150+ sifre - vist i sin helhet av vår BigInt implementering.
• For applikasjoner som krever ln(n!), Bruk identiteten: ln(n!) = Σ ln(k) for k=1 til n.

Faktorialer i datavitenskap: Algoritmer og kompleksitet

Faktoriell er nært knyttet til beregningsmessig kompleksitetsteori - studiet av hvor vanskelige problemer er å løse algoritmisk. Forståelse av faktoriell bidrar til å forklare hvorfor visse problemer er "vanskelige" i en presis matematisk forstand.

DenReisende handelsmannsproblem (TSP)spør: gitt n byer og avstander mellom hvert par, finn den korteste ruten som besøker alle byene nøyaktig en gang. En naiv brute-force tilnærming sjekker alle mulige ordninger: (n-1)!/2 ruter (delte med 2 for symmetri, fastsette startbyen). For n = 20 byer: 19!/2 ~ 6 x 10 ^ 16 ruter. Selv ved 1 trillion ruter / sekund, ville dette ta 60.000 + år. Denne faktoriske eksplosjonen er grunnen til at TSP er "NP-hard" og hvorfor heuristiske algoritmer (i stedet for eksakte løsninger) brukes i praksis for store tilfeller.

Densorteringsproblemhar også faktoriske forbindelser: n! er antall mulige ordninger av n elementer. En optimal sammenligningsbasert sorteringsalgoritme må skille mellom alle n! tilfeller, som krever minst log2 ((n!) sammenligninger. Ved Stirlings tilnærming, log2 ((n!) ~ nxlog2 ((n), som er grunnen til at den teoretiske minimum sammenligninger for sortering er O ((n log n) - oppnådd ved å slå sammen sortering og heap sortering.

In dynamisk programmeringDette reduserer kostnaden for å beregne alle faktoriale fra 1 til n fra O ((n2) til O ((n), en nøkkeloptimalisering i applikasjoner som krever mange faktoriale verdier som sannsynlighetstabeller.