Tekijälaskenta

Faktooriaalien ymmärtäminen

Ei-negatiivisen kokonaislukumäärän n, kirjoitettu n!, faktorioli on kaikkien positiivisten kokonaislukujen kerroin 1-n välillä. Määritelmä:n! = n x (n-1) x (n-2) x ... x 2 x 1Erityistapaus:0! = 1määritelmästä (ei laskelmasta) -- tämä on tarpeen, jotta kombinatiiviset kaavat toimisivat johdonmukaisesti.

5! = 120; 10! = 3,628,800; 15! = 1,307,674,368,000; 20! ~ 2,43 x 10^18; 100! ~ 9,33 x 10^157.

Faktorialin rekursiivinen määritelmä on: n! = n x (n-1)! n > 0, jossa 0! = 1 on perustapa. Tämä rekursiivinen rakenne tekee faktorialista klassisen esittelyesimerkkinä tietotekniikassa rekursiota, dynaamista ohjelmointia ja memoisaatiota varten. Faktorialin laskenta iteraation kautta on myös vakio: käynnistää tulos = 1, sitten kerrotaan jokaisella kokonaislukuun 2 n.

Christian Kramp esitteli "n!"-merkinnän vuonna 1808 helppokäyttöisenä lyhenteenä usein esiintyvälle tuotteelle 1 x 2 x 3 x ... x n. Ennen tätä käytettiin erilaisia muita merkintöjä. Nykyään n! on yleisesti tunnustettu kaikissa matemaattisissa perinteissä.

Faktoriaalit kombinatorikassa ja todennäköisyydessä

Faktooriaali on kombinatoriikan kulmakivi - se osa matematiikkaa, joka käsittelee laskentaa, järjestelyjä ja valintoja.

Permutaatiot (järjestykselliset järjestelyt):N:n eri kohteen järjestämismuotojen lukumäärä on n! -- nimeltään n-faktoriset permutaatiot. Kun hyllyllä on 4 kirjaa: 4! = 24 järjestelyä. Kun kilpailuun on 10 juoksijaa, mahdollisten järjestelyjen lukumäärä ensimmäiselle, toiselle ja kolmannelle paikalle on P10,(3) = 10!/(10-3)! = 10!/7! = 720.

