Історія розвитку комбінаторики та деякі її застосування, Детальна інформація

Проте його робота, написана на мало досяжному для багатьох вчених древньоєврейській мові, залишилась майже непоміченою – знову формулу (1) вивів на початку XVII ст. французький математик П. Ерігон.

Комбінаторика і схоластики

Своєрідною комбінаторикою займались і логіки. Продовжуючи досліди Аристотеля, вони класифікували поняття і логічні судження. В ІІІ ст. н.е. сирієць Порфирій для класифікації понять склав особливу схему, яка отримала назву „дерево Порфирія”. На вершині цього дерева містилось найширше за об’ємом поняття, вузли дерева відповідали різним роз’ясненням поняття, а лінії між вузлами відображали підлеглість понять одне одному. Схожі дерева зараз широко використовуються додатках комбінаторики до різноманітних питань.

Один із засновників медицини, Гален, в ІІ ст. н.е. займався класифікацією силогізмів, що складалися з чотирьох частин. Римський філософ і математик Боецій (V – VІ ст. н.е.) знайшов число пар, які можна скласти з п’яти категорій модальності, беручи їх як в затверджу вальній, так і в заперечній формі і ставлячи або на місце умови, або на місце слідства. Він також класифікував умовні силогізми.

Велику увагу класифікації видів суджень приділяла схоластична наука (взагалі в схоластиці химерно переплітались богуславські „вишуканості” з вивченням проблем, прилягаючих до комбінаторики, математичній логіці, теорії множин та іншим сучасним областям математики – великими затоками схоластичних дослідів були засновники теорії множин Бернард Больцано і Георг Кантор). Сперечаючись про взаємовідносини членів пресвятої трійці, про спів підлеглість ангелів, архангелів, херувимів та серафимів, схоласти були вимушені розглядати різні відношення порядку та ієрархії – достатньо згадати найскладнішу архітектуру стародавнього світу, яку описав Данте у „Божественній комедії” з її колами пекла і різними областями раю.

Схоласт Раймонд Люллій створив у ХІІІ ст. машину, що складалася з декількох кіл, на які було нанесено основні предикати, суб’єкти, атрибути та інші поняття схоластичної логіки. Повертаючи ці кола, він отримував різні суміщення понять і сподівався отримати з їх допомогою істину.

Комбінаторика в країнах Сходу

В VIII ст. н.е. почався розквіт арабської науки. Араби переклали багато творів грецьких учених, вивчили їх, а потім просунулись вперед по областях, мало звертавших увагу греків, - в науці про рішення рівнянь (саме слово „алгебра” – арабського походження), теорії та практиці обчислень та ін. Вирішуючи питання про знаходження коренів з будь-якого степеня, арабські алгебраїсти вивели формулу для степені суми двох чисел, яка відома під невірною історичною назвою „біном Ньютона”. Напевно цю формулу знав поет і математик Омар Хайям (ХІ – ХІІ ст. н.е.). у будь-якому випадку вже і ХІІІ ст. таку формулу друкує в своїх творах Насир ад-Дин ат-Туси, а в XV ст. вона була ретельно досліджена Гияседдином ал-Каші.

Судячи по деяких європейських джерелах, східним до арабських оригіналів, для пошуків коефіцієнтів цієї формули брали число 10001 и зводили його до 2-го, 3-го, ......, 9-го степеня. Виходила таблиця в якій жирним шрифтом були виділені коефіцієнти бінома Ньютона.

1000900360084012601260084003600090001

100080028005600700056002800080001

10007002100350035002100070001

1000600150020001500060001

100050010001000050001

10004000600040001

1000300030001

100020001

10001

Якщо опустити в цій таблиці зайві нулі, то вийде трикутна таблиця біноміальних коефіцієнтів. Арабські вчені знали основну властивість цієї таблиці, що виражається формулою

Ckn = Ckn–1 + Ck-1n-1

