Статья по математике "Комбинаторика"

                               Комбинаторика

                           Историческая справка

Комбинаторика (комбинаторная математика, комбинаторный анализ) — раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами.

Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторики является изучение комбинаторных конфигураций. Это изучение включает в себя вопросы существования комбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задач перечисления, в частности определение числа конфигураций данного класса. Простейшими примерами комбинаторных конфигураций являются перестановки, сочетания и размещения.

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Термин «комбинаторика» был введён в математический обиход Г. Лейбницем.

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

Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов. Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах. Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии.

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

В Западной Европе ряд важных открытий в области комбинаторики сделали два еврейских исследователя: Авраам ибн Эзра и Леви бен Гершом.

Авраам бен Меир ибн Эзра (1089–1164) — знаменитый средневековый философ, поэт, мыслитель, лингвист, астролог, астроном и математик. Ему принадлежат вычисления и установление свойств биноминальных коэффициентов.

Леви бен Гершом (известный также как Лев Герсонид, 1288–1344) — средневековый учёный- универсал: философ, математик, астроном. В трактате «Дело вычислителя» он первым в Европе вывел основные комбинаторные формулы для подсчёта числа сочетаний, перестановок и размещений. Для их доказательства он применял математическую индукцию и вплотную подошёл к выделению индукции в отдельный метод. Работа Леви бен Гершома была написана на труднодоступном большинству учёных древнееврейском языке, поэтому, например, формулу:

заново вывел в начале ХVII в. французский математик П. Эригон, а окончательное оформление метода математической индукции обычно приписывают Паскалю.

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

Значительный толчок к развитию комбинаторики дали такие игры, как шашки, шахматы, домино, карты и, особенно, кости — бросание игральных кубиков.

Наукой комбинаторика становится лишь в XVII веке — в период, когда возникла теория вероятностей. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчинённых тем или иным условиям. После первых работ, выполненных в XVI в. итальянскими учёными Дж. Кардано, Н. Тартальей и Г. Галилеем, такие задачи изучали французские математики Б. Паскаль и П. Ферма.

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

Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666 г. работу «Размышления о комбинаторном искусстве», в которой впервые появляется сам термин «комбинаторный». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику.

Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» множество сведений по комбинаторике.

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

Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей.

Возникновение основных понятий и развитие комбинаторики шло параллельно с развитием других разделов математики, таких как алгебра, теория чисел, теория вероятностей, с которыми комбинаторика тесно связана. После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач.

Значительные достижения в области комбинаторики принадлежат Л. Эйлеру. В его трудах комбинаторика окончательно оформилась как самостоятельный раздел математики.

Идеи комбинаторного характера имеют самое широкое распространение в математике, в таких её разделах, как теория вероятностей, теория чисел, алгебра и др.

Комбинаторика тесно связана с теорией графов, теорией конечных автоматов и другими отраслями математики. Её результаты применяют при планировании и анализе научных экспериментов, кодировании сообщений, в линейном и динамическом программировании, в математической экономике.

В настоящее время комбинаторика находит приложения во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т. д.