Міністерство освіти і науки України
Рівненський державний міський колегіум
Науково-дослідницька робота:
„Історія розвитку комбінаторики та деякі її застосування”
Виконав
учень І курсу
групи „А”
Теличко Павло
Рівне-2004
Комбінаторика – важливий розділ математики, знання якого необхідно представникам різноманітних спеціальностей. З комбінаторними задачами доводиться мати справу фізикам, хімікам, біологам, лінгвістам, спеціалістам по кодам та ін. Комбінаторні методи лежать в основі рішення багатьох задач теорії ймовірностей та її застосувань.
Комбінаторика – гілка математики, що вивчає комбінації та перестановки предметів, - виникла в XVII ст. Довгий час здавалося, що комбінаторика лежить поза основної течії розвитку математики та її застосувань. Хід справ різко змінився після появи ЕВМ та пов’язаним з цим розквіту кінцевої математики. Зараз комбінаторні методи застосовуються в теорії випадкових процесів, статистиці, математичному програмуванні, обчислювальній математиці, плануванні експериментів і т.д. В математиці комбінаторика використовується при вивченні кінцевих геометрій, комбінаторної геометрії, представлень груп, неасоціативних алгебр і т.д.
Справи давнини ...
Кажуть, що дехто засумнівався в правах Ньютона на відкриття закону всесвітнього тяжіння, стверджуючи, що падіння яблук на землю спостерігалось з давніх давен. В цьому жарті є доля правди – до того, як та чи інша область знання формується в певну науку, вона спочатку проходить довготривалий період накопичення емпіричного матеріалу, потім розвивається у надрах іншої, більш загальної науки і тільки потім виділяється в самостійну гілку. А якщо їй пощастить, то з гілки вона перетвориться на великий ліс, що шумить.
Не є винятком і історія про загальні закони комбінування і утворення різних конфігурацій об’єктів, що отримала назву комбінаторики. З задачами, в яких приходиться вибирати ті чи інші предмети, розміщувати їх в певному порядку і відшуковувати серед різних розміщень найкращі, люди стикнулися ще в доісторичну епоху, обираючи найкращі розміщення мисливців під час полювання, воїнів під час битви, інструментів під час роботи. Певним чином розміщувалися прикраси на одязі, візерунки на кераміці. З ускладненням виробничих і суспільних відносин ширше приходилося користуватися загальними поняттями про порядок, ієрархію, групування. В тому ж напрямку діяв розвиток ремесел торгівлі.
Комбінаторні навички виявилися корисними і в години дозвілля. Не можна точно сказати, коли поряд із змаганнями по бігу, метанню диску, стрибках з’явились ігри, що потребували в першу чергу вміння розраховувати, складати плани і спростовувати плани противника. Про такі ігри англійський поет Уордсворд писав:
Не нужно вам владеть клинком,
Не ищем славы громкой.
Тот побеждает, кто знаком
С искусством мыслить тонким.
Серед предметів, покладених в піраміду, де 35 століть тому назад був похований єгипетський фараон Тутанхамон, знайшли розкреслену дощечку з трьома горизонталями і 10 вертикалями та фігурки для давньої гри „сенет”, про правила якої ми, можливо, ніколи не дізнаємось. Пізніше з’явились нарди, шашки й шахмати, а також їх різноманітні варіанти (китайські та японські шахмати, японські облавні шашки „го” і т.д.). в кожній з цих ігор доводилося розглядати різноманітні комбінації фігур, що мали здатність пересовуватись, та вигравав той, хто їх краще вивчив, знав переможні комбінації та вмів уникати програшів.
Звичайно, в цей період ще не було й здогаду про науку, що розглядає рішення комбінаторних задач, з кожною такою задачею доводилося справлятися по особливому.
Загадкова черепаха
Перша згадка про питання, близькі до комбінаторних, зустрічається в китайських рукописах, що відносяться до XII – XIIIст. до н.е. (точно датувати ці рукописи неможливо, тому що вони в 213 р. до н.е. імператор Цин Шихуан наказав спалити всі книги, тому до нас дійшли пізніше зроблені копії). В цих книгах писалося, що усе в світі являється поєднанням двох початків – чоловічого та жіночого, які автори позначали символами ------ та --- ---. В рукописи „Же-ким” („Книга перестановок”) показані різні з’єднання цих знаків по два і по три (рис. 1). Вісім малюнків з трьох рядів символів відображали землю, гори, воду, вітер, грозу, вогонь, хмари і небо (деякі малюнки мали інше значення). Сума перших 8 натуральних чисел (тобто число 36) втілювала в уяву давніх китайців весь світ.
| ------ | --- --- | ------ | --- --- | ------ | --- --- | ------ | --- --- |
| ------ | ------ | --- --- | --- --- | ------ | ------ | --- --- | --- --- |
| ------ | ------ | ------ | ------ | --- --- | --- --- | --- --- | --- --- |
| k 'ien (небо) | tui (хмари) | li (вогонь) | chon (гроза) | sun (вітер) | k 'an (вода) | kon (гори) | k 'un (земля) |
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| Пд. | Пд.Сх. | Сх. | Пн.Сх. | Пд.Зх. | Зх. | Пн.Зх. | Пн. |
(Рис. 1)
По мірі заглиблення знань знадобилось виразити і інші елементи, що входять до складу світу за допомогою тих самих знаків ------ та --- ---. Були складені 64 фігури, що складалися з п’яти рядів рисочок. Треба вважати, що автор рукопису „Же-ким” помітив подвоєння числа малюнків при додаванні одного ряду символів. Це можна розглядати як перший загальний результат комбінаторики.
У рукописі „Же-ким” є і більш складні малюнки. Як стверджує подане в ній додаток, імператор Ію, котрий жив приблизно 4000 років тому назад, побачив на березі річки священну черепаху, на панцирі якої був зображений малюнок з білих і чорних кружків (рис. 2). Якщо замінити кожну фігуру відповідним числом, з’являється така таблиця:
4 9 2
3 5 7
8 1 6
(Рис. 2)
При додаванні чисел в кожному рядку, стовпчику та по діагоналі отримаємо одне і те саме число 15. При тому містичному поясненні, яке надавали числам давні китайці, відкриті таблиці з такими магічними властивостями справило невиправні враження. Рис. 2 назвали „ло-шу”, і почали вважати його магічним символом і використовувати при закляттях. Тому зараз будь-яку квадратну таблицю чисел з однаковими сумами по кожному рядку, стовпчику та по діагоналі називають магічним квадратом.
Комбінаторика в Древній Греції
Говорити з повною впевненістю про рівень знань древніх греків в області комбінаторики дуже важко, оскільки до нас дійшли далеко не все з їх наукових досягнень. В 391 р. н.е. натовп монахів зруйнував центр язичної науки – олександрійський Музеум - і спалив більшу частину зберігаємої там бібліотеки, що налічувала багато тисяч томів. Рештки бібліотеки зруйнувались на протязі ще трьох століть, а в 638 р. н.е. вона остаточно була зруйнована під час захоплення Олександрії військами арабського халіфа Омара. Більшість наукових книг назавжди загинули, і ми можемо лише здогадуватися про їх зміст по коротким переказам натякам в рукописах, що збереглися.
По цим натякам можна все ж таки судити, що певні уявлення про комбінаторику у грецьких вчених були. Філософ Ксенократ, що жив в ІV ст.. до. н.е. підраховував кількість складів. В ІІІ ст.. до н.е. стоїк Хрисипп вважав, що кількість тверджень, отримуваних з 10 аксіом, перевищує мільйон. На думку Геппарха, із стверджуючих аксіом можна скласти 103 049 сполучень, а додавши до них заперечні, 310 952. ми не знаємо який саме зміст надавали ці філософи своїм ствердженням і як вони отримували свої результати – числа, що наводив Геппарх дуже точні, щоб вважати їх результатом грубої оцінки, і в той же час їх не можна пояснити. Напевно, у грецьких вчених були якісь, невідомі нам, правила комбінаторних розрахунків, які скоріше всього були невірними.
Конкретні комбінаторні задачі, що торкалися перерахунку невеликих груп предметів, греки розв’язували без помилок. Аристотель описав без пропусків всі види правильних тричленних силогізмів, а його учень Аристоксен з Тарента перерахував різноманітні комбінації довгих і коротких складів у віршових розмірах. Математик Папп (ІV ст. н.е.) роздивлявся число пар і трійок, які можна отримати з трьох елементів, не забороняючи їх повторення.
Велику увагу грецькі вчені приділяли питанням, граничним між комбінаторикою та теорією чисел. Ще в VІ ст. до н.е. в школі філософа-ідеаліста і математика Піфагора виникло твердження, що світом правлять числа, а речі лише відображення чисел (можливо, ці ідеї виникли у Піфагора під впливом вавилонської культури). Тому, щоб пізнати світ, пафігорейці почали вивчати властивості натуральних чисел. Їхні досліди про парні і непарні числа, ділення чисел, простих і складених числах поклали основу теорії чисел (в науці буває, що невірні похідні основи дають поштовх до корисних досліджень). Як і китайці, піфагорейці надавали особливе значення числу 36 – воно було для них не тільки сумою перших 4 парних і перших 4 непарних чисел, але й сумою перших трьох кубів: 36 = 13 + 23 + 33. Символом бездоганності для піфагорейці вважали бездоганні числа, що дорівнювали сумі своїх дільників, наприклад, 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, а символом дружби – дружні числа, кожне з яких дорівнює сумі дільників іншого числа (наприклад, 220 і 284). Пошук таких чисел потребував комбінаторної майстерності.
. . . .
. . . . . . .
. . . . . . . . .
. . . . . . . . . .
(Рис. 3)
В школі Піфагора була доведена знаменита теорема про сторони прямокутного трикутника. Це викликало інтерес до представлення чисел у вигляді суми двох квадратів, до квадратних чисел 1, 4, 9, 16 і т.д. Квадрати натуральних чисел відображались при цьому геометрично (рис. 3). Але піфагорейці розглядали і інші конфігурації крапок, такі, як зображені на рис. 4 і 5. Кожний трикутник на рис. 4 отримується з попереднього збільшенням довжини його сторони на 1. Підраховуючи кількість крапок у кожному трикутнику, отримуємо послідовність трикутних чисел 1, 3, 6, 10... Ці числа можна отримати, послідовно додаваючи натуральні числа: 1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4 і т.д. Так само шестикутники на рис. 5 призводять до послідовності шестикутних чисел 1, 6, 15 ... отриманій при послідовному додаванні арифметичної прогресії 1 + 5 + 9 + ...