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

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\mathrm{\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:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{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(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

Štaviše, imamo Vilsonovu teoremu koja tvrdi

$(p-1)!\equiv -1(\mathrm{m}\mathrm{o}\mathrm{d}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!!=\{\begin{array}{ccc}1,& & \text{za }n=0\text{ ili }n=1;\\ n(n-2)!!& & \text{za }n\ge 2.\end{array}$

• 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 $\frac{\log n!}{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