Faktorijel

Faktorijel prvih nekoliko brojeva i faktorijel nekih većih brojeva


**faktorijel** (engl. *factorial*, prema lat. *factor*), u matematici, funkcija koja svakom nenegativnom cijelom broju n pridružuje proizvod svih pozitivnih brojeva manjih ili jednakih n. Na primjer,
:5 ! = 1\cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120 \ 
:
:i
:
:6 ! = 1\cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6= 720 \ 
gdje n! predstavlja n-faktorijel.
Oznaku n! je prvi uveo Kristijan Kramp, 1808. godine.

## Definicija
Faktorijel se formalno definiše na sljedeći način

: n!=\prod_{k=1}^n k \qquad \forall n \in \mathbb{N}.\!

Gornja definicija pretpostavlja da je:

:0! = 1 \ 

Ova definicija je korisna jer rekurzivna definicija faktorijela glasi

:(n + 1)! = n! (n + 1),

za šta je neophodno da faktorijel broja 0 bude 1.

## Kombinatorika
Faktorijel je važan u kombinatorici. Na primjer, postoji ukupno n! različitih načina da se rasporedi n različitih objekata (ovi različiti načini rasporeda se zovu *permutacije*). Broj načina na koji se može izvući k objekata iz skupa od n objekata (broj *kombinacija*), je dat takozvanim binomnim koeficijentom:

{n\choose k}={n!\over k!(n-k)!}

## Teorija brojeva
Faktorijel se mnogo koristi u teoriji brojeva. Konkretno, n! je uvijek djeljiv svim prostim brojevima do i uključujući n. Posljedično, n > 5 je kompozitan broj ako i samo ako

:(n-1)!\ \equiv\ 0 \ ({\rm mod}\ n).

Štaviše, imamo Vilsonovu teoremu koja tvrdi

:(p-1)!\ \equiv\ -1 \ ({\rm mod}\ p)

ako i samo ako je p prost broj.

Jedini faktorijel broja a koji je istovremeno i prost broj je broj 2, ali ima mnogo prostih brojeva oblika n! \pm 1.

## Dvostruki faktorijel n!!
n!! nije jednako (n!)!

:
  n!!=
  \left\{
   \begin{matrix}
    1,\qquad\quad\ &&\mbox{za }n=0\mbox{ ili }n=1;
   \\
    n(n-2)!!&&\mbox{za }n\ge2.\qquad\qquad
   \end{matrix}
  \right.
 
* 8!! = 2 · 4 · 6 · 8 = 384
* 9!! = 1 · 3 · 5 · 7 · 9 = 945

## Brzina rasta funkcije

Kako n raste, faktorijel n! postaje veći od svih polinomijalnih i eksponencijalnih funkcija od n.

Kad je n veliko, n! se procjenjuje sa velikom preciznošću koristeći Stirlingovu aproksimaciju:

:n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n.

Logaritam faktorijela se može iskoristiti da bi se izračunalo koliko će cifara u datom brojnom sistemu imati faktorijel zadatog broja. log(n!) se može lako izračunati na sljedeći način:

:\sum_{k=1}^n{\log k}.

Treba obratiti pažnju da ova funkcija, kad joj se nacrta grafik, izgleda približno linearna, za male vrijednosti; ali faktor {\log n!} \over n raste do prilično velikih vrijednosti, premda jako sporo. Grafik log(n!) za n između 0 i 20,000 je prikazan desno.

## Izračunavanje
Vrijednost n! se može izračunati množenjem svih prirodnih brojeva do n, ako n nije veliko. Najveći broj za kojeg većina kalkulatora može izračunati vrijednost je 69!, jer je 70! > 10^{100}. 11! i 20! 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 1 \cdot 2 \cdot ... \cdot n odozdo nagore je neefikasno; bolje je rekurzijom podijeliti sekvencu tako da je veličina svakog potproizvoda manja.

## Povezano
* gama funkcija
* lijevi faktorijel
* Stirlingova formula