Возникновение комбинаторики

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

     Термин "комбинаторика" был введён в  математический обиход знаменитым Лейбницем. В 1666 году он опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов выводит свойства сочетаний, строит таблицы сочетаний до n = k = 12, после чего рассуждает о приложениях комбинаторики к логике, арифметике, к проблемам стихосложения и др.

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

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

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

     -для  числа перестановок из n элементов  

     -для  числа сочетаний (называемого  Я. Бернулли классовым числом) без повторений и с повторениями; 

     -для  числа размещений с повторениями  и без повторений.  

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

     В 1896 году американский математик Элиаким Гастингс Мур ввёл термин тактическая конфигурация в статье "Tactical memoranda", понимая под этим термином систему n множеств, содержащих, соответственно, a1, a2, … , an элементов. Тактическую конфигурацию Мур задаёт квадратной матрицей порядка n, в которой элемент akk, стоящий на главной диагонали, равен числу ak (числу элементов в k-ом множестве); элемент aij (i j) равен числу элементов i-ого множества, инцидентных j -ому множеству. К тактическим конфигурациям Мур относит сочетания, размещения, системы решений задачи Киркмана о 15 школьницах, подгруппы некоторых групп. Он демонстрирует широкий спектр задач из геометрии, теории групп, которые приводят к тактическим разложениям или используют тактические разложения. Мур обогатил список известных комбинаторных конфигураций построением новых, обобщающих системы троек Штейнера, и системы троек Киркмана. Мур построил системы S[k, l, m], m k l ( m, k, l - натуральные числа), содержащие такие k -сочетания (блоки) из m элементов, что каждое l -сочетание входит точно в одно k -сочетание. Число k -сочетаний в системе S[k, l, m] равно . Мур в своей статье ссылается на Артура Кэли, который подчёркивал высокую значимость тактических задач в алгебре.

     Термин "тактика" ввёл в математику английский математик Джеймс Джозеф Сильвестр  в 1861 году. Сильвестр определял тактику, как раздел математики, изучающий расположение элементов друг относительно друга. В сфере этого раздела находится, по мнению Сильвестра, теория групп, комбинаторный анализ и теория чисел. Мысли Сильвестра о тактике разделял его друг Артур Кэли.

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

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

     Простейшие  комбинаторные задачи напоминают детскую  игру в кубики. Имеется конечное число кубиков, или элементов  некоторого конечного множества, а  нужно подсчитать количество тех или иных комбинаций, составленных из тех кубиков. Если нужных комбинаций не слишком много, то все их можно просто перечислить, или, как говорят, перебрать все возможности. В этом и состоит метод перебора вариантов. Например, если из цифр 1, 5, 9 следует составить трехзначное число без повторяющихся цифр, то все возможные варианты не трудно выписать. Это 159, 195, 519, 591, 915 и 951. Значит, всего можно составить шесть таких чисел.

     Подчеркну, что уже в этом простом примере  я привела не случайный, а разумно организованный перебор. Сначала на первом месте зафиксировала 1 и увидела, что таких вариантов всего два: 159 и 195. затем на первое место поставила 5 и увидела, что получилось ёщё два варианта:519 и 591. наконец,  таким же образом составила числа, начинающиеся с 9,- это 915 и 951.

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