Комбинаторика: история и современность

 

Содержание 
 
 

     1. Древний период         1

     2. Средневековье          2

     3. Новое время          3

     4. Современное развитие        4

     5. Литература          5 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Появление и развитие комбинаторики 

     История комбинаторики освещает развитие комбинаторики  — раздела конечной математики, который исследует в основном различные способы выборки заданного  числа m элементов из заданного конечного множества: размещения, сочетания, перестановки, а также перечисление и смежные проблемы. Начав с анализа головоломок и азартных игр, комбинаторика оказалась исключительно полезной для решения практических задач почти во всех разделах математики. Кроме того, комбинаторные методы оказались полезными в статистике, генетике, лингвистике и многих других науках. 

1. Древний период 

Гексаграмма из «Книги Перемен»

Магический  квадрат на гравюре Дюрера «Меланхолия» 

     Комбинаторные мотивы можно заметить в символике  китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо[1]. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты.

     Классическая  задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.).[2]. Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона[2]. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени n равна 2n.

     Античные  греки также рассматривали отдельные  комбинаторные задачи, хотя систематическое  изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько  следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха — более 100000[3]. Аристотель при изложении своей логики безошибочно  перечислил все возможные типы трёхчленных  силлогизмов. Аристоксен рассмотрел различные  чередования длинных и коротких слогов в стихотворных размерах.[3] Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.). 

 
 

2. Средневековье 

     В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные  с перестановками и сочетаниями, включая перестановки с повторениями.

     В Западной Европе ряд глубоких открытий в области комбинаторики сделали  два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра обнаружил  симметричность биномиальных коэффициентов, а Герсонид дал явные формулы  для их подсчёта и применения в  задачах вычисления числа размещений и сочетаний.

     Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число  гирь, достаточное для взвешивания  любого товара весом от 1 до 40 фунтов.

 
 

3. Новое время 

     Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю  зарождавшейся теории вероятностей вошла переписка заядлого игрока шевалье де Мерэ с Пьером Ферма  и Блезом Паскалем, где были затронуты  несколько тонких комбинаторных  вопросов. Помимо азартных игр, комбинаторные  методы использовались (и продолжают использоваться) в криптографии —  как для разработки шифров, так  и для их взлома. 

Треугольник Паскаля

     Блез  Паскаль много занимался биномиальными  коэффициентами и открыл простой  способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого  треугольника. Наряду с Лейбницем, он считается основоположником современной  комбинаторики. Сам термин «комбинаторика»  придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал  книгу «Рассуждения о комбинаторном  искусстве». Правда, термин «комбинаторика»  Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику[4]. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей  книге «Искусство предположений» (1713) множество сведений по комбинаторике.

     В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).

     После появления математического анализа  обнаружилась тесная связь комбинаторных  и ряда аналитических задач. Абрахам  де Муавр и Джеймс Стирлинг нашли  формулы для аппроксимации факториала.[5]

     Окончательно  комбинаторика как самостоятельный  раздел математики оформилась в трудах Эйлера. Он детально рассмотрел, например, следующие проблемы.:

• Задача о ходе коня
• Задача о семи мостах, с которой началась теория графов
• Построение греко-латинских квадратов
• Обобщённые перестановки

 

     Кроме перестановок и сочетаний, Эйлер  изучал разбиения, а также сочетания  и размещения с условиями. 

4. Современное развитие 

     В начале XX века начала развиваться комбинаторная  геометрия: были доказаны теоремы Минковского  — Радона, Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема. На стыке топологии, анализа  и комбинаторики были доказаны теоремы  Борсука — Улама и Люстерника — Шнирельмана. Во второй четверти XX века были поставлены проблема Борсука  и проблема Нелсона — Эрдёша —  Хадвигера. В 1940-х годах оформилась теория Рамсея. Отцом современной  комбинаторики считается Пал  Эрдёш, который ввёл в комбинаторику  вероятностный анализ. Внимание к  конечной математике и, в частности, к комбинаторике значительно  повысилось со второй половины XX века, когда появились компьютеры. Сейчас это чрезвычайно содержательная и быстроразвивающаяся область  математики.

