1.2. Элементы комбинаторики

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

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

Правило умножения. Пусть требуется выполнить одно за другим (последовательно) k действий. Если первое действие можно выполнить n₁ способами, второе n₂ способами, и так далее до k-го действия, которое можно выполнить n_k способами, то все k действий можно выполнить n₁ ∙ n₂ ∙… ∙ n_k способами.

Правило сложения. Если элемент А может быть выбран m способами, а элемент В – n способами, то выбрать либо А, либо В можно m + n способами.

Пример 1. В группе 28 человек. Необходимо выбрать старосту и профорга. Сколькими способами это можно сделать?

Решение. Старостой может быть выбран любой из 28 студентов, т. е. существует 28 способов выбора старосты. Профоргом можно выбрать любого из оставшихся 27 студентов, так как один уже выбран старостой. Тогда общее число способов выбора старосты и профорга равно

Пример 2. Имеется 16 изделий 1-го сорта и 25 изделий 2-го сорта. Необходимо выбрать два изделия одного сорта. Сколько способов выбора двух изделий возможно в данной ситуации?

Решение. По правилу умножения два изделия 1-го сорта можно выбрать способами. Аналогично, два изделия 2-го сорта можно выбратьспособами. Поэтому общее число способов выбора изделий или 1-го, или 2-го сорта равно.

Существуют две схемы выбора m элементов из заданного множества: без возвращения и с возвращением.

Схемы выбора без возвращения предполагают, что выбранные элементы не возвращаются в исходное множество.

Размещениями из n элементов по m (0 ≤ m ≤ n) называются соединения по m элементов, которые отличаются друг от друга либо хотя бы одним элементом, либо порядком их расположения.

Число размещений обозначается символом и вычисляется по формуле:

Замечание: символ (читается «эн факториал») обозначает произведение всех натуральных чисел от 1 доn включительно:

.

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

Решение. Искомое число способов равно

В частном случае, когда выбираются все элементы, т. е. m = n, размещения называются перестановками.

Перестановками из n элементов называются соединения, содержащие все n элементов и отличающиеся друг от друга порядком следования элементов.

Число перестановок обозначается символом и вычисляется по формуле:

Пример 4. Сколькими способами можно составить четырехцветный флаг из горизонтальных полос, имея четыре различных цвета?

Решение. В данном случае различные флаги отличаются друг от друга лишь порядком цветов. Число возможных флагов равно

Сочетаниями из n элементов по m называются соединения по m элементов, отличающиеся друг от друга хотя бы одним элементом.

Число сочетаний из n элементов по m обозначается иопределяется по формуле:

.

Для чисел называемых также биномиальными коэффициентами, справедливы следующие тождества:

(свойство симметрии);

(рекуррентное соотношение);

;

(следствие бинома Ньютона).