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

4.1. Перестановки, размещения и их количество

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

Определение 1. Пусть имеется элементов, отличающихся друг от друга какими-то признаками, например, номерами, названиями, индексами и т. д. Назовем эту совокупностьгенеральной совокупностью.

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

Правило суммы. Пусть объект можно выбратьспособами, объектможно выбратьспособами. Тогда выбор либо объекта, либо объекта можно осуществить способами.

Пример 1. Студент выбирает какую-либо одну книгу на полке, где находятся 20 различных учебников по математике, 15 учебников по информатике и 10 учебников по химии. Тогда существуют 20 + 15 + 10 = 47 различных вариантов выбора книги.

Правило произведения. Пусть объект можно выбратьспособами, объектможно выбратьспособами. Тогда выбор парыиможно осуществитьспособами.

Пример 2. Из города в городведут 5 дорог, а из городадо городаведут 4 дороги. Следовательно, количество путей, ведущих изви проходящих через город, равно.

Рассмотрим группы элементов, называемые перестановками, размещениями и сочетаниями.

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

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

Каждая перестановка содержит все элементов множества, и различные перестановки отличаются только порядком элементов.

Число перестановок из элементов обозначается, где– первая буква от английского словаpermutation – перестановка.

Определение 4. Произведение подряд идущих натуральных чисел от 1 до некоторого называетсяфакториалом целого положительного числа и обозначается. Таким образом,. Принято считать, что.

Пример 3. Сколько различных четырехзначных чисел можно составить из цифр 1, 2, 5, 8 при условии, что цифры в числе не повторяются?

Решение

Количество различных четырехзначных чисел из данных цифр равно числу перестановок из четырех элементов .

Пример 4. Найти , если.

Решение

Применяя формулу для числа перестановок, запишем соотношение в виде .

Подберем значение , исходя из равенств,,,,,.

Следовательно, , откудаи.

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

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

Число размещений обозначается символом , где– первая буква от французского словаarrangement, что означает размещение, приведение в порядок.

Формулу удобно записывать в виде.

Заметим, что при мы получаем формулу перестановок.

Пример 5. Сколько существует способов избрания президента, вице-президента, секретаря и казначея из 32 членов клуба?

Решение

Из 32 человек необходимо выбрать четверых, причем важно, в каком порядке будет происходить выбор, поскольку каждому достаются различные посты. Поэтому количество способов равно числу размещений из 32 по 4:

.

Пример 6. Найти , если.

Решение

Применяя формулы для числа перестановок и числа размещений, запишем соотношение в виде .

После сокращения получим ,,,. Поскольку числонатуральное, то смысл имеет только значение.