Факторијел

Факторијел првих неколико бројева и факторијел неких већих бројева
$n$	$n!$
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	7003504000000000000♠5040
8	7004403200000000000♠40320
9	7005362880000000000♠362880
10	7006362880000000000♠3628800
11	7007399168000000000♠39916800
12	7008479001600000000♠479001600
13	7009622702080000000♠6227020800
14	7010871782912000000♠87178291200
15	7012130767436800000♠1307674368000
16	7013209227898880000♠20922789888000
17	7014355687428096000♠355687428096000
18	7015640237370572800♠6402373705728000
19	7017121645100408832♠121645100408832000
20	7018243290200817664♠2432902008176640000
25	7025155112100400000♠1,551121004×10²⁵
50	7064304140932000000♠3,041409320×10⁶⁴
70	7100119785716700000♠1,197857167×10¹⁰⁰
100	7157933262154400000♠9,332621544×10¹⁵⁷
450	9000000000000000000♠1,733368733×10¹⁰⁰⁰
7003100000000000000♠1000	9000000000000000000♠4,023872601×10²⁵⁶⁷
7003324900000000000♠3249	9000000000000000000♠6,412337688×10¹⁰⁰⁰⁰
7004100000000000000♠10000	9000000000000000000♠2,846259681×10³⁵⁶⁵⁹
7004252060000000000♠25206	9000000000000000000♠1,205703438×10¹⁰⁰⁰⁰⁰
7005100000000000000♠100000	9000000000000000000♠2,824229408×10⁴⁵⁶⁵⁷³
7005205023000000000♠205023	9000000000000000000♠2,503898932×10^1000004
7006100000000000000♠1000000	9000000000000000000♠8,263931688×10^5565708
7100100000000000000♠10¹⁰⁰	10^{7101995657055180894♠10^{101,9981097754820}}

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

Историја

Концепт факторијала је настао независно у многим културама:

У индијској математици, један од најранијих познатих описа факторијала потиче из Анујогадвара-сутре,^[2] једног од канонских дела џаинске литературе, коме су додељени датуми који варирају од 300. п. н. е. до 400. године нове ере.^[3] Он одваја сортирани и обрнути редослед скупа ставки од осталих („мешовитих“) редоследа, процењујући број мешовитих поруџбина одузимањем два од уобичајене формуле производа за факторијел. Правило производа за пермутације је такође описао џаински монах Џинабадра из 6. века нове ере.^[2] Хинду научници су користили факторијалне формуле од најмање 1150. године, када је Баскара II поменуо факторијале у свом делу Лилавати, у вези са проблемом на које начине је Вишну могао да држи своја четири карактеристична предмета (шкољку, диск, буздован и лотосов цвет) у његове четири руке, и сличан проблем за десеторуког бога.^[4]
У математици Блиског истока, хебрејска мистична књига о стварању Сефер Јецирах, из талмудског периода (200. до 500. не), наводи факторијале до 7! као део истраживања о броју речи које се могу формирати од хебрејског алфабета.^[5]^[6] Факторијале је из сличних разлога проучавао и арапски граматичар из 8. века ел-Фарахиди. Factorials were also studied for similar reasons by 8th-century Arab grammarian [[]].^[5] Арапски математичар Ибн ел-Хајтам (такође познат као Алхазен, око 965 – око 1040) био је први који је формулисао Вилсонову теорему повезујући факторијеле са простим бројевима.^[7]
У Европи, иако је грчка математика укључивала неку комбинаторику, и Платон је чувено користио 5.040 (факторијал) као популацију идеалне заједнице, делом због његових својстава дељивости,^[8] не постоје директни докази о древном грчком проучавању факторијала. Уместо тога, први рад о факторијелима у Европи био је од стране јеврејских научника као што је Шабетај Доноло, објашњавајући одломак Сефер Јецира.^[9] Године 1677, британски писац Фабијан Стедман описао је примену факторијела за промену звоњења, музичку уметност која укључује звоњење неколико подешених звона.^[10]^[11]

