Факторијел

Из Википедије, слободне енциклопедије
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-факторијел. Ознаку је први увео Кристијан Крамп, 1808. године.

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

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

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

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

,

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

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

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

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

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

.

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

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

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

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

није једнако

  • 8!! = 2 · 4 · 6 · 8 = 384
  • 9!! = 1 · 3 · 5 · 7 · 9 = 945

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

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

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

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

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

Треба обратити пажњу да ова функција, кад јој се нацрта график, изгледа приближно линеарна, за мале вриједности; али фактор расте до прилично великих вриједности, премда јако споро. График за између 0 и 20,000 је приказан десно.

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

Вриједност се може израчунати множењем свих природних бројева до , ако није велико. Највећи број за којег већина калкулатора може израчунати вриједност је , јер је . и су, тим редом, највећи бројеви чији факторијел може да стане у стандардне цјелобројне промјенљиве код тридесетдвобитних и шездесетчетворобитних рачунара. У пракси, већина програма рачуна ове мале бројеве директним множењем или вађењем резултата из табеле. Факторијели већих бројева се рачунају обично апроксимацијом, користећи Стирлингову формулу.

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

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