Faktorijel

Izvor: Wikipedia
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[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\ge2.\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.

Vidi još[uredi - уреди]