Од касног 15. века па надаље, факторијели су постали предмет проучавања западних математичара. У расправи из 1494. године, италијански математичар Лука Пакиоли израчунао је факторијеле до 11!, у вези са проблемом распореда трпезаријских столова.^[12] Кристофер Клавијус је расправљао о факторијелима у коментару из 1603. о делу Јоханеса де Сакробоска, а током 1640-их, француски полимат Марин Мерсен је објавио велике (али не сасвим тачне) табеле факторијала, до 64!, засноване на Клавијусовом делу.^[13] Степени ред за експоненцијалну функцију, са реципрочним факторијелима за њене коефицијенте, први је формулисао Исак Њутн 1676. године у писму Готфриду Вилхелму Лајбницу.^[14] Друга важна дела ране европске математике о факторијелима укључују опсежно покривање у расправи Џона Волиса из 1685. године, студију њихових приближних вредности за велике вредности $n$ коју је урадио Абрам де Моавр из 1721. године, писмо Џејмса Стирлинга де Моавру из 1729. у којем се наводи оно што је постало познато као Стирлингова апроксимација, и у исто време рад Даниела Бернулија и Леонхарда Ојлера који формулишу континуирано проширење факторијелне функције на гама функцију.^[15] Адријен-Мари Лежандр је укључио Лежандрову формулу, описујући експоненте у факторизацији факторијела у просте степене, у текст из 1808. о теорији бројева.^[16]

Ознаку $n!$ за факторијале је увео француски математичар Кристијан Крамп 1808. године.^[17] Коришћене су и многе друге ознаке. Још једна каснија нотација, у којој је аргумент факторијала био напола затворен са леве и доње стране кутије, била је популарна неко време у Британији и Америци, али је изашла из употребе, можда зато што је тешко припремити за штампу.^[17] Реч „факторијел“ (првобитно француски: factorielle) је први пут употребио 1800. године Луј Франсоа Антоан Арбогаст,^[18] у првом раду о Фаа-ди-Бруновој формули,^[19] али се односи на општији концепт производа аритметичких прогресија. „Фактори“ на које се овај назив односи су чланови формуле производа за факторијел.^[20]

Види још

Референце

