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

Как и многие разделы математики, комбинаторика, относясь к дискретной математике, появилась достаточно давно. Задачи комбинаторики упоминаются в трудах индийских математиков еще в IV веке до н.э. Первые научные работы в этой области принадлежат ученым средневековья, таким как Галилео Галилей, Пьер Ферма. Как самостоятельный раздел математики, комбинаторику стали рассматривать в XVII веке, с появлением трудов немецкого ученого Г.В. Лейбница. Именно он впервые ввел термин «комбинаторика» (combinare), означающий «соединять, сочетать».
Сегодня в понятие «комбинаторика» вкладывают изучение способов выборки заданного числа  элементов из заданного конечного множества, а именно размещение, сочетание, перестановку, перечисление и смежные проблемы. Методы комбинаторики используются во многих науках для решения практических задач, например статистике, лингвистике, физике, генетике, химии, информатике. Помимо выполнения научных задач комбинаторика помогает решать головоломки, шифровать данные, играть в игры, развивая мышление и логику человека.
В основе комбинаторики лежит теория множества. Под множеством подразумевается произвольный набор различных элементов, определяемый как единое целое. При этом запись того, что некоторый элемент x является элементом множества A, выглядит следующим образом: x A.
Множество можно задать двумя способами:
путем перечисления всех его элементов, например
В = {1,2,3,..,11};
2) описав характеристические свойства его элементов. При этом способе определяется свойство которым обладает каждый элемент входящий в множество, а не принадлежащие к множеству элементы этим свойством не обладают, например В = {x|1 x 4 x Z}.
Существуют множества, которые не содержат в себе элементов, называются пустыми и обозначаются значком . Пустое множество может быть подмножеством любого другого множества.
Если указаны все элементы множества с помощью некоторого общего признака или с помощью некоторого списка элементов, то оно считается определенным. Если множество имеет конечное число элементов, его принято называть конечным множеством. Именно с таким типом множеств работает комбинаторика.
Основное правило комбинаторики – правило умножения, которое можно представить в следующем общем виде: если необходимо выполнить одно за другим действия (k), причем первое действие можно выполнить n1 способами, второе действие n2 способами, третье n3, и так до nk -способа k-го действия, то все k-действия вместе могут быть выполнены способами N, рассчитанными как произведение, т.е
N = n1 ∙ n2 ∙ n3 ∙… ∙ nk..
Например, необходимо вычислить, сколько трехзначных чисел можно составить из цифр 4, 5, 6, 7, 8, 9, если ни одна из цифр не повторяется.
Решение данной задачи будет выглядеть следующим образом. Первой цифрой трехзначного числа может быть любая из предложенных, соответственно количество способов выбора первой цифры числа – 6. Вторая цифра будет выбрана 5-тью способами, третья – 4-мя

. Значит, в соответствии с основным правилом комбинаторики – правилом умножения, общее число способов будет рассчитано так: 6∙5∙4=120.
Так же важным правилом комбинаторики является правило сложения, которое можно сформулировать следующим образом:
Если элемент А можно выбрать n-способами, а элемент В выбрать m-способами, то выбор элемента А  или элемента В, можно осуществить  N способами, равными N = m + n.
Например, необходимо определить количество способов N, которыми можно выбрать синий и красный карандаш из коробки цветных карандашей, в которой лежат 6 зеленых, 8 красных, 4 синих и 5 желтых карандашей. Согласно правилу сложения, решение данной задачи будет следующим: N=4+8 =12 способов.
В теории комбинаторики выделяют три основных понятия: сочетания; перестановки и размещения (без повторений и с повторениями).
Сочетания.
Любое множество может быть образовано из подмножеств, образуя те или иные совокупности. Произвольное k-элементное подмножество множества из n элементов называется сочетанием (комбинацией) из n-элементов по k. При этом порядок элементов в подмножестве не имеет значения. По другому можно сказать, что сочетаниями Сnk   из n-элементов по k называются неупорядоченные совокупности, отличающиеся друг от друга хотя бы одним элементом.
Сочетаниями без повторений из n-элементов по k называют комбинации, получаемые путем выборки из генеральной совокупности сразу несколько элементов, либо элементов взятых последовательно, но без учета порядка их появления. Число таких сочетаний определяют по формуле:
Сnk=n!(n-k)!∙k! (1)
Рассмотрим, как можно применить формулу 1 для решения задач на сочетание.
Задача. Замок домофона можно разблокировать одновременным нажатием трех кнопок. При этом на замке всего 9 символов. Какое количество комбинаций существует для разблокировки замка домофона?
Решение. Искомое число комбинаций равно числу трех-элементарных подмножеств множества 9 элементов, то есть является сочетанием без повторений из n=9 элементов по k=3. Вычисляем по формуле 1:
С93=9!(9-3)!∙3!=9∙8∙7∙6∙5∙4∙3∙2(6∙5∙4∙3∙2)∙(3∙2)=9∙8∙73∙2 =84
В результате вычислений мы выяснили, что для разблокировки замка домофона существует 84 комбинации.
В случае если необходимо определить сочетание из m-элементов по n-элементов, получаемые путем выборки из генеральной совокупности сразу несколько элементов, либо элементов взятых последовательно, с учетом порядка их появления, то есть которые могут повторяться, используют формулу для расчета сочетаний с повторениями:
Nmn = Cm+n-1 n= (m+n-1)!n!(m-1)! (2)
В качестве примера применения формулы 2 используем задачу из примера 1, но внесем в её условие некоторые изменения.
Задача. Замок домофона можно разблокировать последовательным нажатием трех кнопок, причем кнопки могут повторяться. На замке всего 9 символов. Какое количество комбинаций существует для разблокировки замка домофона?
Решение