Faktorijel

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,

$n$	$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... · 10⁶⁴
70	1,19785717... · 10¹⁰⁰
450	1,73336873... · 10^{1 000}
3249	6,41233768... · 10^{10 000}
25206	1,205703438... · 10^{100 000}

Faktorijel prvih nekoliko brojeva i faktorijel nekih većih brojeva

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 uredi

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 uredi

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 uredi

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

$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\geq 2.\qquad \qquad \end{matrix}}\right.

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

Brzina rasta funkcije uredi

Grafik prirodnog logaritma faktorijela

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 uredi

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.