Одночасно з арабами вирахуванням біноміальних коефіцієнтів займались китайські математики. Вони склали до ХІІІ ст. н.е. таблицю таких чисел до n = 8, наведену в книзі алгебраїста Чжу Ши-дзе „Ямшове дзеркало”. Присутні здогади, що І Сінь в VIII ст. н.е. вирахував кількість різних розміщень фігур у грі, що нагадувала шахи.

Цікавились суміщеннями і в Індії. Ще в ІІ ст. до н.е. індійці знали числа Сkn і той факт, що сума C0n + C1n + … + Cnn дорівнювала 2n. А в ХІІ ст. індійський математик Бхаскара написав книгу „Лілаваті”, в якій серед інших питань математики вивчає і проблеми комбінаторики. Він пише про застосування перестановок до підрахунку варіацій у віршоскладанні, різних розміщень в архітектурі та ін. Він також дає правила для пошуку числа перестановок та суміщень декількох предметів, при чому розглядає і випадок, коли в цих перестановках є елементи, що повторюються.

Liber Abaci

На початку ХІІ ст. Східна Європа почала пробуджуватися після багатовікової духовної сплячки. Розвиток торгівлі зі Сходом призвів до проникнення у Європу арабської науки. Найбільш сміливі та охочі європейці пробиралися в Іспанію, що знаходилася під владою арабів, та знайомились там не тільки з твореннями грецьких вчених, але й з досягненнями арабської та індійської наукової думки – алгеброю та десятинною системою числення.

В арабських навчальних закладах отримав освіту і Леонардо – син видатного купця, що торгував у Алжирі. У своїй книзі „Liber Abaci”, що вийшла у 1202 р., Леонардо, котрий отримав прізвисько Фібоначчі, привів в систему арифметику арабів, деякі відомості з геометрії Евкліда і додав до них результати своїх досліджень. Праця Фебоначчі містила і нові комбінаторні задачі, наприклад про пошук найменшої кількості гир, за допомогою яких можна отримати будь-яку цілу вагу від 1 до 40 фунтів. Розглядав Леонардо і пошук цілих рішень рівнянь. В подальшому аналогічні задачі призвели до пошуку кількості натуральних рішень систем рівнянь і нерівностей, які можуть розглядатися як одна з глав комбінаторики.

Проте головною заслугою Леонардо перед комбінаторикою було те, що він сформулював і розв’язав задачу про кроликів. З часів грецьких математиків були відомі дві послідовності, кожний член яких отримувався за певних умов з попередніх – арифметична і геометрична прогресії. В задачі Леонардо з’явилась нова послідовність, члени якої були пов’язані один з одним відношенням un = un-1 + un-2. це була перша в історії науки формула, в якій наступний член виражався через два попередніх. Подібні формули отримали назву рекурентних (від лат. recurrere – повертатись). Метод рекурентних формул виявився одним із найпотужніших для рішення комбінаторних задач.

Гра в кості

Значний поштовх до розвитку комбінаторики дали азартні ігри, які існували ще в глибоку давнину, але отримали особливе розповсюдження після хрестових походів. Найбільшу популярність отримала гра в кості – два чи три кубики з нанесеними на них очками кидали на стіл, і вигравав той, хто отримував більшу кількість очок. В кості грали повсюди, виграючи та програючи в них золото, замки, дорогоцінні камені та коней. Атос – один з героїв „Трьох мушкетерів” – зумів грати навіть на свого слугу Гримо. Постанови церковних соборів містили досить суворі заборони цієї гри. Мусульманські вчені писали про гру в нарди, в якій пересування шашок визначалося кидком костей: „Як же ганебно для мудрого стати рабом двох камінців до такої міри, що він віддає свої досягнення та свою землю в їх руки, і вони наказують йому і забороняють, а він підкоряється їх керівництву більше, ніж підкоряється верблюд, коли його веде маленька дівчинка”.

Але ніщо не допомагало, і вбудь-якому місті можна було спостерігати картину, описану в „Божественній комедії” Данте:

Когда кончается игра в три кости,