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

uredi

Faktorijel 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

uredi

Faktorijel 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

uredi

Faktorijel 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!!

uredi

  nije jednako  

 
  • 8!! = 2 · 4 · 6 · 8 = 384
  • 9!! = 1 · 3 · 5 · 7 · 9 = 945

Brzina rasta funkcije

uredi
 
Grafik prirodnog logaritma faktorijela

Kako   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

uredi

Vrijednost   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.

Povezano

uredi