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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 Основные правила комбинаторики.

 

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

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

Если некоторый объект А можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m+n способами.

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

Пример. Пусть из пункта А в пункт В можно добраться самолетом, поездом и автобусом, причем между этими пунктами существуют 2 авиамаршрута, 1 - железнодорожный и 3 - автобусных Следовательно, общее число маршрутов между пунктами А и В равно 2 + 1 + 3 = 6

Второе правило, называемое правилом произведения, несколько сложнее.  Часто при составлении комбинации из двух элементов известно, сколькими способами можно выбрать первый элемент, и сколькими способами второй, причем число способов выбора второго элемента не зависит от того, как именно выбран первый элемент. Пусть первый элемент можно выбрать m способами, а второй n способами. Тогда пару этих элементов можно выбрать mn способами. Иными словами:

Если объект А можно  выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить mn способами.

Для доказательства правила  произведения заметим, что каждый из m способов выбора объекта А можно скомбинировать с n способами выбора объекта В. А это и приводит к mn способам выбора пары (А,В).

Пример. Сколькими различными способами можно распределить четыре шара по двум лункам, в которые помещается ровно один шар. Очевидно, первую лунку можно заполнить четырьмя способами, так как при выборе первой лунки имеется четыре шара. Вторую лунку можно заполнить тремя шарами, так как после заполнения первой лунки осталось три шара. Заметим, что с каждым из четырех способов заполнения первой лунки может совпасть любой из трех способов заполнения второй. Поэтому общее число способов распределения двух лунок равно 4x3 = 12

Комбинаторные задачи.

 

1. Метод решения: перебор возможных вариантов.

Способы:

1. способ кодировки
2. способ построения дерева возможных вариантов
3. способ набора точек и отрезков
4. способ табличный

 

2. Формулы комбинаторики.

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

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

В теории вероятностей принято  говорить не о комбинациях, а о  выборках. Поэтому мы будем придерживаться термина «выборка». В комбинаторике рассматриваются виды выборок — перестановки, размещения, сочетания.

Генеральная совокупность без повторений — это набор некоторого конечного числа различных элементов:

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

Выборкой объема будем называть произвольную группу из т элементов данной генеральной совокупности. Наглядному представлению такой выборки может служить последовательность из т шаров, выбранная из имеющегося множества.

Каким минимальным признаком  может отличиться одна выборка объема т от другой выборки такого же объема? Это равносильно вопросу: каким минимальным признаком могут отличаться две линейки из шариков, построенная из их одинакового количества?

Минимальным признаком, отличающим одну выборку объема т от другой выборки такого же объема, может быть:

1) их различие по  крайней мере одним элементом

2) их различие порядком расположения элементов.

Назовем такие выборки размещениями без повторений из п элементов по т.

Отсюда следует определение  понятия:

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

Характерный пример размещений без повторений —  вся совокупность четырехзначных номеров, в каждом из которых нет повторения цифр.

Число размещений из п элементов по m договоримся обозначать . Попробуем определить это число.

Пусть мы имеем п элементов. Первый элемент можно выбрать п способами. Второй приходится выбирать из оставшихся (п-1) элементов, поэтому второй элемент можно выбрать (п-1) способом. Тогда по правилу произведения пары двух элементов можно образовать п(п-1) способами. Третий элемент придется отбирать из числа оставшихся (п-2) элементов. Это можно сделать (п-2) способами. Тогда опять по правилу произведения тройки элементов можно образовать п (п-1)(п-2) способами. Аналогично четверки можно образовать п (п- 1) (п- 2) (п- 3) способами, а размещения по m элементов п (п — 1) (п — 2)…(п-(т- 1)) способами. Таким образом,

Преобразуем полученную формулу, умножая и деля правую часть на произведение:

. Тогда выведенная формула имеет вид:

 

.

 

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

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

Характерный пример перестановок без повторений — вся совокупность всех десятизначных номеров, в каждом из которых нет повторения цифр.

Обозначим число  перестановок объема п символом Р_п. Тогда по определению

Среди размещений без повторений из п элементов по m (m < п) можно выделить такие, которые отличаются одно от другого  только первым признаком, а именно по крайней мере одним элементом. Значит:

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

Число таких сочетаний  обозначается символом . Разумеется, при т = п .

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

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

,

откуда

.

 

Примеры использования  полученных формул:

Задача 1. На тренировках занимаются 12 баскетболистов. Сколько может быть образовано тренером разных стартовых пятерок?

Решение: Так как при  составлении стартовой пятерки тренера интересует только состав пятерки, то достаточно определить число сочетаний из 12 элементов по 5:

.

 

Задача 2. Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли взять друг друга?

Решение: Ясно, что в  этом случае на каждой горизонтали  и каждой вертикали шахматной  доски может быть расположено  только по одной ладье. Число возможных  позиций — число перестановок из 8 элементов:

.

3. Для научной экспедиции необходимо укомплектовать следующий команду: начальник экспедиции, первый его заместитель, второй заместитель, два сотрудника и один стажер. Начальник и его заместители может быть отобрана из числа 25 кандидатов наук, два сотрудника — из числа 20 специалистов, в совершенстве знающих характер предстоящей работы, и стажер — из числа 8 наиболее подготовленных студентов. Сколькими способами можно укомплектовать команду экспедиции?

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

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

Значит по правилу  умножения всю экспедицию можно  укомплектовать способами.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы.

 

1. Н.Я. Виленкин. Популярная комбинаторика. - М.: Наука, 1975.
2. Н.Я. Виленкин. Комбинаторика. - М.: Наука, 1969.
3. П.В. Грес. Математика для гуманитариев. - М.: Юрайт, 2000.
4. Я.С. Бродский. Статистика. Вероятность. Комбинаторика. - М.: Оникс, 2008.
5. Энциклопедия для детей. Метематика. Том 11. – М.: Аванта+, 1998.