Faktorijel
faktorijel (engl. factorial, prema lat. factor), u matematici, funkcija koja svakom nenegativnom cijelom broju pridružuje proizvod svih pozitivnih brojeva manjih ili jednakih . Na primjer,
0 | 1 |
1 | 1 |
2 | 2 |
3 | 6 |
4 | 24 |
5 | 120 |
6 | 720 |
7 | 5040 |
8 | 40320 |
9 | 362880 |
10 | 3628800 |
15 | 1307674368000 |
20 | 2432902008176640000 |
25 | 15511210043330985984000000 |
50 | 3,04140932... · 1064 |
70 | 1,19785717... · 10100 |
450 | 1,73336873... · 101 000 |
3249 | 6,41233768... · 1010 000 |
25206 | 1,205703438... · 10100 000 |
Faktorijel prvih nekoliko brojeva i faktorijel nekih većih brojeva
- i
gdje predstavlja n-faktorijel. Oznaku je prvi uveo Kristijan Kramp, 1808. godine.
Definicija
urediFaktorijel se formalno definiše na sljedeći način
Gornja definicija pretpostavlja da je:
Ova definicija je korisna jer rekurzivna definicija faktorijela glasi
- ,
za šta je neophodno da faktorijel broja 0 bude 1.
Kombinatorika
urediFaktorijel je važan u kombinatorici. Na primjer, postoji ukupno različitih načina da se rasporedi različitih objekata (ovi različiti načini rasporeda se zovu permutacije). Broj načina na koji se može izvući objekata iz skupa od objekata (broj kombinacija), je dat takozvanim binomnim koeficijentom:
Teorija brojeva
urediFaktorijel se mnogo koristi u teoriji brojeva. Konkretno, je uvijek djeljiv svim prostim brojevima do i uključujući . Posljedično, je kompozitan broj ako i samo ako
- .
Štaviše, imamo Vilsonovu teoremu koja tvrdi
ako i samo ako je prost broj.
Jedini faktorijel broja a koji je istovremeno i prost broj je broj 2, ali ima mnogo prostih brojeva oblika .
Dvostruki faktorijel n!!
uredinije jednako
- 8!! = 2 · 4 · 6 · 8 = 384
- 9!! = 1 · 3 · 5 · 7 · 9 = 945
Brzina rasta funkcije
urediKako raste, faktorijel postaje veći od svih polinomijalnih i eksponencijalnih funkcija od .
Kad je veliko, se procjenjuje sa velikom preciznošću koristeći Stirlingovu aproksimaciju:
Logaritam faktorijela se može iskoristiti da bi se izračunalo koliko će cifara u datom brojnom sistemu imati faktorijel zadatog broja. se može lako izračunati na sljedeći način:
Treba obratiti pažnju da ova funkcija, kad joj se nacrta grafik, izgleda približno linearna, za male vrijednosti; ali faktor raste do prilično velikih vrijednosti, premda jako sporo. Grafik za između 0 i 20,000 je prikazan desno.
Izračunavanje
urediVrijednost se može izračunati množenjem svih prirodnih brojeva do , ako nije veliko. Najveći broj za kojeg većina kalkulatora može izračunati vrijednost je , jer je . i su, tim redom, najveći brojevi čiji faktorijel može da stane u standardne cjelobrojne promjenljive kod tridesetdvobitnih i šezdesetčetvorobitnih računara. U praksi, većina programa računa ove male brojeve direktnim množenjem ili vađenjem rezultata iz tabele. Faktorijeli većih brojeva se računaju obično aproksimacijom, koristeći Stirlingovu formulu.
U teoriji brojeva i kombinatorici, često su potrebne tačne vrijednosti faktorijela velikih brojeva. Faktorijeli velikih brojeva se mogu izračunati direktnih množenjem, ali množenje redom odozdo nagore je neefikasno; bolje je rekurzijom podijeliti sekvencu tako da je veličina svakog potproizvoda manja.