^ Graham, Knuth & Patashnik 1988, стр. 111.
^ ^а ^б Datta, Bibhutibhusan; Singh, Awadhesh Narayan (2019). „Use of permutations and combinations in India”. Ур.: Kolachana, Aditya; Mahesh, K.; Ramasubramanian, K. Studies in Indian Mathematics and Astronomy: Selected Articles of Kripa Shankar Shukla. Sources and Studies in the History of Mathematics and Physical Sciences. Springer Singapore. стр. 356—376. S2CID 191141516. doi:10.1007/978-981-13-7326-8_18. . Revised by K. S. Shukla from a paper in. Indian Journal of History of Science. 27 (3): 231—249. 1992. Недостаје или је празан параметар |title= (помоћ), , MR 1189487. See p. 363.
^ Jadhav, Dipak (август 2021). „Jaina Thoughts on Unity Not Being a Number”. History of Science in South Asia. University of Alberta Libraries. 9: 209—231. doi:10.18732/hssa67  . . See discussion of dating on p. 211.
^ Biggs, Norman L. (мај 1979). „The roots of combinatorics”. Historia Mathematica. 6 (2): 109—136. MR 0530622. doi:10.1016/0315-0860(79)90074-0  .
^ ^а ^б Katz, Victor J. (јун 1994). „Ethnomathematics in the classroom”. For the Learning of Mathematics. 14 (2): 26—30. JSTOR 40248112.
^ Sefer Yetzirah at Wikisource, Chapter IV, Section 4
^ Rashed, Roshdi (1980). „Ibn al-Haytham et le théorème de Wilson”. Archive for History of Exact Sciences (на језику: француски). 22 (4): 305—321. MR 595903. S2CID 120885025. doi:10.1007/BF00717654.
^ Acerbi, F. (2003). „On the shoulders of Hipparchus: a reappraisal of ancient Greek combinatorics”. Archive for History of Exact Sciences. 57 (6): 465—502. JSTOR 41134173. MR 2004966. S2CID 122758966. doi:10.1007/s00407-003-0067-0.
^ Katz, Victor J. (2013). „Chapter 4: Jewish combinatorics”. Ур.: Wilson, Robin; Watkins, John J. Combinatorics: Ancient & Modern. Oxford University Press. стр. 109–121. ISBN 978-0-19-965659-2. See p. 111.
^ Hunt, Katherine (мај 2018). „The Art of Changes: Bell-Ringing, Anagrams, and the Culture of Combination in Seventeenth-Century England” (PDF). Journal of Medieval and Early Modern Studies. 48 (2): 387—412. doi:10.1215/10829636-4403136.
^ Stedman, Fabian (1677). Campanalogia. London. стр. 6–9. The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed.
^ Knobloch, Eberhard (2013). „Chapter 5: Renaissance combinatorics”. Ур.: Wilson, Robin; Watkins, John J. Combinatorics: Ancient & Modern. Oxford University Press. стр. 123–145. ISBN 978-0-19-965659-2. See p. 126.
^ Knobloch 2013, стр. 130–133.
^ Ebbinghaus, H.-D.; Hermes, H.; Hirzebruch, F.; Koecher, M.; Mainzer, K.; Neukirch, J.; Prestel, A.; Remmert, R. (1990). Numbers. Graduate Texts in Mathematics. 123. New York: Springer-Verlag. стр. 131. ISBN 0-387-97202-1. MR 1066206. doi:10.1007/978-1-4612-1005-4.
^ Dutka, Jacques (1991). „The early history of the factorial function”. Archive for History of Exact Sciences. 43 (3): 225—249. JSTOR 41133918. MR 1171521. S2CID 122237769. doi:10.1007/BF00389433.
^ Dickson, Leonard E. (1919). „Chapter IX: Divisibility of factorials and multinomial coefficients”. History of the Theory of Numbers. 1. Carnegie Institution of Washington. стр. 263—278. See in particular p. 263.
^ ^а ^б Cajori, Florian (1929). „448–449. Factorial " $n$ "”. A History of Mathematical Notations, Volume II: Notations Mainly in Higher Mathematics. The Open Court Publishing Company. стр. 71—77.
^ Miller, Jeff. „Earliest Known Uses of Some of the Words of Mathematics (F)”. MacTutor History of Mathematics archive. University of St Andrews.
^ Craik, Alex D. D. (2005). „Prehistory of Faà di Bruno's formula”. The American Mathematical Monthly. 112 (2): 119—130. JSTOR 30037410. MR 2121322. S2CID 45380805. doi:10.1080/00029890.2005.11920176.
^ Arbogast, Louis François Antoine (1800). Du calcul des dérivations (на језику: француски). Strasbourg: L'imprimerie de Levrault, frères. стр. 364—365.

Литература

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
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.

[FOOTNOTEGrahamKnuthPatashnik1988111-1] Graham, Knuth & Patashnik 1988, стр. 111.

[datta-singh-2] а ^б Datta, Bibhutibhusan; Singh, Awadhesh Narayan (2019). „Use of permutations and combinations in India”. Ур.: Kolachana, Aditya; Mahesh, K.; Ramasubramanian, K. Studies in Indian Mathematics and Astronomy: Selected Articles of Kripa Shankar Shukla. Sources and Studies in the History of Mathematics and Physical Sciences. Springer Singapore. стр. 356—376. S2CID 191141516. doi:10.1007/978-981-13-7326-8_18. . Revised by K. S. Shukla from a paper in. Indian Journal of History of Science. 27 (3): 231—249. 1992. Недостаје или је празан параметар |title= (помоћ), , MR 1189487. See p. 363.

