Факторијел

Из Википедије, слободне енциклопедије

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! > 10100. 11! и 20! су, тим редом, највећи бројеви чији факторијел може да стане у стандардне цјелобројне промјенљиве код тридесетдвобитних и шездесетчетворобитних рачунара. У пракси, већина програма рачуна ове мале бројеве директним множењем или вађењем резултата из табеле. Факторијели већих бројева се рачунају обично апроксимацијом, користећи Стирлингову формулу.

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

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


- Добављено из „http://sr.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D1%98%D0%B5%D0%BB“