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

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

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

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

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

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

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

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

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

Новое время

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

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

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

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

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

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

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

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

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

См. также

• Теория графов
• Теория игр

Примечания

Литература

• Виленкин Н. Я. . — М. : Наука, 1975. — 208 с.
• История математики. С древнейших времен до начала Нового времени // История математики / Под редакцией А. П. Юшкевича , в трёх томах. — М. : Наука, 1970. — Т. I.
• Математика XVII столетия // История математики / Под редакцией А. П. Юшкевича , в трёх томах. — М. : Наука, 1970. — Т. II.
• Математика XVIII столетия // История математики / Под редакцией А. П. Юшкевича , в трёх томах. — М. : Наука, 1972. — Т. III.
• Рыбников К. А. Комбинаторный анализ. Очерки истории. — М. : Изд. мехмата МГУ, 1996. — 124 с.
• Рыбников К. А. История математики в двух томах. — М. : Издательство МГУ, 1960-1963.