Факторијел

Из Википедије, слободне енциклопедије
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

Факторијел првих неколико бројева и факторијел неких већих бројева

У математици, факторијел ненегативног цијелог броја n је производ свих позитивних бројева мањих или једнаких n. На примјер,

5 ! = 1\cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120 \
и
6 ! = 1\cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6= 720 \

гдје n! представља n-факторијел. Ознаку n! је први увео Кристијан Крамп, 1808. године.

Дефиниција[уреди]

Факторијел се формално дефинише на сљедећи начин

 n!=\prod_{k=1}^n k \qquad \forall n \in \mathbb{N}.\!

Горња дефиниција претпоставља да је:

0! = 1 \

Ова дефиниција је корисна јер рекурзивна дефиниција факторијела гласи

(n + 1)! = n! (n + 1),

за шта је неопходно да факторијел броја 0 буде 1.

Комбинаторика[уреди]

Факторијел је важан у комбинаторици. На примјер, постоји укупно n! различитих начина да се распореди n различитих објеката (ови различити начини распореда се зову пермутације). Број начина на који се може извући k објеката из скупа од n објеката (број комбинација), је дат такозваним биномним коефицијентом:

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

Теорија бројева[уреди]

Факторијел се много користи у теорији бројева. Конкретно, n! је увијек дјељив свим простим бројевима до и укључујући n. Посљедично, n > 5 је композитан број ако и само ако

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

Штавише, имамо Вилсонову теорему која тврди

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

ако и само ако је p прост број.

Једини факторијел броја а који је истовремено и прост број је број 2, али има много простих бројева облика n! \pm 1.

Двоструки факторијел n!![уреди]

n!! није једнако (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

Брзина раста функције[уреди]

График природног логаритма факторијела

Како n расте, факторијел n! постаје већи од свих полиномијалних и експоненцијалних функција од n.

Кад је n велико, n! се процјењује са великом прецизношћу користећи Стирлингову апроксимацију:

n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n.

Логаритам факторијела се може искористити да би се израчунало колико ће цифара у датом бројном систему имати факторијел задатог броја. log(n!) се може лако израчунати на сљедећи начин:

\sum_{k=1}^n{\log k}.

Треба обратити пажњу да ова функција, кад јој се нацрта график, изгледа приближно линеарна, за мале вриједности; али фактор {\log n!} \over n расте до прилично великих вриједности, премда јако споро. График log(n!) за n између 0 и 20,000 је приказан десно.

Израчунавање[уреди]

Вриједност n! се може израчунати множењем свих природних бројева до n, ако n није велико. Највећи број за којег већина калкулатора може израчунати вриједност је 69!, јер је 70! > 10^{100}. 11! и 20! су, тим редом, највећи бројеви чији факторијел може да стане у стандардне цјелобројне промјенљиве код тридесетдвобитних и шездесетчетворобитних рачунара. У пракси, већина програма рачуна ове мале бројеве директним множењем или вађењем резултата из табеле. Факторијели већих бројева се рачунају обично апроксимацијом, користећи Стирлингову формулу.

У теорији бројева и комбинаторици, често су потребне тачне вриједности факторијела великих бројева. Факторијели великих бројева се могу израчунати директних множењем, али множење редом 1 \cdot 2 \cdot ... \cdot n одоздо нагоре је неефикасно; боље је рекурзијом подијелити секвенцу тако да је величина сваког потпроизвода мања.

Види још[уреди]