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

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

1. Перестановки

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

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

Число перестановок обозначается Р_п и читается «Р из л».

Пример 5.21.

Примеры перестановок:

• — распределение п различных должностей среди п человек;
• — расположение п различных предметов в одном ряду. ?

Сколько различных перестановок можно образовать во множестве U?

Чтобы вывести формулу числа перестановок, представим себе п ячеек, пронумерованных 1, 2, …, п. Все перестановки будем образовывать, располагая элементы U в этих ячейках.

В первую ячейку можно занести любой из п элементов (иначе: первую ячейку можно заполнить п различными способами). Заполнив первую ячейку, можно (п — 1) способом заполнить вторую ячейку (иначе: при каждом способе заполнения первой ячейки находится (п — 1) способов заполнения второй ячейки).

Таким образом, существует п (п — 1) способов заполнения двух первых ячеек. При заполнении первых двух ячеек можно найти (п — 2) способов заполнения третьей ячейки, откуда получается, что три ячейки можно заполнить п (п — 1)(п — 2) способами.

Продолжая этот процесс, получим, что число способов заполнения п ячеек равно п (п — 1)(п — 2) •… -3 -2 • 1. Это произведение определяет число перестановок:

п! читается «п-факториал».

Считается, что 1! = 1; 0! = 1.

На книжной полке стоит шесть книг по юриспруденции. Сколькими способами можно расположить эти книги на полке?

Решение. Так как порядок книг по условию примера значения не имеет, то это задача о числе перестановок 6 разных книг. Следовательно,.

Также одним из вариантов комбинаций являются перестановки с повторяющимися элементами.

Если среди т элементов имеется т_г одинаковых элементов одного типа, т₂ одинаковых элементов другого типа и т. д., то при перестановке этих элементов всевозможными способами получаем комбинации, количество которых определяется по формуле.

где т_к — количество элементов последнего к-то типа.

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

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

Номер автомобиля состоит из трех букв и четырех цифр. Сколько различных номеров можно составить, используя 10 цифр и алфавит в 30 букв?

Решение. Очевидно, что количество всех возможных комбинаций из 10 цифр по 4 равно 10 000.

Так как буквы могут повторяться, то число повторяющихся комбинаций по две буквы равно 30 • 30 = 900.

Поскольку номер содержит не две, а три буквы, то количество комбинаций увеличивается в 30 раз, т. е. достигает 27 000 комбинаций.

Так как каждой буквенной комбинации можно поставить в соответствие любую числовую комбинацию, то полное количество автомобильных номеров равно 27 000 • 10 000 = 270 000 000. ?

Пример 5.26.

Сколькими способами можно переставить буквы в слове «какао», чтобы получились все возможные различные наборы букв?

В заданном слове содержится пять букв, причем буквы «к» и «а» повторяются по два раза, а буква «о» встречается один раз. Таким образом,

2. Размещения

Рассмотрим множество U, состоящее из п элементов.

Размещением из п элементов по к называется упорядоченное подмножество, состоящее из к элементов, выбранное из множества п элементов и расположенное в определенном порядке. Число размещений из п элементов по к элементов обозначается А% и читается «А из п по к».

Пример 5.27.

Примеры задач, приводящих к необходимости подсчета числа размещений:

• 1) сколькими способами можно выбрать из 15 юристов пять кандидатов и назначить их на пять различных должностей в системе юриспруденции;
• 2) сколькими способами можно из 20 книг по юриспруденции отобрать 12 и расставить их в ряд на полке? ?

В задачах о размещениях полагается к < п. В случае если к = п, то легко получить = Р_п =п.

Для подсчета Afr используем тот же метод, что использовался для подсчета Р_п, только здесь берется к ячеек.

Первую ячейку можно заполнить п способами, вторую, при заполненной первой, можно заполнить (п -1) способами. Можно продолжать этот процесс до заполнения последней fc-й ячейки.

Эту ячейку при заполненных первых (к — 1) ячейках можно заполнить [п-(к — 1)] способами (или (п — к + 1)). Таким образом, все к ячеек заполняются числом способов, равным.

Получаем.

Сколько существует различных вариантов выбора четырех кандидатур из девяти специалистов для поездки в четыре различные страны?

Решение. Имеем

Пример 5.29.

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

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

Решение.

Любое число можно записать с использованием 10 цифр — 0, 1, …, 9. В предположении, что номер телефона преступника не начинаются с нуля (обычно это так), задача состоит в вычислении числа комбинаций из девяти различных цифр по 7.

Очевидно, что это — размещение по семи различным местам семи из девяти различных цифр, т. е.

