Faktorijel

Faktorijel prvih nekoliko brojeva i faktorijel nekih većih brojeva
$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}}

U matematici, faktorijel nenegativnog cijelog broja $n$ je proizvod svih pozitivnih brojeva manjih ili jednakih $n$ . Na primjer, $5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120\$ i $6!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6=720\$ , gdje $n!$ predstavlja n-faktorijel. Oznaku $n!$ je prvi uveo Kristijan Kramp, 1808. godine. Vrednost 0! je 1, prema konvenciji za prazan proizvod.^[1]

Operacija faktorijel se sreće u mnogim oblastima matematike, a posebno u kombinatorici, algebri i matematičkoj analizi. Njegova najosnovnija upotreba je brojanje mogućih različitih nizova -- permutacija -- od $n$ različitih objekata: kojih ima $n!$ .

Faktorijelska funkcija se isto tako može proširiti na argumente koji nisu celobrojni uz zadržavanje najvažnijih svojstava; to uključuje napredniju matematiku, i tehnike iz matematičke analize.

Definicija uredi

Faktorijel se formalno definiše na sljedeći način

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

Gornja definicija pretpostavlja da je:

0!=1\

Ova definicija je korisna jer rekurzivna definicija faktorijela glasi

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

,

za šta je neophodno da faktorijel broja 0 bude 1.

Kombinatorika uredi

Faktorijel je važan u kombinatorici. Na primjer, postoji ukupno $n!$ različitih načina da se rasporedi $n$ različitih objekata (ovi različiti načini rasporeda se zovu permutacije). Broj načina na koji se može izvući $k$ objekata iz skupa od $n$ objekata (broj kombinacija), je dat takozvanim binomnim koeficijentom:

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

Teorija brojeva uredi

Faktorijel se mnogo koristi u teoriji brojeva. Konkretno, $n!$ je uvijek djeljiv svim prostim brojevima do i uključujući $n$ . Posljedično, $n>5$ je kompozitan broj ako i samo ako

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

.

Štaviše, imamo Vilsonovu teoremu koja tvrdi

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

ako i samo ako je $p$ prost broj.

Jedini faktorijel broja a koji je istovremeno i prost broj je broj 2, ali ima mnogo prostih brojeva oblika $n!\pm 1$ .

Dvostruki faktorijel n!! uredi