Разрозненные  комбинаторные задачи человечество решало с незапамятных времён. К  концу XVI века накопились знания, относящиеся  к:

1. свойствам фигурных чисел,
2. построению магических (и иных числовых) квадратов,
3. свойствам биномиальных коэффициентов.

Готфрид Вильгельм Лейбниц

Элиаким Гастингс Мур

Джеймс  Джозеф Сильвестр

 

- строит  таблицы сочетаний до n = k = 12, после чего рассуждает о приложениях комбинаторики к логике, арифметике, к проблемам стихосложения и др.

В течение  всей своей жизни Лейбниц многократно  возвращался к идеям комбинаторного искусства. Комбинаторику он понимал  весьма широко, именно, как составляющую любого исследования, любого творческого  акта, предполагающего сначала анализ (расчленение целого на части), а  затем синтез (соединение частей в  целое). Мечтой Лейбница, оставшейся, увы, неосуществлённой, оставалось построение общей комбинаторной теории. Комбинаторике Лейбниц предрекал блестящее будущее, широкое применение.

В XVIII веке к решению комбинаторных задач  обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о  построении магических и латинских  квадратов.

В 1713 году было опубликовано сочинение Я. Бернулли "Искусство предположений", в  котором с достаточной полнотой были изложены известные к тому времени  комбинаторные факты. "Искусство  предположений" появилось после  смерти автора и не было автором  завершено. Сочинение состояло из 4 частей, комбинаторике была посвящена  вторая часть, в которой содержатся формулы:

• для числа перестановок из n элементов,
• для числа сочетаний (называемого Я. Бернулли классовым числом) без повторений и с повторениями,
• для числа размещений с повторениями и без повторений.

Для вывода формул автор использовал наиболее простые и наглядные методы, сопровождая  их многочисленными таблицами и  примерами. Сочинение Я. Бернулли превзошло  работы его предшественников и современников  систематичностью, простотой методов, строгостью изложения и в течение XVIII века пользовалось известностью не только как серьёзного научного трактата, но и как учебно-справочного издания. В работах Я. Бернулли и Лейбница тщательно изучены свойства сочетаний, размещений, перестановок. Перечисленные  комбинаторные объекты относятся  к основным комбинаторным конфигурациям . В математике в XIX веке появился сначала термин "геометрическая конфигурация" в лекциях по проективной геометрии профессора университета в Страсбурге К.Т. Рейе (1882).

разложения. Мур обогатил список известных комбинаторных  конфигураций построением новых, обобщающих системы троек Штейнера, и системы  троек Киркмана. Мур построил системы  
S[k, l, m], m  k  l ( m, k, l - натуральные числа), содержащие такие k -сочетания (блоки) из m элементов, что каждое l -сочетание входит точно в одно k -сочетание. Число k -сочетаний в системе S[k, l, m] равно  . Мур в своей статье ссылается на Артура Кэли, который подчёркивал высокую значимость тактических задач в алгебре.

Комбинаторика, пройдя многовековой путь развития, обретя собственные методы исследования, с  одной стороны, широко используется при решении задач алгебры, геометрии, анализа, с другой стороны, сама использует геометрические, аналитические и  алгебраические методы исследования. В конце XVIII века учёные, принадлежащие  комбинаторной школе Гинденбурга, попытались построить общую комбинаторную  теорию, используя бесконечные ряды. Исследователи этой школы изучили  большое количество преобразований рядов: умножение, деление, возведение в степень, извлечение корней, обращение  рядов, разложение трансцендентных  функций. Использование производящих функций в комбинаторике можно  отнести к (уже) классическим традициям.

В XX веке комбинаторика подверглась  мощному процессу алгебраизации  благодаря работам  
Дж.-К. Рота (1964), а затем Р. Стенли. Изучение ими частично упорядоченных множеств, свойств функции Мёбиуса, абстрактных свойств линейной зависимости, выявление их роли при решении комбинаторных задач способствовали обогащению комбинаторных методов исследования и дальнейшей интеграции комбинаторики в современную математику.