Faktorijel

$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... · 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

U matematici, faktorijel nenegativnog cijelog broja $n$ je 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

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

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.

Vidi još

• Gama funkcija
• Levi faktorijel