Osapermutaatioiden kaava: P ((n,r) = n!/ ((n-r)!) laskee järjestetyt valinnat r kohteista n:stä. Permutaatioiden kaava n! on erityistapaus r = n.

Yhdistelmät (järjestyksettömät valinnat):C ((n,r) = n!/(r!(n-r)!), jota kirjoitetaan myös nCr tai "n valitsee r" tai binomiaalikertoimena. Tämä laskee r-kohteiden valitsemistapojen lukumäärän n:stä, jossa järjestyksellä ei ole väliä. 52 kortista 5 kortin käsien lukumäärä = C ((52,5) = 52!/(5!x47!) = 2,598,960.

Monikertaiset kertoimet:n!/(n1! x n2! x ... x nk!) lasketaan järjestelyt n kohteita, joissa n1 ovat tyyppi 1, n2 tyyppi 2, jne. Järjestämällä kirjaimet MISSISSIPPI: 11!/(1!x4!x4!x2!) = 34,650 erillisiä järjestelyjä.

Faktoritaulukko: n! n = 0-20

Tässä on täydellinen faktoriotaulukko pienille n:n arvoille. Ensimmäisten 10 faktorioiden muistaminen on hyödyllistä nopeiden henkisten kombinatoristen laskelmien tekemiseen.

Tämä räjähdysmäinen kasvu on hämmästyttävä: 10! = 3,6 miljoonasta 20! = 2,4 quintillionia vain 10 askelta.

Stirlingin lähestymistapa ja suuret tekijät

Suurille n:lle tarkkojen faktorialojen laskenta on epäkäytännöllistä -- 100! on 158 numeroa.Stirlingin lähestymistapaantaa erinomaisen arvion: n! ~ √(2πn) x (n/e) ^ n, jossa e ~ 2.71828 on Eulerin luku.

Stirlingin lähestymistavan tarkkuus: n=10, exact = 3,628,800; Stirling antaa ~ 3,598,696, virhe alle 1%. n=100, suhteellinen virhe on alle 0,1%. Mitä suurempi n, sitä tarkempi lähestymistapa tulee - lähestymistavan suhteellinen virhe on O(1/n).

Log-faktoriaali ln(n!) = Σ ln(k k=1 to n (logaritmien summa) on laskennallisesti tärkeä. Tilastossa ja koneen oppimisessa log-todennäköisyyksiä käytetään raaka-todennäköisyyksien sijasta, jotta vältetään numeerinen alivirtaus (monen pienen numeron kertominen nopeasti 0:een kelluvassa pisteessä). Log-gamma-toiminto laajentaa tätä ei-kokoon argumentteihin.

SeuraavaGamma-toimintoΓ(n) on faktorielin jatkuva laajennus kaikille monimutkaisille numeroille lukuun ottamatta ei-positiivisia kokonaislukuja: Γ(n) = (n-1)! positiivisille kokonaislukuille. Tämä esiintyy todennäköisyysjakaumissa (Gamma-jakauma, Chi- neliöjakauma, Beta-jakauma) ja monissa fysiikan kaavoissa. Jotkut laskimet voivat laskea Γ(1.5) = √π/2 ~ 0.886 - "faktorielin" 0,5.

Todennäköisyysjakauman tekijät

Monet tilaston tärkeimmistä todennäköisyysjakaumista käyttävät faktooriaaleja kaavoissaan yhdistämällä puhtaan kombinatorion reaalimaailman tietojen analyysiin.

Binomiaalijakauma:P ((X = k) = C ((n,k) x p^k x (1-p) ^ ((n-k). Modeloi n:n riippumattoman kokeilun onnistumisten määrän jokaisella todennäköisyydellä p. C ((n,k) = n!/(k!(n-k)!) on kombinatiivinen kerroin.

Poisson-jakauma:P ((X = k) = (λ^k x e^(-λ)) / k!. Modeloi harvinaisten tapahtumien määrää, jotka tapahtuvat kiinteässä väliajassa, kun keskimääräinen määrä on λ. K! nimittäjässä normalisoi jakauman. Käytetään: sairaalaan saapuminen tunnissa, vakuutusvaatimukset päivässä, mutaatiot per genomin replikaatio.

NormaalijakaumaStirlingin ja Stirlingin lähestymistavat ovat syvästi yhteydessä toisiinsa. Keskilimiittiteoreema - että riippumattomien satunnaisten muuttujien summat lähestyvät normaalia jakautumista - voidaan todistaa käyttämällä Stirlingin n:n lähestymistapaa! Tämä yhteys erillisten (faktoriaali) ja jatkuvien (normaalijakauma) maailmojen välillä on yksi todennäköisyysteorian syvimmistä tuloksista.

Syntymäpäiväongelma:Todennäköisyys, että kaikilla 23 ihmisellä huoneessa on eri syntymäpäivät = 365!/(365-23)! ÷ 365^23 ~ 49.3%. Joten on suurempi kuin 50% mahdollisuus, että ainakin kaksi on samaa syntymäpäivää - kuuluisa intuitiivinen tulos, joka käyttää osittaisia permutaatioita.

Faktoriaali numeroteoriassa: Trailing Zeros ja Wilsonin lause

Faktooriaali vuorovaikuttaa runsaasti alkulukuteorian kanssa ja tuottaa tyylikkäitä tuloksia jaettavuudesta ja alkulukujen havaitsemisesta.

Seuraavat nollat n:N:ssä olevien nollatulosten lukumäärä on yhtä suuri kuin 10-kertoimittajien lukumäärä, joka on yhtä suuri kuin 5-kertoimittajien lukumäärä (koska 2-kertoimittajat ovat aina runsaampia).

Legendren kaava:Korkein potenssi alkuluku p:stä jakaen n! on n/p + n/p2 + n/p3 + ... Tämä kertoo n:n tarkan alkulukufaktorisoinnin, joka on välttämätöntä lukuteoriassa ja kombinatorioissa.

Wilsonin lause:Kokonaisluku p > 1 on alkuluku, jos ja vain jos (p-1)! -1 (mod p). Jos p=5: 4! = 24 4 -1 (mod 5) . Jos p=6 (komposiitti): 5! = 120 0 (mod 6). Vaikka Wilsonin lause on kaunis teoreettisesti, se on laskennallisesti epäkäytännöllinen suurille numeroille, koska laskenta (p-1)! on eksponentiaalisesti kallista.

Faktoriaaliset alkulukuja:Faktooriaalinen alkuluku on alkuluku muodossa n! + 1 tai n! - 1. Esimerkkejä: 2! - 1 = 1 (ei alkuluku), 3! - 1 = 5 (alkuluku), 3! + 1 = 7 (alkuluku), 4! - 1 = 23 (alkuluku).

Kuinka käyttää tätä tekijälaskentaa

Kirjoita ei-negatiivinen kokonaisluku n (0 - 170) ja napsauta Laske. Laskuri palauttaa tarkkan faktorialaarvon kokonaislukuina käyttäen JavaScriptin BigIntia suurille arvoille, välttäen kelluvan pisteen epätarkkuutta, joka vahingoittaisi tuloksia n >= 19.

Huomautukset:

• Sisääntuloon on sisällyttävä ei-negatiivinen kokonaisluku, ja laskin leikkaa desimaalin lähimpään kokonaislukuun.
• Maksimi n = 170 tarkkaa laskentaa varten (170! ~ 7,26 x 10^306, vain näytön kaksinkertaisen tarkkuuden alueella).
• Jos n = 0, tulos on 1 (määritelmän mukaan).
• Erittäin suurille faktorialleille (n > 100), tulos on luku, jossa on yli 150 numeroa - näytetään kokonaisuudessaan BigInt-sovelluksella.
• Sovelluksissa, joissa tarvitaan ln ((n!), käytetään identiteettiä: ln ((n!) = Σ ln ((k) k = 1 n:n kohdalla.

Faktoriaalit tietotekniikassa: Algoritmit ja monimutkaisuus

Faktoriaali on läheisesti yhteydessä laskennalliseen monimutkaisuusteoriaan - tutkimukseen siitä, kuinka vaikeita ongelmia on ratkaista algoritmisesti. Faktoriaalin ymmärtäminen auttaa selittämään, miksi tietyt ongelmat ovat "vaikeita" täsmällisessä matemaattisessa mielessä.

SeuraavaMatkailijan ongelma (TSP)kysyy: kun on n kaupunkia ja kunkin parin väliset etäisyydet, etsi lyhin reitti, joka vierailee kaikissa kaupungeissa täsmälleen kerran. Naiivi raaka-aine lähestymistapa tarkistaa kaikki mahdolliset järjestelyt: (n-1)!/2 reittiä (jaetaan 2 symmetriaa varten, kiinnitetään lähtökaupunki). n = 20 kaupunkia varten: 19!/2 ~ 6 x 10 ^ 16 reittiä. Jopa 1 biljoonaa reittiä sekunnissa tämä kestäisi 60 000+ vuotta. Tämä faktoriaaliräjähdys on syy siihen, miksi TSP on "NP-kova" ja miksi heuristisiä algoritmeja (tarkan ratkaisun sijasta) käytetään käytännössä suurissa tapauksissa.

Seuraavalajitteluongelmaon myös faktorialaisia yhteyksiä: n! on n-elementtien mahdollisten järjestelyjen lukumäärä. Optimaalisen vertailupohjaisen lajittelualgoritmin on erotettava kaikki n! tapaukset, jotka vaativat vähintään log2 ((n!) vertailut. Stirlingin lähestymistavalla, log2 ((n!) ~ nxlog2 ((n), minkä vuoksi lajittelun teoreettinen vähimmäisvertailut ovat O ((n log n) - saavutetaan yhdistämällä lajittelua ja kasa lajittelua.

In dynaaminen ohjelmointiTämä pienentää kustannuksia, jotka aiheutuvat kaikkien 1 - n-faktoriaalien laskemisesta O ((n2) - O ((n), mikä on keskeinen optimointi sovelluksissa, jotka vaativat monia faktoriaaliarvoja, kuten todennäköisyystaulukon luomista.