Faktorijel

${\displaystyle n}$	${\displaystyle n!}$
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

faktorijel (engl. factorial, prema lat. factor), u matematici, funkcija koja svakom nenegativnom cijelom broju ${\displaystyle n}$ pridružuje proizvod svih pozitivnih brojeva manjih ili jednakih ${\displaystyle n}$. Na primjer,

${\displaystyle 5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120\ }$

i

${\displaystyle 6!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6=720\ }$

gdje ${\displaystyle n!}$ predstavlja n-faktorijel. Oznaku ${\displaystyle n!}$ je prvi uveo Kristijan Kramp, 1808. godine.

Definicija

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

${\displaystyle n!=\prod _{k=1}^{n}k\qquad \forall n\in \mathbb {N} .\!}$

Gornja definicija pretpostavlja da je:

${\displaystyle 0!=1\ }$

Ova definicija je korisna jer rekurzivna definicija faktorijela glasi

${\displaystyle (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 ${\displaystyle n!}$ različitih načina da se rasporedi ${\displaystyle n}$ različitih objekata (ovi različiti načini rasporeda se zovu permutacije). Broj načina na koji se može izvući ${\displaystyle k}$ objekata iz skupa od ${\displaystyle n}$ objekata (broj kombinacija), je dat takozvanim binomnim koeficijentom:

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

Teorija brojeva

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

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

Štaviše, imamo Vilsonovu teoremu koja tvrdi

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

ako i samo ako je ${\displaystyle p}$ prost broj.

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

Dvostruki faktorijel n!!

${\displaystyle n!!}$ nije jednako ${\displaystyle (n!)!}$

${\displaystyle n!!=\left\{{\begin{matrix}1,\qquad \quad \ &&{\mbox{za }}n=0{\mbox{ ili }}n=1;\\n(n-2)!!&&{\mbox{za }}n\geq 2.\qquad \qquad \end{matrix}}\right.}$

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

Brzina rasta funkcije

Kako ${\displaystyle n}$ raste, faktorijel ${\displaystyle n!}$ postaje veći od svih polinomijalnih i eksponencijalnih funkcija od ${\displaystyle n}$.

Kad je ${\displaystyle n}$ veliko, ${\displaystyle n!}$ se procjenjuje sa velikom preciznošću koristeći Stirlingovu aproksimaciju:

${\displaystyle 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. ${\displaystyle log(n!)}$ se može lako izračunati na sljedeći način:

${\displaystyle \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 ${\displaystyle {\log n!} \over n}$ raste do prilično velikih vrijednosti, premda jako sporo. Grafik ${\displaystyle log(n!)}$ za ${\displaystyle n}$ između 0 i 20,000 je prikazan desno.

Izračunavanje

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

Vidi još

• gama funkcija
• lijevi faktorijel
• Stirlingova formula