Historie kombinatoriky

Historie kombinatoriky poukazuje na vývoj kombinatoriky , odvětví konečné matematiky , které především zkoumá různé způsoby, jak vybrat daný počet m prvků z dané konečné množiny : umístění , kombinace , permutace , stejně jako výčet a související problémy. Počínaje analýzou hádanek a hazardních her se kombinatorika ukázala jako mimořádně užitečná pro řešení praktických problémů téměř ve všech odvětvích matematiky. Kromě toho se kombinatorické metody ukázaly jako užitečné ve statistice , genetice , lingvistice a mnoha dalších vědách.

Starověké období

Kombinatorické motivy můžeme vidět v symbolice čínské „Knihy proměn“ (5. století př. n. l.). Podle jejích autorů je vše na světě kombinováno z různých kombinací mužských a ženských principů a také osmi živlů: země, hory, voda, vítr, bouřka, oheň, mraky a nebe [1] . Historici také zaznamenali kombinatorické problémy v příručkách pro hraní Go a dalších her. Velký zájem matematiků v mnoha zemích od starověku neustále probouzel magické čtverce .

Klasický úkol kombinatoriky: „kolik způsobů je možné extrahovat m prvků z N “ je zmíněn v sútrách starověké Indie (počínaje kolem 4. století př. n. l.) [2] . Indičtí matematici byli zřejmě první, kdo objevil binomické koeficienty a jejich souvislost s Newtonovým binomem [2] . Ve II století před naším letopočtem. E. Indové věděli, že součet všech binomických koeficientů stupně n je .

Staří Řekové také uvažovali o samostatných kombinatorických problémech, ačkoli jejich systematická prezentace těchto problémů, pokud existovala, se k nám nedostala. Chrysippus ( III. století př. n. l. ) a Hipparchos ( II. století př. n. l. ) vypočítali, kolik důsledků lze získat z 10 axiomů ; metoda výpočtu je nám neznámá, ale Chrysippus dostal více než milion a Hipparchos - více než 100 000 [3] . Aristoteles při prezentaci své logiky neomylně vyjmenoval všechny možné typy tříčlenných sylogismů . Aristoxenus zvažoval různé střídání dlouhých a krátkých slabik v metrech . [3] Pythagorejci pravděpodobně používali při konstrukci své teorie čísel a numerologie některá kombinatorická pravidla ( dokonalá čísla , obrazná čísla , pythagorejské trojice atd.).

Středověk

Ve 12. století indický matematik Bhaskara ve svém hlavním díle Lilavati podrobně studoval problémy související s permutacemi a kombinacemi, včetně permutací s opakováním.

V západní Evropě učinili dva židovští badatelé, Abraham ibn Ezra ( XII. století ) a Levi ben Gershom (aka Gersonides , XIV. století ) řadu hlubokých objevů na poli kombinatoriky . Ibn Ezra spočítal počet umístění s permutacemi v samohláskách jména boha [4] a objevil symetrii binomických koeficientů a Gersonides dal explicitní vzorce pro jejich výpočet a aplikaci v problémech s výpočtem počtu umístění a kombinací .

Několik kombinatorických problémů je obsaženo v „ Knize počítadla “ ( Fibonacci , XIII. století ). Dal si například za úkol najít nejmenší počet závaží, který by stačil k navážení jakéhokoli produktu o hmotnosti od 1 do 40 liber.

Nový čas

Gerolamo Cardano napsal matematickou studii o hře v kostky , publikovanou posmrtně. Teorií této hry se zabývali také Tartaglia a Galileo . Historie vznikající teorie pravděpodobnosti zahrnovala korespondenci zaníceného hráče Chevaliera de Méraye s Pierrem Fermatem a Blaise Pascalem , kde bylo vzneseno několik jemných kombinatorických otázek. Kromě hazardních her se v kryptografii používaly (a nadále používají) kombinatorické metody  , a to jak k vývoji šifer, tak k jejich prolamování.

