Міністерство освіти і науки України
Рівненський державний міський колегіум
Науково-дослідницька робота:
„Історія розвитку комбінаторики та деякі її застосування”
Виконав
учень І курсу
групи „А”
Теличко Павло
Рівне-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 + ...
Рис. 4
В подальшому такі суми вдалося виразити за допомогою біноміальних коефіцієнтів С
k
n
, що відіграють важливу роль в комбінаториці.
Перехід від площини до простору дав можливість будувати ще більш складні числа. Наприклад з трикутників можна скласти піраміди. Підраховуючи кількість крапок в таких пірамідах, прийшли до пірамідальних чисел 1, 4, 10, 20, ..., що були сумами ряду 1 + 3 + 6 + 10 + ..., складеного з натуральних чисел. Проте подальше узагальнення потребували введення багатомірних просторів, що лежало за рамками можливостей давньогрецької математики.
Вчення про фігурні числа приваблювало до себе математиків на протязі багатьох століть. Ними багато займався французький вчений П’єр Ферма, що жив у XVІІ ст.. Він довів, наприклад, що будь-яке натуральне число є чи трикутне чи сума 2 чи 3 трикутних чисел, квадратне чи сума 2, 3, 4 чи 5 п’ятикутних і т.д. Як і багато інших отриманих ним результатів, він лише сформулював це твердження в листі до Блеза Паска ля (юрист по основній професії, Ферма займався математикою лише у години дозвілля). Часткові випадки цієї теореми довели Ейлер та Лагранж, а взагалі доведення було дано в 1815 р. французьким математиком О. Коші.
Одночасно з комбінаторикою чисел грецькі вчені займались і окремими питаннями геометричної комбінаторики – правильними і напівправильними многогранниками, складанням фігур з 14 частин особливим методом розрізаного квадрата і т.д. Останньому питанню була присвячена робота Архімеда „Стомахіон”.
Рис.5
Містики, астрологи, кабалісти
З ІІ ст. до н.е. починається спочатку поступовий, а потім все більш швидкий занепад науки в елліністичних країнах, що відображав загальну кризу рабовласницької общини. Багато тогочасних робіт були присвячені містичним тлумаченням чисел в дусі піфагорейців (наприклад, „Арифметична теологія” неопіфагорейця Никомаха, що жив у І – ІІ ст. до н.е.). великий розвиток отримали різноманітні числові вірування та тлумачення, пов’язані із заміною букв, що відповідали числам (греки позначали числа за допомогою букв – перші 9 букв алфавіту позначали числа від 1 до 9, наступні за ними – від 10 до 90, а останні 9 букв – від 100 до 900). Були „вчені”, яких називали кабалістами, які піддавали такому „аналізу” слова Біблії та інших священних книг і робили на основі своїх винаходів пророцтва про майбутнє світу.
У часи богословських спорів, що почалися після перемоги християнства, намагалися отримати з імен єретиків число 666 – адже по Апокаліпсису це було „тваринне число”, символ анти християнства. Такі спроби робились і пізніше – лютерани намагались вивести число 666 з імені римського папи, а католики – з імені Мартіна Лютера. У романі „Війна і мир” Л. М. Толстой описує, як П’єр Безухов намагався вивести це число з імені Наполеона Бонапарта. Такого роду досліди при всій своїй без результативності давали поштовх до майбутнього розвитку комбінаторики.
Наряду з кабалістами і містиками комбінаторикою в ці темні століття занепаду науки займались астрологи. Їх цікавило питання про рух планет і їх „вплив” на долі людей. Особливе значення надавали вони порядку планет – зустрічі планет одному знаку Зодіаку. Астролог Бен Езра у 1140 році розрахував кількість суміщень семи планет по дві, по три і т. д. Він знав, що число суміщень планет по дві дорівнює числу їх суміщень по п’ять, а число суміщень по три дорівнює дорівнює числу суміщень по чотири. Якщо позначити ці твердження сучасними символами, то отримаємо рівності С2
7
= С5
7
і С3
7
= С4
7
(через Сk
n
визначають число суміщень з nрізних предметів поk).
В остаточному вигляді формулу для числа суміщень отримав математик Леві бен Гершон (початок XIV ст.), довівши, що
Ck
n
=
n
(
n
- 1)… (
n
–
k
+ 1)
(1)
Проте його робота, написана на мало досяжному для багатьох вчених древньоєврейській мові, залишилась майже непоміченою – знову формулу (1) вивів на початку XVII ст. французький математик П. Ерігон.
Комбінаторика і схоластики
Своєрідною комбінаторикою займались і логіки. Продовжуючи досліди Аристотеля, вони класифікували поняття і логічні судження. В ІІІ ст. н.е. сирієць Порфирій для класифікації понять склав особливу схему, яка отримала назву „дерево Порфирія”. На вершині цього дерева містилось найширше за об’ємом поняття, вузли дерева відповідали різним роз’ясненням поняття, а лінії між вузлами відображали підлеглість понять одне одному. Схожі дерева зараз широко використовуються додатках комбінаторики до різноманітних питань.
Один із засновників медицини, Гален, в ІІ ст. н.е. займався класифікацією силогізмів, що складалися з чотирьох частин. Римський філософ і математик Боецій (V – VІ ст. н.е.) знайшов число пар, які можна скласти з п’яти категорій модальності, беручи їх як в затверджу вальній, так і в заперечній формі і ставлячи або на місце умови, або на місце слідства. Він також класифікував умовні силогізми.
Велику увагу класифікації видів суджень приділяла схоластична наука (взагалі в схоластиці химерно переплітались богуславські „вишуканості” з вивченням проблем, прилягаючих до комбінаторики, математичній логіці, теорії множин та іншим сучасним областям математики – великими затоками схоластичних дослідів були засновники теорії множин Бернард Больцано і Георг Кантор). Сперечаючись про взаємовідносини членів пресвятої трійці, про спів підлеглість ангелів, архангелів, херувимів та серафимів, схоласти були вимушені розглядати різні відношення порядку та ієрархії – достатньо згадати найскладнішу архітектуру стародавнього світу, яку описав Данте у „Божественній комедії” з її колами пекла і різними областями раю.
Схоласт Раймонд Люллій створив у ХІІІ ст. машину, що складалася з декількох кіл, на які було нанесено основні предикати, суб’єкти, атрибути та інші поняття схоластичної логіки. Повертаючи ці кола, він отримував різні суміщення понять і сподівався отримати з їх допомогою істину.
Комбінаторика в країнах Сходу
В VIII ст. н.е. почався розквіт арабської науки. Араби переклали багато творів грецьких учених, вивчили їх, а потім просунулись вперед по областях, мало звертавших увагу греків, - в науці про рішення рівнянь (саме слово „алгебра” – арабського походження), теорії та практиці обчислень та ін. Вирішуючи питання про знаходження коренів з будь-якого степеня, арабські алгебраїсти вивели формулу для степені суми двох чисел, яка відома під невірною історичною назвою „біном Ньютона”. Напевно цю формулу знав поет і математик Омар Хайям (ХІ – ХІІ ст. н.е.). у будь-якому випадку вже і ХІІІ ст. таку формулу друкує в своїх творах Насир ад-Дин ат-Туси, а в XV ст. вона була ретельно досліджена Гияседдином ал-Каші.
Судячи по деяких європейських джерелах, східним до арабських оригіналів, для пошуків коефіцієнтів цієї формули брали число 10001 и зводили його до 2-го, 3-го, ......, 9-го степеня. Виходила таблиця в якій жирним шрифтом були виділені коефіцієнти бінома Ньютона.
1
0009
0036
0084
0126
0126
0084
0036
0009
0001
1
0008
0028
0056
0070
0056
0028
0008
0001
1
0007
0021
0035
0035
0021
0007
0001
1
0006
0015
0020
0015
0006
0001
1
0005
0010
0010
0005
0001
1
0004
0006
0004
0001
1
0003
0003
0001
1
0002
0001
1
0001
Якщо опустити в цій таблиці зайві нулі, то вийде трикутна таблиця біноміальних коефіцієнтів. Арабські вчені знали основну властивість цієї таблиці, що виражається формулою
Ck
n
= Ck
n–1
+ Ck-1
n-1
Одночасно з арабами вирахуванням біноміальних коефіцієнтів займались китайські математики. Вони склали до ХІІІ ст. н.е. таблицю таких чисел до n = 8, наведену в книзі алгебраїста Чжу Ши-дзе „Ямшове дзеркало”. Присутні здогади, що І Сінь в VIII ст. н.е. вирахував кількість різних розміщень фігур у грі, що нагадувала шахи.
Цікавились суміщеннями і в Індії. Ще в ІІ ст. до н.е. індійці знали числа С
k
n
і той факт, що сума C
0
n
+
C
1
n
+ … +
Cn
n
дорівнювала 2n
. А в ХІІ ст. індійський математик Бхаскара написав книгу „Лілаваті”, в якій серед інших питань математики вивчає і проблеми комбінаторики. Він пише про застосування перестановок до підрахунку варіацій у віршоскладанні, різних розміщень в архітектурі та ін. Він також дає правила для пошуку числа перестановок та суміщень декількох предметів, при чому розглядає і випадок, коли в цих перестановках є елементи, що повторюються.
Liber
Abaci
На початку ХІІ ст. Східна Європа почала пробуджуватися після багатовікової духовної сплячки. Розвиток торгівлі зі Сходом призвів до проникнення у Європу арабської науки. Найбільш сміливі та охочі європейці пробиралися в Іспанію, що знаходилася під владою арабів, та знайомились там не тільки з твореннями грецьких вчених, але й з досягненнями арабської та індійської наукової думки – алгеброю та десятинною системою числення.
В арабських навчальних закладах отримав освіту і Леонардо – син видатного купця, що торгував у Алжирі. У своїй книзі „LiberAbaci”, що вийшла у 1202 р., Леонардо, котрий отримав прізвисько Фібоначчі, привів в систему арифметику арабів, деякі відомості з геометрії Евкліда і додав до них результати своїх досліджень. Праця Фебоначчі містила і нові комбінаторні задачі, наприклад про пошук найменшої кількості гир, за допомогою яких можна отримати будь-яку цілу вагу від 1 до 40 фунтів. Розглядав Леонардо і пошук цілих рішень рівнянь. В подальшому аналогічні задачі призвели до пошуку кількості натуральних рішень систем рівнянь і нерівностей, які можуть розглядатися як одна з глав комбінаторики.
Проте головною заслугою Леонардо перед комбінаторикою було те, що він сформулював і розв’язав задачу про кроликів. З часів грецьких математиків були відомі дві послідовності, кожний член яких отримувався за певних умов з попередніх – арифметична і геометрична прогресії. В задачі Леонардо з’явилась нова послідовність, члени якої були пов’язані один з одним відношенням un
=
un
-1
+ un
-2
. це була перша в історії науки формула, в якій наступний член виражався через два попередніх. Подібні формули отримали назву рекурентних (від лат. recurrere – повертатись). Метод рекурентних формул виявився одним із найпотужніших для рішення комбінаторних задач.
Гра в кості
Значний поштовх до розвитку комбінаторики дали азартні ігри, які існували ще в глибоку давнину, але отримали особливе розповсюдження після хрестових походів. Найбільшу популярність отримала гра в кості – два чи три кубики з нанесеними на них очками кидали на стіл, і вигравав той, хто отримував більшу кількість очок. В кості грали повсюди, виграючи та програючи в них золото, замки, дорогоцінні камені та коней. Атос – один з героїв „Трьох мушкетерів” – зумів грати навіть на свого слугу Гримо. Постанови церковних соборів містили досить суворі заборони цієї гри. Мусульманські вчені писали про гру в нарди, в якій пересування шашок визначалося кидком костей: „Як же ганебно для мудрого стати рабом двох камінців до такої міри, що він віддає свої досягнення та свою землю в їх руки, і вони наказують йому і забороняють, а він підкоряється їх керівництву більше, ніж підкоряється верблюд, коли його веде маленька дівчинка”.
Але ніщо не допомагало, і вбудь-якому місті можна було спостерігати картину, описану в „Божественній комедії” Данте:
Когда кончается игра в три кости,
То проигравший снова их берет,
И мечет их один в унылой злости;
Другого провожает весь народ…
Не дивлячись на давнину іг
Таким чином, виявилось, що потрібно враховувати не тільки поєднання очок, але і їх порядок.
Більш складними виявились відповідні досліди для трьох костей. Тут при врахуванні порядку костей виявляється 216 різних комбінацій, а без порядку – 56.
Цими питаннями займались такі видатні італьянські математики XVI ст., як Д. Кардано, Н. Тарталья та ін. Більш повніше дослідив його в XVII ст. Галілео Галілей, але його рукопис залишався неопублікованим до 1718 р.
Гравець і вчення
Одним з найазартніших гравців в кості у XVII ст. був шевальє де Маре, котрий без перестану знаходив нові види змагань. Наприклад, він запропонував, що буде кидати чотири кості і буде брати виграш лише у випадку, коли хоча б одна з них відкриється на шести. Проте скоро його партнери відмовились від такої гри – шевальє частіше вигравав, ніж програвав. Тоді де Маре придумав інший варіант – він кидав декілька раз пару костей і забирав виграш в тому випадку, якщо хоча б раз випадали дві шестірки. Треба було лише визначити, скільки потрібно зробити кидків, щоб гра була йому така ж вигідна, як і перша. Шевальє вирішив, що треба кидати 24 рази. Адже при чотирьох кидках однієї кості шестірка випадала більш ніж у половині випадків, а так як друга кость дає шість варіантів випадання, то й треба помножити 4 на 6.
Роздуми здавалися незаперечними, але досвід не підтвердив надій де Маре – тепер він став частіше програвати, ніж вигравати. В повному нерозумінні він звернувся до двох великих математиків Франції XVII ст. –
Блезу Паскалю та П’єру Ферма. Розбираючись в цій та інших задачах, поставлених перед ними де Маре, вони сформулювали і довели перші теореми комбінаторики та теорії ймовірностей.
Нова гілка математика
Роботи Паскаля і Ферма дали поштовх для народження двох нових гілок математичної науки – комбінаторики і теорії ймовірностей. Якщо до них комбінаторні проблеми лише торкалися в загальних роботах по астрології, логіці і математиці, а більшою частиною відносились до області математичних розваг, то вже у 1666 р. Готтфрід Вільгельм Лейбніц публікує „Дисертацію про комбінаторне мистецтво”, в котрій вперше з’являється сам термін „комбінаторика”. Титульний лист книги двадцятирічного автора, котрий мав учений степінь бакалавра... юриспруденції, обіцяв додатки до всіх областей науки і новий підхід до логіки винаходження, а тематика введення могла суперничати по своїй широті з програмою, яку, як свідчить Льюіс Керрол, намітив Плотникдля бесід з устрицями. Проте, про королів та капусту там не йшлося, але проголошувалось відношення теорії до замків, органів, силогізмів, змішанню кольорів та віршобудуванні, логіки, геометрії, воєнного мистецтва, юриспруденції, граматики, медицини та теології.
Але про цю дисертацію можна сказати те ж, що Еммануїл Кант сказав про роботи Лейбніца: „Знаменитий Лейбніц володів багатьма дійсними знаннями, котрими він збагатив науки, але ще більш грандіозними були його замисли, виконання котрих весь світ з захопленням чекав від нього”. Дисертація Лейбніца мала стати лише початком великої роботи, про яку він часто згадував у своїх листах і друкованих працях та для котрої робив у своїх записних книжках спеціальні помітки. З них видно, що Лейбніц планував для комбінаторики все нові й нові додатки: до кодування і декодування, ігор, статистики, теорії спостережень. Він вважав, що комбінаторика повинна займатись однаковим і різним, схожим і несхожим, абсолютним і відносним розміщенням, в той час як звичайна математика займається великим і малим, одниною і множиною, цілим і частиною. Іншими словами, під поняттям комбінаторики Лейбніц розумів приблизно те, що ми тепер називаємо дискретною математикою. До області комбінаторики Лейбніц відносив і „універсальну характеристику” – математику суджень, тобто прообраз теперішньої математичної логіки.
Проекти Лейбніца здавалися нездійсненними тогочасним математикам, але тепер, після створення ЕВМ, багато планів Лейбніца почали втілюватися у життя, а дискретна математика виросла у своєму значенні настільки, що почала суперничати з класичним математичним аналізом.
В 1713 р. була опублікована книга „Мистецтво припущень” Якоба Бернуллі, в якій вказувались формули для числа розміщень з n елементів по k, виводились вираження для степеневих сум та ін. Чудові досягнення в області комбінаторики належать одному з найбільших математиків XVIII ст., Леонарду Ейлеру, швейцарцю, що прожив майже все життя в Росії, де він був членом Петербурзької академії наук. Основна частина наукової роботи Ейлера присвячена математичному аналізу, в якому він проклав нові шляхи, створив цілий ряд нових областей і закінчив досліди інших областей. Але у Ейлера вистачало часу думати і про задачі, які, здавалося б, не заслуговували його уваги, - про те, чи можна обійти мости в Кенігсберзі (нині Калінінграді) так, щоб не побувати двічі на одному і тому самому мості, чи можна поставити 36 офіцерів з 6 різних полків так, щоб у кожній шерензі і у кожній колоні було по одному офіцеру кожного військового звання з полку, скількома способами можна розбити число на частини і т.д. Але, дивна справа, робота про мости виявилась так званим зерном, з якого потім виросли топологія і теорія графів, задача про офіцерів виявилась зараз пов’язаною з плануванням експериментів, а методи, що використовувалися при розв’язуванні задачі про розбиття чисел, після довгого та важкого шляху розвитку перетворилась в науку про інтегральні перетворення, що використовується для розв’язання рівнянь математичної фізики.
Після робіт Паскаля і Ферма, Лейбніца і Ейлера можна було вже говорити про комбінаторику, як про окрему, самостійну гілку математики, тісно пов’язану з іншими областями науки, такими, як теорія ймовірностей., вчення про ряди та ін. В кінці XVIII ст. німецький учений Гінденбург та його учні зробили спробу побудувати загальну теорію комбінаторного аналізу. Проте вона не отримала успіху – в той час ще не було накопичено достатньої кількості важливих і цікавих задач, які могли б дати необхідний фундамент для такої теорії.
В ХІХ ст. в ході досліджень по комбінаториці стали помічатися зв’язки цієї теорії з визначеннями кінцевими геометріями, групами, математичної логіки і т.д.
Шифри та анаграми
Не тільки азартні ігри спонукали математиків до комбінаторних роздумів. Ще з давніх давен дипломати, що прагнули до таємних переписів, винаходили все більш складні шифри, а секретні служби інших держав намагалися ці шифри розгадати. Одним з найпростіших шифрів була „тарабарська грамота”, в якій літери замінювались іншими за певними правилами. Проте такі шифри легко розгадувалися за характерними поєднаннями літер. Тому почали застосовувати шифри, які були основані на комбінаторних методах, наприклад, на різних перестановках літер, заміна літер з використанням ключових слів та ін.
Для кодування та розшифровки залучались математики. Ще в кінці XVI ст. розшифровкою переписів між ворогами французького короля Генріха ІІІ та іспанцями займався один із творців сучасної алгебри Франсуа Вієт. А в Англії XVIIст. монархічні заколотники дивувались швидкості, з якою Кромвель проникав у їх замисли. Монархісти вважали шифри, якими вони користувались при переписі, нерозшифрованими, і вважали, що ключі до них були видані кимсь з учасників заколоту. І лише після падіння республіки та царювання Карла ІІ вони дізналися, що всі їх шифри розгадував один з найкращих англійських математиків того часу, професор Оксфордського університету Уолліс, котрий володів винятковими комбінаторними можливостями. Він назвав себе засновником нової науки „криптографії”.
Шифрами користувались не тільки дипломати і заколотники, але й самі вчені. До XVII ст. майже не існувало наукових журналів. Вчені дізнавалися про досягнення своїх колег з книг або приватних листів. Це створювало великі труднощі при опублікуванні нових результатів – адже друкування книг займало роки, а написати про свої відкриття приватним листом було ризиковано – хтось міг присвоїти досягнення, і потім довелося б доводити, що це він не сам вигадав, а дізнався з отриманого листа. Тому часто виникали суперечки на тему переваг. Ще в кінці XVII ст. йшли довгі суперечки на тему пріоритетів між Ньютоном та Лейбніцом (про те, хто першим відкрив диференціальне та інтегральне числення), Ньютоном та Гуком (хто першим сформулював закон всесвітнього тяжіння) та ін.
А давнину Архімеду доводилося застосовувати хитрощі. Коли деякі олександрійські вчені присвоювали собі його результати, про які дізнавались з отриманих від нього листів, він писав їм ще одного листа. Лист складався з формул для обчислень об’ємів та площ різних фігур і тіл. Олександрійці знову казали, що ці формули вони давно знають і нічого нового Архімед їм не повідомив. Але тут виявлялось, що усі ці формули були невірними!
Для того, щоб забезпечити пріоритет і не допустити передчасного розголосу отриманих результатів, вчені в короткій формі формулювали суть відкриття, а потім переставляли в ній літери і відправляли листа з переставленими літерами своїм колегам. Такі тексти з переставленими літерами називаються анаграми.
Наприклад слово „Москва” та „смоква” – анаграми. Коли ж друкувалась книга з детальним викладенням результатів, в ній давалася і розшифровка анаграми.
Проте не завжди анаграми дозволяли зберегти все у таємниці. Коли Гюйгенс відкрив перший супутник Сатурна та визначив його порядок обертання навколо планети, він виклав своє відкриття в анаграмі і відправив її своїм колегам. Проте вже згадуваний вище Уолліс, отримав цю анаграму, розгадав її, після чого склав свою анаграму та відправив її Гюйгенсу. Коли вчені обмінювалися розгадками анаграми, то вийшло так, немов Уолліс ще до Гюйгенса зробив те ж саме відкриття. Потім Уолліс зізнався, що пожартував із Гейгенсом, щоб довести безкорисність анаграм у справі таємності. Проте, хоча Гейгенс і сам був великим любителем і знавцем комбінаторики, він не оцінив жарту і розізлився.
Ієрогліфи та клинопис
Навички в розгадці складних шифрів допомогли ученим, коли археологи почали відкопувати камені та черепи з таємними знаками – письменністю, що замовкла декілька тисячоліть тому. Одним з найкращих успіхів у розшифровці було читання французьким філологом Жаном Франсуа Шампольним ієрогліфів, якими писали єгиптяни ще до того, як виникла наука у древніх греків.
У Шампольна були попередники – шведський археолог Д. Окерблад та англійський фізик т. Юнг, які розшифровували єгипетські тексти за допомогою комбінаторного аналізу. В їхніх руках були „білінгви” – написи, які були зроблені одночасно на єгипетській та грецькій мовах. Порівнюючи обидва тексти та помічаючи повторність груп знаків, Окерблад упізнав деякі знаки так званого демотичного письма – пізньої стадії розвитку єгипетського письма. А творець хвильової оптики Томас Юнг полюбляв відпочити від роздумів на фізичні теми і займався то каліграфією, то складанням алфавітів іноземних мов, то... танцями на слабо натягнутому канаті, - на думку Юнга все, що могла зробити одна людина, могла повторити інша. У 1814 р. він взяв з собою на канікули древньоєгипетський папірус і спробував прочитати його. Не маючи потрібної філологічної підготовки, шляхом комбінаторного він отримав цікаві результати, а потім спробував прочитати ієрогліфи. Деяких успіхів він досяг і тут, але далося в знаки недостатнє знання мов – він шукав ієрогліфи не тільки для приголосних, але й для голосних літер, а в єгипетській мові голосні опускаються. Лише Шампольну, котрий поєднав незаурядний комбінаторний дар з глибокими знаннями філології, вдалося прочитати ієрогліфи.
Складність задачі, що постала перед Шампольном, доповнювалась незнанням мови написів та змісту знаків. Проте, виділивши знаки, які на грецькій мові означали імена царів, Шампольна помітив, що деякі знаки в іменах фараонів Птоломея та Клеопатри співпадають. Так були знайдені звучання ієрогліфів, що означали літери „л” та „п” (до цього місця дійшов і Юнг). А потім Шампольн прочитав імена римських імператорів Тиберія та Трояна, давніх фараонів Рамсеса та Тутмеса – ключ до читання ієрогліфів, втрачений декілька тисячоліть тому, був знову отриманий.
Це було торжеством комбінаторного методу у читанні забутих писемностей, заснованого на спостереженні за текстом, на співставленні повторюванні комбінацій слів та граматичних форм в поєднанні з уявою.
Ще тісніше пов’язана з комбінаторикою розшифровка клинописів. Історикам вдалося вияснити, що ці надписи було зроблено в епоху Ахеменідів, що правили в Ірані два з половиною тисячоліття тому назад. Були зроблені і припущення про мову надписів. А потім комбінаторний аналіз тексту виявив часте повторення певної групи знаків з семи знаків. Інколи ця група повторювалася двічі підряд з невеликими змінами. І датський вчений Мюнтер вирішив, що ця група означає слово „цар”, а повторення двічі – „цар царів”. Але дізнатись про звучання цих звуків Мюнтер не зумів. Це зробив молодий німецький учитель Гротефенд. Любитель різноманітних головоломок та таємного письма, одного дня він посперечався, що розшифрує клинопис. Аналізуючи поєднання звуків біля титулів „цар” та „цар царів”, Гротефенд побачив, що деякі з них зустрічаються у різних позиціях. Звідси було зроблено висновок, що це ім’я царя, яке в іншій позиції означає „син царя такого-то”. Це дозволило упізнати групу символів і для слова „син”. В одному місці після цієї групи знаків не стояло слово „царя”. Значить, вирішив Гротефенд, цар, про якого тут йдеться, не був сином царя – це був сам засновник династії Дарій, син Гістаспа. А так як Дарій був батьком Ксеркса, то у Гротефенда в руках були звукові значення для знаків, що входили в імена „Гістасп”, „Дарій”, „Ксеркс” – початок розшифровки клинопису розпочався.
Комбінаторика дозволила прочитати і крито-мікенське лінійне письмо. Перші надійні основи розшифровки цієї писемності заклала Аліса Д. Кобер, яка захистила у 1932 р. докторську дисертацію по математиці у Колумбійському університеті. Поряд з дослідженнями по чистій математиці вона багато сил приділяла розшифровці давніх писемностей. Вивчивши знаки критського письма, Аліса встановила, що це письмо складається зі складів. Далі вона помітила, що в текстах, котрі вона досліджує деякі слова зустрічаються у трьох різних формах, які відрізняються одна від одної декількома останніми знаками. А далі вона почала складати „лінгвістичні рівняння” для складів, що дозволили їй знайти склади з однаковими приголосними, але з різними голосними, і однаковими голосними, і різними приголосними. В результаті Кобер отримала координатну сітку, в якій замість осей координат стояли номери голосних і приголосних літер. У цієї сітки був лише один недолік – ніхто не знав, які саме голосні та приголосні формують цю систему координат.
Лише через два роки після смерті дослідниці молодий англійський архітектор Майкл Вентріс, розширюючи її координатну сітку, спробував вгадати значення деяких голосних – число голосних менше числа приголосних, і розбір краще починати з них. Одна із спроб закінчилася вдало – текст заговорив на мові, досить нагадувавши грецьку. Але це не була класична грецька мова „Іліади” та „Одіссея”, а грецька мова більш ранньої епохи. Вентрису допоміг завершити розшифровку видатний знавець ранньої грецької мови Чедвік. Використовуючи імена царів та списки географічних назв, дослідники розшифровували один склад за іншим. А потім почалася швидка розшифровка – три десятки знаків отримали своє значення. Це був повний тріумф комбінаторного підходу, що був заснований наступним методом, сформульованим Вентрисом: „при спробі дешифрувати документи на незнайомій мові, що були написані невідомим листом, перший крок складається в отриманні тих фактів, які самі даються в руки при розгляді наявних документів. Суть другого кроку у тому, що дослідник шляхом ретельного аналізу і логічної дедукції виявляє, які висновки можна зробити з цих основних фактів”.
При розшифровці буквеної писемності виявляється дуже важливим розділення знаків, що означають голосні літери, від знаків, що означають приголосні. І тут на допомогу приходить комбінаторика. Радянський учений В. В. Шеворошкін заснував метод, що був оснований на комбінаторному порівнянні частоти різних поєднань пар знаків. Добре відомо, що у мовах голосні та приголосні літери певним образом чергуються одна з одною. Це дозволяє розділити усі знаки на дві групи так, що, як правило, знаки однієї групи межуються в тексті зі знаками іншої групи. Тоді знаки, що входять в меншу групу, будуть означати голосні, а ті що входять в іншу групу, - приголосні. Цей метод дав досліднику ключ до читання карійських написів.
Комбінаторика в біології
Складність будови біологічних систем, їх строга ієрархічність, взаємо поєднання окремих процесів в цілому організмі роблять біологію підходящим полем для прикладення комбінаторних методів. Радянський біолог А. А. Любищєв припускав навіть, що схожість рослин та морозних візерунків на вікнах не випадково – в обох випадках проявляються певні закони комбінування частин в одне ціле.
Коли біологи почали вивчати передачу генетичної інформації у бактерій, то помітили, що в процесі цієї передачі хромосоми переходять від однієї бактерії до другої не цілком. Вони надіялися, вивчаючи частини, що перейшли, визначити порядок розміщення генів у хромосомі. Тут їх чекала невдача – карти хромосом, складені в різних лабораторіях, були несхожими одна на одну. Проте детально порівнявши отримані карти, французькі учені Жакоб та Вальмон помітили їх комбінаторну схожість. Виявилося, що всі ці карти були частинами одного кільця – хромосоми бактерій виявлялись згорнутими у кільця, які перед переходом у іншу бактерію розриваються, після чого до одного кінця прикріплюється фактор, що перетягує хромосому з однієї бактерії до іншої. А так як розірватися кільце могло у будь-якому місці, а фактор міг прикріпитися до будь-якого кінця, то й виникало багато різних карт, котрі заплутували картину.
Однією з найбільш складних загадок в біології ХХ ст. була будова „ниток життя” – молекул білка і нуклеїнових кислот. Виявилося, що молекули білка – це об’єднання декількох довгих ланцюгів, що складалися з 20 амінокислот.
Щоб розгадати структуру хоча б одного ланцюга, його відділяють від інших і піддають дії ферментів, що розривають ланцюг на строго визначені частини. Ці частини вже можна піддати хімічному аналізу, та дізнатись про порядок розташування амінокислот. Далі виникає питання про збірку всього ланцюга з виключених частин. Для цього беруть ті ж молекули білка і піддають їх дії інших ферментів. Тоді вони розпадаються на інші частини, будова яких також піддається вивченню. Шляхом вивчення перекриттів окремих частин вдається вияснити порядок розташування амінокислот у всьому ланцюзі. Звичайно, такий комбінаторний аналіз потребує залучення потужної техніки. Поєднуючи комбінаторні розгляди з вивченням рентгенівських знімків, вченим вдалося розгадати будову багатьох білків, в тому числі гемоглобіну, інсуліну та ін.
Найбільшим досягненням комбінаторного підходу до проявів життя можна вважати розшифровку будови дезоксирибонуклеїнової кислоти (ДНК), зроблену в Кембриджі Ф. Криком та Дж. Уотсоном у 1953 р.. було відомо, що ДНК грає важливу роль в наслідуванні властивостей організмів. Це залучало до її вивчення багатьох дослідників.
Хімічний пасьянс
Небагато знайдеться днів в історії науки, які можна порівняти по своєму значенню з 17 лютим 1869 р. у цей день з хаосу хімічних елементів, кожен з яких мав свої властивості, виникла таблиця – був відкритий періодичний закон. Це відкриття було зроблено Дмитром Івановичем Мендєлєєвим, професором Петербурзького університету. Готуючи курс лекцій по загальній хімії, він задумався над порядком, в якому потрібно було розповідати про елементи.
Ще до Мендєлєєва вчені помітили схожість хімічних властивостей деяких елементів. Англійський хімік Ньюлендс у 1804 р. навіть спробував об’єднати елементи в трійки. Проте тоді було відомо досить мало елементів, а Ньоюлендс не ризикнув зробити припущення про деяких елементів. Тому до його трійки потрапили і зовсім не схожі елементи, що викликало у одного опонента прискіпливе питання, чи не намагався автор розташувати елементи по алфавіту і чи не була при цьому помічена будь яка закономірність.
І все ж Мендєлєєв спробував піти забороненим шляхом, групуючи схожі елементи один з одним. Він зробив і наступний, найскладніший крок, спробував розмістити в правильному порядку і групи. Як писав пізніше сам Дмитро Іванович: „шукати щось, хоча б гриби, чи якусь залежність, не можна інакше, як дивлячись та пробуючи”. Для того щоб „дивитися і пробувати”, він почав підбирати, написавши на окремих картках назви елементів з їхніми атомними масами та властивостями даного елемента, схожі елементи та атомні маси.
Розкладуючи свій хімічний пасьянс, великий вчений після напружених роздумів, знайшов правильне розміщення елементів. Кажуть, що кінцевий вигляд таблиці постав перед ним у сні, коли, стомлений неперервними роздумами над нею, він приліг відпочити. Дивно, що ця праця, котра мала невраховані наслідки для розвитку хімії та фізики, була зроблена Мендєлєєвим за один день – зранку 17 лютого 1869 р. він ще не починав розкладати свій пасьянс, а до вечора того ж дня таблиця була написана.
Не тільки у відкритті періодичної системи елементів виявилась корисною комбінаторика. Як відомо серед обмежених об’єднань зустрічаються і ізомери, тобто об’єднання, котрі мають один і той самий склад, але різну будову. Комбінаторика дала можливість перерахувати усі ізомери даного складу.
У фізиці комбінаторика виявляється необхідною при вивчені властивостей кристалів, опису моделі феромагнетизму та ін.
Комбінаторика епохи комп’ютерів
Ми вже згадували, що зараз на наших очах змінюється співвідношення дискретної та класичної математики. На протязі двох з половиною століть основну роль у вивчені природи грав математичний аналіз – диференціальне та інтегральне числення, диференціальні рівняння математичної фізики, варіаційне числення та ін. Процеси, що мали автоматичну природу, замінювались неперервними, щоб можна було застосовувати до них розвинений апарат математики неперервного. Дискретна математика була Попелюшкою, краса якої затьмарювалась блиском впливових та сильних сестер.
Положення справ змінилося після того, як були створені ЕВМ. Тепер такі абстрактні образи математики, як математична логіка, загальна алгебра, формальні граматики, стали прикладними – для складання алгоритмічних мов, на яких пишуть програми для машин, потрібні спеціалісти саме з цих областей математики. Важливу роль почали відігравати різноманітні схеми, дослідження сітківок та їх властивості. Додатки до економіки поставили перед математиками нові типи проблем, що відносяться до математичного програмування та до цілочисельного програмування (якщо при рішенні задачі виявиться, що най економніше буде грузити по 3,5 автомашини, то рішення доведеться переглянути).
В цю епоху дискретної математики змінилась і роль давньої області дискретної математики – комбінаторики. З області, що цікавила більшу частину авторів задач та знаходила основні застосування в кодуванні і розшифровці давні писемностей, вона перетворилася на область, що знаходилась на магістральному шляху розвитку науки. За допомогою ЕВМ стало можливим робити перебори, що раніше потребували сотень і тисяч років.
Література:
Н. Я. Віленкін - „Популярная комбинаторика”