Предположим, что если на проверку одного телефонного номера тратить 1 мин, то на проверку всех номеров будет затрачено 3024 ч или 126 сут. Таким образом, следователь поторопился с докладом. ?

Пример 5.30.

Преступник пытается подобрать шифр к сейфу и надеется, что на это хватит 30 мин. Получится ли это у него, если шифр состоит из трех цифр, и комбинации, составленные из цифр 0,1,2, 3,…, 8, 9, различаются только расположением цифр или самими цифрами?

Решение.

Найдем размещения.

Если предположить, что на подбор одной комбинации будет уходить 5 с, то на подбор 720 комбинаций уйдет.

Следовательно, преступнику может не хватить 30 мин, чтобы подобрать шифр и открыть сейф. ?

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

3. Сочетания

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

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

Общее число сочетаний из п по к обозначается С*.

Выведем формулу для подсчета числа сочетаний.

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

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

Следовательно, при одних и тех же значениях пик число сочетаний в к меньше числа размещений, т. е.

Задачи на подсчет числа подмножеств конечного множества называются комбинаторными.

Пример 5.31.

Сколькими способами из 10 кандидатов можно выбрать:

• а) председателя, зам. председателя и секретаря?
• б) трех делегатов на конференцию?

Решение. В обоих случаях мы выбираем из множества 10 элементов три элемента, т. е. п = 10, к = 3, но в случае а) располагаем их на определенных местах, т. е. на указанных должностях.

В случае б) порядок их расположения ни на что не влияет, так как статус делегатов одинаков. Поэтому.

Пример 5.32.

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

Сколько всего календарных игр?

Решение. Данная задача — о числе выборок из 16 по 2. Таким образом,.

Сколькими способами можно выбрать двух дежурных по следственному изолятору из 27 оперативных работников?

Решение.

Пример 5.34.

1. Из семи заводов организация должна выбрать три для размещения трех различных заказов.

Сколькими способами можно разместить заказы?

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

2. Если из текста задачи 1 убрать условие различия трех заказов, сохранив все остальные условия, получим другую задачу.

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

3. Имеется семь заводов.

Сколькими способами организация может разместить на них три различных производственных заказа? (Заказ нельзя дробить, т. е. распределять его на несколько заводов.).

Решение. В отличие от условия первой задачи здесь организация может отдать все три заказа первому заводу или, например, отдать два заказа второму заводу, а один — седьмому.

Задача решается так. Первый заказ может быть размещен семью различными способами (на первом заводе, на втором и т. д.).

Разместив первый заказ, имеем семь вариантов размещения второго (иначе, каждый способ размещения первого заказа может сопровождаться семью способами размещения второго).

Таким образом, существует 7 • 7 = 49 способов размещения первых двух заказов. Разместив их каким-либо образом, можем найти семь вариантов размещения третьего (иначе, каждый способ размещения первых двух заказов может сопровождаться семью различными способами распределения третьего заказа).

Следовательно, существует 49 • 7 = 7^{3 4} способов размещения трех заказов. Если бы заказов было п, то получилось бы 7^п способов размещения.

4. Добавим к условию задачи 1 одну фразу: организация также должна распределить три различных заказа на изготовление деревянных перекрытий среди четырех лесопилок. Сколькими способами могут быть распределены все заказы?

Решение. Каждый из Aj способов распределения заказов на заводах может сопровождаться А| способами размещения заказов на лесопилках.

Общее число возможных способов размещения всех заказов будет равно.

Пример 5.35.

_{v D} 7!4!f 8! 9!).

Упростить выражение В =——.

^v 10! 3!6! 2!7!)

Решение. Было бы неправильным просто вычислить все факториалы, после чего перейти к арифметике — слишком большие числа. Используем, где возможно, расчленение факториалов:

1 48.

Следовательно, В =—(84−366) = — = 1,6. ?

_ 30 30.

Пример 5.36.

.. 5! (т + 1)!

Упростить выражение А ——.

m (m +1) Cm — 1)!-3!

ml

Решение. Напомним, что (m +1)! = т!• (т +1);(т-1)! = — и 5! = 3! • 4 • 5, тогда.

т

Пример 5.37.

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

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

• 1) событие А — заказаны книги из различных разделов;
• 2) событие В — заказаны книги из одного и того же раздела.

Решение.

Число всех равновероятных исходов равно числу сочетаний с повторениями из 16 разделов по четырем заказам:

Число исходов, благоприятных событию А, равно числу способов отобрать без возращения четыре заказа из 16 разделов:

Число исходов, благоприятных событию В, равно числу способов выбрать один раздел из 16, поэтому