Blaise Pascal udělal spoustu práce na binomických koeficientech a objevil jednoduchý způsob, jak je vypočítat: " Pascalův trojúhelník ". Přestože tuto metodu znali již na východě (asi od 10. století), Pascal na rozdíl od svých předchůdců vlastnosti tohoto trojúhelníku striktně uváděl a dokazoval. Spolu s Leibnizem je považován za zakladatele moderní kombinatoriky. Samotný termín „kombinatorika“ vytvořil Leibniz, který v roce 1666 (tehdy mu bylo 20 let) vydal knihu „Rozpravy o kombinatorickém umění“. Pravda, Leibniz chápal termín "kombinatorika" příliš široce, včetně celé konečné matematiky a dokonce i logiky [5] . Leibnizův žák Jacob Bernoulli , jeden ze zakladatelů teorie pravděpodobnosti, představil ve své knize The Art of Assumptions ( 1713 ) mnoho informací o kombinatorice.

Ve stejném období se formovala terminologie nové vědy. Termín " kombinace " ( kombinace ) se poprvé vyskytuje v Pascalu ( 1653 , publikováno v roce 1665 ). Termín " permutace " ( permutace ) byl použit ve specifikované knize Jacoba Bernoulliho (ačkoli se s ním už dříve občas setkal). Bernoulli také používal termín “ uspořádání ” .

Po příchodu matematické analýzy byla nalezena úzká souvislost mezi kombinatorickými a řadou analytických problémů. Abraham de Moivre a James Stirling našli vzorce pro aproximaci faktoriálu . [6]

Konečně, kombinatorika jako nezávislé odvětví matematiky se zformovala v dílech Eulera . Podrobně se zabýval například těmito problémy:

• problém tahu rytíře ;
• problém sedmi můstků , který odstartoval teorii grafů ;
• stavba řecko-latinských čtverců ;
• zobecněné permutace .

Kromě permutací a kombinací Euler studoval oddíly , stejně jako kombinace a umístění s podmínkami.

Moderní vývoj

Na počátku 20. století se začala rozvíjet kombinatorická geometrie : byly dokázány Radonovy , Hellyho , Youngovy , Blaschkeovy věty a důsledně dokázána i izoperimetrická věta . Borsuk- Ulamova a Lyusternik-Shnirelmanova věta byla prokázána na průsečíku topologie, analýzy a kombinatoriky . Ve druhé čtvrtině 20. století vznikl Borsuk problém a Nelson-Erdős-Hadwiger problém . Ve čtyřicátých letech se zformovala Ramseyho teorie . Za otce moderní kombinatoriky je považován Pal Erdős , který do kombinatoriky zavedl pravděpodobnostní analýzu. Od druhé poloviny 20. století, kdy se objevily počítače , výrazně vzrostla pozornost konečné matematice a zejména kombinatorice . Nyní je to extrémně bohatá a rychle se rozvíjející oblast matematiky.

Viz také

• teorie grafů
• Herní teorie

Poznámky

1. ↑ Vilenkin N. Ya., 1975 , s. 7.
2. ↑ 1 2 Amulya Kumar Bag . Binomická věta ve starověké Indii. Archivováno 3. srpna 2021 na Wayback Machine Indian J. History Sci., 1:68-74, 1966.
3. ↑ 1 2 Vilenkin N. Ya., 1975 , str. 9.
4. ↑ Stručný komentář k Exodus 3:13.
5. ↑ Vilenkin N. Ya., 1975 , s. 19.
6. ↑ O'Connor, John; Edmund Robertson. Abraham de Moivre . Archiv MacTutor History of Mathematics (6. 2004). Datum přístupu: 31. května 2010. Archivováno z originálu 27. dubna 2012.  (neurčitý)

Literatura

• Vilenkin N. Ya. Populární kombinatorika . - M. : Nauka, 1975. - 208 s.
• Historie matematiky. Od starověku do počátku New Age // Historie matematiky / Editoval A.P. Juškevič , ve třech svazcích. - M .: Nauka, 1970. - T.I.
• Matematika 17. století // Historie matematiky / Editoval A.P. Juškevič , ve třech svazcích. - M. : Nauka, 1970. - T. II.
• Matematika 18. století // Historie matematiky / Editoval A.P. Juškevič , ve třech svazcích. - M .: Nauka, 1972. - T. III.
• Rybnikov K. A. Kombinatorická analýza. Historické eseje. - M .: Ed. Mekhmat Moskevské státní univerzity, 1996. - 124 s.
• Rybnikov K. A. Historie matematiky ve dvou svazcích. - M. : Nakladatelství Moskevské státní univerzity, 1960-1963.