Факторијел

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

n	n!
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	7003504000000000000♠5,040
8	7004403200000000000♠40,320
9	7005362880000000000♠362,880
10	7006362880000000000♠3,628,800
11	7007399168000000000♠39,916,800
12	7008479001600000000♠479,001,600
13	7009622702080000000♠6,227,020,800
14	7010871782912000000♠87,178,291,200
15	7012130767436800000♠1,307,674,368,000
16	7013209227898880000♠20,922,789,888,000
17	7014355687428096000♠355,687,428,096,000
18	7015640237370572800♠6,402,373,705,728,000
19	7017121645100408832♠121,645,100,408,832,000
20	7018243290200817664♠2,432,902,008,176,640,000
25	7025155112100400000♠1,551,121,004×1025
50	7064304140932000000♠3,041,409,320×1064
70	7100119785716700000♠1,197,857,167×10100
100	7157933262154400000♠9,332,621,544×10157
450	9000000000000000000♠1,733,368,733×101,000
7003100000000000000♠1,000	9000000000000000000♠4,023,872,601×102,567
7003324900000000000♠3,249	9000000000000000000♠6,412,337,688×1010,000
7004100000000000000♠10,000	9000000000000000000♠2,846,259,681×1035,659
7004252060000000000♠25,206	9000000000000000000♠1,205,703,438×10100,000
7005100000000000000♠100,000	9000000000000000000♠2,824,229,408×10456,573
7005205023000000000♠205,023	9000000000000000000♠2,503,898,932×101,000,004
7006100000000000000♠1,000,000	9000000000000000000♠8,263,931,688×105,565,708
7100100000000000000♠10100	107101995657055180894♠10101,998,109,775,4820

У математици, факторијел ненегативног цијелог броја $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. године. Вредност 0! је 1, према конвенцији за празан производ.

Операција факторијел се среће у многим областима математике, а посебно у комбинаторици, алгебри и математичкој анализи. Његова најосновнија употреба је бројање могућих различитих низова -- пермутација -- од n различитих објеката: којих има n!.

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

Дефиниција

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

$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\geq 2.\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$ одоздо нагоре је неефикасно; боље је рекурзијом подијелити секвенцу тако да је величина сваког потпроизвода мања.

Види још

• Гама функција
• Леви факторијел

Литература

• Bostock, Linda; Chandler, Suzanne; Rourke, C. (1. 11. 2014), Further Pure Mathematics (на језику: енглески), Nelson Thornes, ISBN 9780859501033 
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1988), Concrete Mathematics, Reading, MA: Addison-Wesley, ISBN 978-0-201-14236-5 
• Guy, Richard K. (2004), „E24 Irrationality sequences”, Unsolved problems in number theory (3rd изд.), Springer-Verlag, ISBN 978-0-387-20860-2, Zbl 1058.11001 
• Higgins, Peter (2008), Number Story: From Counting to Cryptography, New York: Copernicus, ISBN 978-1-84800-000-1 
• Stedman, Fabian (1677), Campanalogia, London 
• Hadamard, M. J. (1894), „Sur L’Expression Du Produit 1·2·3· · · · ·(n−1) Par Une Fonction Entière” (PDF), Œuvres de Jacques Hadamard (на језику: French), Paris (1968): Centre National de la Recherche Scientifiques CS1 одржавање: Непрепознат језик (веза)
• Ramanujan, Srinivasa (1988), The Lost Notebook and Other Unpublished Papers, Springer Berlin, стр. 339, ISBN 978-3-540-18726-4 

Спољашње везе

• Hazewinkel Michiel, ур. (2001). „Factorial”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Weisstein, Eric W. „Factorial”. MathWorld. 
• Factorial at PlanetMath.org.