$n!!$ nije jednako $(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

Brzina rasta funkcije uredi

Grafik prirodnog logaritma faktorijela

Kako $n$ raste, faktorijel $n!$ postaje veći od svih polinomijalnih i eksponencijalnih funkcija od $n$ .

Kad je $n$ veliko, $n!$ se procjenjuje sa velikom preciznošću koristeći Stirlingovu aproksimaciju:

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

Logaritam faktorijela se može iskoristiti da bi se izračunalo koliko će cifara u datom brojnom sistemu imati faktorijel zadatog broja. $log(n!)$ se može lako izračunati na sljedeći način:

\sum _{k=1}^{n}{\log k}.

Treba obratiti pažnju da ova funkcija, kad joj se nacrta grafik, izgleda približno linearna, za male vrijednosti; ali faktor ${\log n!} \over n$ raste do prilično velikih vrijednosti, premda jako sporo. Grafik $log(n!)$ za $n$ između 0 i 20,000 je prikazan desno.

Izračunavanje uredi

Vrijednost $n!$ se može izračunati množenjem svih prirodnih brojeva do $n$ , ako $n$ nije veliko. Najveći broj za kojeg većina kalkulatora može izračunati vrijednost je $69!$ , jer je $70!>10^{100}$ . $11!$ i $20!$ su, tim redom, najveći brojevi čiji faktorijel može da stane u standardne cjelobrojne promjenljive kod tridesetdvobitnih i šezdesetčetvorobitnih računara. U praksi, većina programa računa ove male brojeve direktnim množenjem ili vađenjem rezultata iz tabele. Faktorijeli većih brojeva se računaju obično aproksimacijom, koristeći Stirlingovu formulu.

U teoriji brojeva i kombinatorici, često su potrebne tačne vrijednosti faktorijela velikih brojeva. Faktorijeli velikih brojeva se mogu izračunati direktnih množenjem, ali množenje redom $1\cdot 2\cdot ...\cdot n$ odozdo nagore je neefikasno; bolje je rekurzijom podijeliti sekvencu tako da je veličina svakog potproizvoda manja.

Istorija uredi

Koncept faktorijala je nastao nezavisno u mnogim kulturama:

U indijskoj matematici, jedan od najranijih poznatih opisa faktorijala potiče iz Anujogadvara-sutre,^[2] jednog od kanonskih dela džainske literature, kome su dodeljeni datumi koji variraju od 300. p. n. e. do 400. godine nove ere.^[3] On odvaja sortirani i obrnuti redosled skupa stavki od ostalih („mešovitih“) redosleda, procenjujući broj mešovitih porudžbina oduzimanjem dva od uobičajene formule proizvoda za faktorijel. Pravilo proizvoda za permutacije je takođe opisao džainski monah Džinabadra iz 6. veka nove ere.^[2] Hindu naučnici su koristili faktorijalne formule od najmanje 1150. godine, kada je Baskara II pomenuo faktorijale u svom delu Lilavati, u vezi sa problemom na koje načine je Višnu mogao da drži svoja četiri karakteristična predmeta (školjku, disk, buzdovan i lotosov cvet) u njegove četiri ruke, i sličan problem za desetorukog boga.^[4]
U matematici Bliskog istoka, hebrejska mistična knjiga o stvaranju Sefer Jecirah, iz talmudskog perioda (200. do 500. ne), navodi faktorijale do 7! kao deo istraživanja o broju reči koje se mogu formirati od hebrejskog alfabeta.^[5]^[6] Faktorijale je iz sličnih razloga proučavao i arapski gramatičar iz 8. veka el-Farahidi. Factorials were also studied for similar reasons by 8th-century Arab grammarian [[]].^[5] Arapski matematičar Ibn el-Hajtam (takođe poznat kao Alhazen, oko 965 – oko 1040) bio je prvi koji je formulisao Vilsonovu teoremu povezujući faktorijele sa prostim brojevima.^[7]
U Evropi, iako je grčka matematika uključivala neku kombinatoriku, i Platon je čuveno koristio 5.040 (faktorijal) kao populaciju idealne zajednice, delom zbog njegovih svojstava deljivosti,^[8] ne postoje direktni dokazi o drevnom grčkom proučavanju faktorijala. Umesto toga, prvi rad o faktorijelima u Evropi bio je od strane jevrejskih naučnika kao što je Šabetaj Donolo, objašnjavajući odlomak Sefer Jecira.^[9] Godine 1677, britanski pisac Fabijan Stedman opisao je primenu faktorijela za promenu zvonjenja, muzičku umetnost koja uključuje zvonjenje nekoliko podešenih zvona.^[10]^[11]

Od kasnog 15. veka pa nadalje, faktorijeli su postali predmet proučavanja zapadnih matematičara. U raspravi iz 1494. godine, italijanski matematičar Luka Pakioli izračunao je faktorijele do 11!, u vezi sa problemom rasporeda trpezarijskih stolova.^[12] Kristofer Klavijus je raspravljao o faktorijelima u komentaru iz 1603. o delu Johanesa de Sakroboska, a tokom 1640-ih, francuski polimat Marin Mersen je objavio velike (ali ne sasvim tačne) tabele faktorijala, do 64!, zasnovane na Klavijusovom delu.^[13] Stepeni red za eksponencijalnu funkciju, sa recipročnim faktorijelima za njene koeficijente, prvi je formulisao Isak Njutn 1676. godine u pismu Gotfridu Vilhelmu Lajbnicu.^[14] Druga važna dela rane evropske matematike o faktorijelima uključuju opsežno pokrivanje u raspravi Džona Volisa iz 1685. godine, studiju njihovih približnih vrednosti za velike vrednosti $n$ koju je uradio Abram de Moavr iz 1721. godine, pismo Džejmsa Stirlinga de Moavru iz 1729. u kojem se navodi ono što je postalo poznato kao Stirlingova aproksimacija, i u isto vreme rad Daniela Bernulija i Leonharda Ojlera koji formulišu kontinuirano proširenje faktorijelne funkcije na gama funkciju.^[15] Adrijen-Mari Ležandr je uključio Ležandrovu formulu, opisujući eksponente u faktorizaciji faktorijela u proste stepene, u tekst iz 1808. o teoriji brojeva.^[16]

Oznaku $n!$ za faktorijale je uveo francuski matematičar Kristijan Kramp 1808. godine.^[17] Korišćene su i mnoge druge oznake. Još jedna kasnija notacija, u kojoj je argument faktorijala bio napola zatvoren sa leve i donje strane kutije, bila je popularna neko vreme u Britaniji i Americi, ali je izašla iz upotrebe, možda zato što je teško pripremiti za štampu.^[17] Reč „faktorijel“ (prvobitno francuski: factorielle) je prvi put upotrebio 1800. godine Luj Fransoa Antoan Arbogast,^[18] u prvom radu o Faa-di-Brunovoj formuli,^[19] ali se odnosi na opštiji koncept proizvoda aritmetičkih progresija. „Faktori“ na koje se ovaj naziv odnosi su članovi formule proizvoda za faktorijel.^[20]

Vidi još uredi

Reference uredi

^ Graham, Knuth & Patashnik 1988, str. 111.
^ ^a ^b Datta, Bibhutibhusan; Singh, Awadhesh Narayan (2019). „Use of permutations and combinations in India”. Ur.: 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. str. 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. Nedostaje ili je prazan parametar |title= (pomoć), 1992, MR 1189487. See p. 363.
^ Jadhav, Dipak (avgust 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  . CS1 održavanje: Format datuma (veza). See discussion of dating on p. 211.
^ Biggs, Norman L. (maj 1979). „The roots of combinatorics”. Historia Mathematica. 6 (2): 109—136. MR 0530622. doi:10.1016/0315-0860(79)90074-0  . CS1 održavanje: Format datuma (veza)
^ ^a ^b Katz, Victor J. (jun 1994). „Ethnomathematics in the classroom”. For the Learning of Mathematics. 14 (2): 26—30. JSTOR 40248112. CS1 održavanje: Format datuma (veza)
^ 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 (na jeziku: francuski). 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”. Ur.: Wilson, Robin; Watkins, John J. Combinatorics: Ancient & Modern. Oxford University Press. str. 109–121. ISBN 978-0-19-965659-2. See p. 111.
^ Hunt, Katherine (maj 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. CS1 održavanje: Format datuma (veza)
^ Stedman, Fabian (1677). Campanalogia. London. str. 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”. Ur.: Wilson, Robin; Watkins, John J. Combinatorics: Ancient & Modern. Oxford University Press. str. 123–145. ISBN 978-0-19-965659-2. See p. 126.
^ Knobloch 2013, str. 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. str. 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. str. 263—278. See in particular p. 263.
^ ^a ^b Cajori, Florian (1929). „448–449. Factorial " $n$ "”. A History of Mathematical Notations, Volume II: Notations Mainly in Higher Mathematics. The Open Court Publishing Company. str. 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 (na jeziku: francuski). Strasbourg: L'imprimerie de Levrault, frères. str. 364—365.

Literatura uredi

Bostock, Linda; Chandler, Suzanne; Rourke, C. (1. 11. 2014), Further Pure Mathematics (na jeziku: engleski), 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 izd.), 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 (na jeziku: French), Paris (1968): Centre National de la Recherche Scientifiques
Ramanujan, Srinivasa (1988), The Lost Notebook and Other Unpublished Papers, Springer Berlin, str. 339, ISBN 978-3-540-18726-4

Spoljašnje veze uredi

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

[FOOTNOTEGrahamKnuthPatashnik1988111-1] Graham, Knuth & Patashnik 1988, str. 111.

[datta-singh-2] Datta, Bibhutibhusan; Singh, Awadhesh Narayan (2019). „Use of permutations and combinations in India”. Ur.: 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. str. 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. Nedostaje ili je prazan parametar |title= (pomoć), 1992, MR 1189487. See p. 363.

[3] Jadhav, Dipak (avgust 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  . CS1 održavanje: Format datuma (veza). See discussion of dating on p. 211.

[4] Biggs, Norman L. (maj 1979). „The roots of combinatorics”. Historia Mathematica. 6 (2): 109—136. MR 0530622. doi:10.1016/0315-0860(79)90074-0  . CS1 održavanje: Format datuma (veza)

[katz-5] Katz, Victor J. (jun 1994). „Ethnomathematics in the classroom”. For the Learning of Mathematics. 14 (2): 26—30. JSTOR 40248112. CS1 održavanje: Format datuma (veza)

[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 (na jeziku: francuski). 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”. Ur.: Wilson, Robin; Watkins, John J. Combinatorics: Ancient & Modern. Oxford University Press. str. 109–121. ISBN 978-0-19-965659-2. See p. 111.

[10] Hunt, Katherine (maj 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. CS1 održavanje: Format datuma (veza)

[11] Stedman, Fabian (1677). Campanalogia. London. str. 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”. Ur.: Wilson, Robin; Watkins, John J. Combinatorics: Ancient & Modern. Oxford University Press. str. 123–145. ISBN 978-0-19-965659-2. See p. 126.

[FOOTNOTEKnobloch2013130–133-13] Knobloch 2013, str. 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. str. 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. str. 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. str. 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 (na jeziku: francuski). Strasbourg: L'imprimerie de Levrault, frères. str. 364—365.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]