§6. Основные правила комбинаторики. Перестановки, размещения и сочетания без повторений

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

Рассмотрим два основных правила, с помощью которых решается большинство задач комбинаторики.

Правило суммы:

Если некоторый объект а можно выбрать n способами, а другой объект b — m способами, то выбор «либо a либо b» можно произвести (n+m) способами.

При использовании правила суммы в последней формулировке надо следить, чтобы ни один из способов выбора объекта а не совпадал с каким-нибудь способом выбора объекта b. Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь m+n–k способов выбора, где k — число совпадений.

Задача. Допустим, что разноцветных шариков распределены по двум ящикам: в первом –– шаров, во втором –– . Произвольно из какого–нибудь ящика вынимаем один шарик. Сколькими разными способами можно это сделать? Из первого ящика шарик можно вынуть разными способами, из второго –– разными способами. Всего способами.

Правило произведения:

Это правило применяется, когда необходимо выбрать пару элементов. Известно, что первый элемент пары можно выбрать n способами, а второй — m способами. Причём число способов выбора второго элемента не зависит от выбора первого элемента. Тогда всю пару можно выбрать (n∙m) способами.

Задача. Сколько можно записать двузначных чисел в десятичной системе счисления?

Решение. Число десятков двузначного числа может принимать одно из девяти значений: 1, 2, 3, 4, 5, 6, 7, 8, 9. Число единиц может принимать одно из десяти значений: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Если цифра десятков 1, цифра единиц может быть 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 –– всего 10 значений. Если цифра десятков 2, то вновь, цифра единиц может быть равна 0, 1, 2, …, 9. Всего получим 90 () двузначных чисел.

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

Задача. Сколько можно составить k-расстановок, если первый элемент может быть одного из n1 различных видов, второй — из n2 различных видов, ..., k-й — из nk различных видов. При этом две расстановки считаются различными, если хотя бы на одном месте в них стоят разные элементы.

Решение:

Первый элемент можно выбрать n1 способами. Каждый из выбранных элементов можно соединить с любым из n2 видов вторых элементов, что дает (n1∙n2) пар. Каждую пару можно соединить с любым из n3 видов третьих элементов, что дает (n1 ∙n2∙ n3) троек, и т. д.мы получим в конце концов (n1 ∙n2∙…∙ nk ) расстановок искомого типа.

Напомним, что множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое натуральное число (номер элемента) от 1 до , где –– число элементов множества, так что различным элементам соответствуют различные числа.

Очевидно, что каждое множество, содержащее более одного элемента, можно упорядочить не единственным способом.

Определение 1. Различные упорядоченные множества, которые отличаются лишь порядком элементов (т.е. могут быть получены из того же самого множества), называются перестановками этого множества (здесь важен порядок элементов).

Множество из одного элемента можно упорядочить одним–единственным образом: единственный элемент множества приходится считать первым. Возьмем множество из двух элементов, для примера, из двух букв А и Б. Очевидно, что их можно расположить по порядку двумя способами:

АБ или БА.

Три буквы А, Б, В можно расположить по порядку шестью способами:

АБВ, АВБ, БАВ, БВА, ВАБ, ВБА.

Число перестановок из элементов обозначают . Мы нашли, что

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

.

Будем последовательно выбирать элементы данного множества, и размещать их в определенном порядке на местах. На первое место можно поставить любой из элементов. После того как заполнится первое место, на второе место можно поставить любой из оставшихся n–1 элементов. После того как заполнятся первое и второе места, на третье место можно поставить любой из оставшихся элементов и т.д. По правилу умножения все мест можно заполнить

способами. Таким образом, .

Рассмотрим теперь упорядоченные подмножества данного множества.

Определение 2. Конечные упорядоченные подмножества данного множества называются размещениями данного множества (здесь важен порядок элементов).

Число упорядоченных k–элементных подмножеств множества, состоящего из различных элементов, т.е. число размещений из по k обозначают и вычисляется по формуле.

.

Пример 2. Сколькими способами можно выбрать четырех человек на четыре различные должности из девяти кандидатов на эти должности?

Решение.

Если задано некоторое множество Х, то можно рассматривать новое множество М(Х) –– множество всех его подмножеств.

Рассмотрим все подмножества множества {А; Б; В}; их восемь: ? –– пустое множество; {А}, {Б}, {В} –– три множества по одному элементу в каждом; {А; В}, {А; Б}, {Б; В} –– три множества по два элемента в каждом; {А; Б; В} –– одно множество из трех элементов.

Естественно задать вопрос: сколько различных –элементных подмножеств имеет множество из элементов?

Определение 3. Произвольное –элементное подмножество –элементного множества называется сочетанием из элементов по (здесь порядок элементов не важен).

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

Пример 3. В девятом классе 35 учащихся. Из них нужно выбрать четыре делегата на конференцию. Сколько имеется возможностей такого выбора?

Решение.