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

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

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

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

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

Новое время В этот же период формируется терминология новой науки. Термин « сочетание » впервые встречается у Паскаля (1653, опубликован в 1665 году ). Термин « перестановка » употребил в указанной книге Якоб Бернулли ( хотя эпизодически он встречался и раньше ). Бернулли использовал и термин « размещение ». После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала. Окончательно комбинаторика как самостоятельный раздел математики оформилась в трудах Эйлера. Он детально рассмотрел, например, следующие проблемы : Задача о ходе коня Задача о семи мостах, с которой началась теория графов Построение греко - латинских квадратов Обобщенные перестановки Кроме перестановок и сочетаний, Эйлер изучал разбиение, а также сочетания и размещения с условиями.

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

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