[3] Jadhav, Dipak (август 2021). „Jaina Thoughts on Unity Not Being a Number”. History of Science in South Asia. University of Alberta Libraries. 9: 209—231. doi:10.18732/hssa67  . . See discussion of dating on p. 211.

[4] Biggs, Norman L. (мај 1979). „The roots of combinatorics”. Historia Mathematica. 6 (2): 109—136. MR 0530622. doi:10.1016/0315-0860(79)90074-0  .

[katz-5] а ^б Katz, Victor J. (јун 1994). „Ethnomathematics in the classroom”. For the Learning of Mathematics. 14 (2): 26—30. JSTOR 40248112.

[6] Sefer Yetzirah at Wikisource, Chapter IV, Section 4

[7] Rashed, Roshdi (1980). „Ibn al-Haytham et le théorème de Wilson”. Archive for History of Exact Sciences (на језику: француски). 22 (4): 305—321. MR 595903. S2CID 120885025. doi:10.1007/BF00717654.

[8] Acerbi, F. (2003). „On the shoulders of Hipparchus: a reappraisal of ancient Greek combinatorics”. Archive for History of Exact Sciences. 57 (6): 465—502. JSTOR 41134173. MR 2004966. S2CID 122758966. doi:10.1007/s00407-003-0067-0.

[9] Katz, Victor J. (2013). „Chapter 4: Jewish combinatorics”. Ур.: Wilson, Robin; Watkins, John J. Combinatorics: Ancient & Modern. Oxford University Press. стр. 109–121. ISBN 978-0-19-965659-2. See p. 111.

[10] Hunt, Katherine (мај 2018). „The Art of Changes: Bell-Ringing, Anagrams, and the Culture of Combination in Seventeenth-Century England” (PDF). Journal of Medieval and Early Modern Studies. 48 (2): 387—412. doi:10.1215/10829636-4403136.

[11] Stedman, Fabian (1677). Campanalogia. London. стр. 6–9. The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed.

[12] Knobloch, Eberhard (2013). „Chapter 5: Renaissance combinatorics”. Ур.: Wilson, Robin; Watkins, John J. Combinatorics: Ancient & Modern. Oxford University Press. стр. 123–145. ISBN 978-0-19-965659-2. See p. 126.

[FOOTNOTEKnobloch2013130–133-13] Knobloch 2013, стр. 130–133.

[exponential-series-14] Ebbinghaus, H.-D.; Hermes, H.; Hirzebruch, F.; Koecher, M.; Mainzer, K.; Neukirch, J.; Prestel, A.; Remmert, R. (1990). Numbers. Graduate Texts in Mathematics. 123. New York: Springer-Verlag. стр. 131. ISBN 0-387-97202-1. MR 1066206. doi:10.1007/978-1-4612-1005-4.

[15] Dutka, Jacques (1991). „The early history of the factorial function”. Archive for History of Exact Sciences. 43 (3): 225—249. JSTOR 41133918. MR 1171521. S2CID 122237769. doi:10.1007/BF00389433.

[16] Dickson, Leonard E. (1919). „Chapter IX: Divisibility of factorials and multinomial coefficients”. History of the Theory of Numbers. 1. Carnegie Institution of Washington. стр. 263—278. See in particular p. 263.

[cajori-17] а ^б Cajori, Florian (1929). „448–449. Factorial " $n$ "”. A History of Mathematical Notations, Volume II: Notations Mainly in Higher Mathematics. The Open Court Publishing Company. стр. 71—77.

[18] Miller, Jeff. „Earliest Known Uses of Some of the Words of Mathematics (F)”. MacTutor History of Mathematics archive. University of St Andrews.

[craik-19] Craik, Alex D. D. (2005). „Prehistory of Faà di Bruno's formula”. The American Mathematical Monthly. 112 (2): 119—130. JSTOR 30037410. MR 2121322. S2CID 45380805. doi:10.1080/00029890.2005.11920176.

[20] Arbogast, Louis François Antoine (1800). Du calcul des dérivations (на језику: француски). Strasbourg: L'imprimerie de Levrault, frères. стр. 364—365.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]