Комбинаторика

Общие правила комбинаторики

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

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

Число таких задач, безусловно, легко умножить.

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

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

Одним из первых, кто занялся подсчетом числа различных комбинаций при игре в кости, был итальянский математик Тарта-лья. Теоретическое исследование вопросов комбинаторики в XVII веке предприняли французские математики Б. Паскаль и П. Ферма. Дальнейшее развитие комбинаторики связано с именами широко известных математиков: Я. Бернулли, Г. Лейбница, Л. Эйлера. В настоящее время интерес к комбинаторике обусловлен тем, что многие проблемы техники, экономики, науки формулируются как комбинаторные задачи, в которых требуется найти комбинацию, доставляющую наилучшее значение некоторой функции или функционалу.

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

Рассмотрим правило суммы.

Когда все изучаемые комбинации можно разбить на несколько классов так, что каждая входит в один и только один класс, то общее число комбинаций равно сумме комбинаций всех классов. Иными словами, если некоторый объект А можно выбрать т способами, а другой объект В — п способами, то существует т + п способов выбора. Это и есть правило суммы. Например, пусть из города А в город В отправляются 10 поездов, 5 самолетов и 3 автобуса. Сколькими способами одному человеку можно добраться т А в В?

В этой задаче классы комбинаций составлют поезда, самолеты и автобусы. Если в качестве передвижения выбирается, например, самолет, то поезда и автобусы исключаются. Поэтому по правилу суммы число способов переезда из А в В равно 10 + 5 + 3=18.

При использовании правила суммы необходимо следить за тем, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В, т. е. чтобы ни одна комбинация не попадала сразу в два класса. Если такие совпадения есть и их число к, то число способов выбора А или В будет равно п + т- к.

Пусть из пункта А через пункт В необходимо проехать в пункт С. Из А в В ведут четыре дороги, а из В в С — две дороги. Требуется найти все способы проезда из пункта А в пункт С и выбрать лучший из них.

Очевидно, что для каждой дороги из А в В существует две дороги из В в С. Поэтому число способов проезда из пункта А в пункт С будет равно 4-2 = 8. Выбор лучшего варианта осуществляется путем сравнения стоимости, времен или других важных характеристик способов проезда между собой.

Известно, что наименьшей расчетной единицей памяти современных ЭВМ является байт, состоящий из восьми бит, образно говоря — из восьми ячеек, в каждую из которых может быть помещена единица или нуль. Набор единиц и нулей, помещенный в байт, называется двоичной конфигурацией (комбинацией). Возможная двоичная комбинация, помещенная в байт, приведена на рис. 3.1.

Рис. 3.1. Двоичная комбинация байта

Требуется найти, сколько различных двоичных комбинаций может содержать один байт памяти ЭВМ.

Эта задача решается так же, как и предыдущая. Любой бит памяти может содержать либо нуль, либо единицу. Поэтому для первого бита имеем две комбинации, для первого и второго получим 2-2 = 4 комбинации. Для очередного, третьего, будем иметь 2-2 -2 = 8 комбинаций. И, наконец, для последнего, восьмого бита число комбинаций будет равно 2-2-2-2-2-2-2-2 = 256 = 2⁸. Поэтому часто говорят, что в байте может храниться 256 различных двоичных чисел. Приведенные две задачи были решены с использованием правила произведения. Оно формулируется следующим образом.

Если требуется выполнить одно за другим к действий (сделать к выборов или принять к решений) и первое действие может быть выполнено п_] способами, второе действие — п₂ способами, а к-е действие п_к способами, то все к действий могут быть выполнены п_х п₂-... п_к способами.

Действительно, в первой задаче о переезде из пункта Л в пункт С первое действие включало четыре варианта выбора дороги из Л в В, а второе действие — два варианта выбора дороги из В в С. Поэтому п_х п₂ = 4-2 = 8. Во второй задаче каждый бит байта хранит единицу или нуль, т.е. имелось две возможности хранения. Поскольку всего в байте восемь бит, то число двоичных комбинаций п₁-п₂-п₃-п₄-п₅-п₆-п₁-п_і=2-2-2-2-2-2-2-2 = 256.

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

Рассмотрим следующую задачу. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали среди восьми профессиональных команд на первенстве мира по хоккею. Очевидно, что любая из восьми команд может получить золотые медали. Поэтому /7, = 8. Серебряные и бронзовые медали может получить одна из оставшихся семи команд. Поэтому п₂ = 7, а способов распределения золотых и серебряных медалей л, •п₂ = = 56. Бронзовые медали может получить одна из оставшихся шести команд. Поэтому п₃ - 6.

Таким образом, всего способов распределения медалей ^п '^п2 '^пг ~ 56-6 = 336.

Аналогичным способом решается следующая задача. Сколько четырехзначных чисел можно составить из цифр 0, 1,2, 3, 4, 5, если:

• а) ни одна из цифр в этих числах не повторяется;
• б) цифры в числах могут повторяться;
• в) числа должны быть нечетными, а цифры в них могут повторяться?

Для пункта а) первой цифрой числа может быть одна из пяти цифр: 1, 2, 3, 4, 5, кроме 0, так как при использовании нуля число не будет четырехзначным. Поэтому л, = 5. Если первая цифра выбрана, то вторая может быть выбрана из пяти цифр (используется нуль). Поэтому п₂ = 5. Третья цифра может быть выбрана из четырех цифр, т. е. /7₃ = 4, а четвертая — из трех цифр, т. е. п₃ -4.

Таким образом, всего может быть составлено п_х ?п₂ -п₃ ?п₄ = - 5-5-4-3 = 300 чисел.

Для пункта б) первой цифрой может быть одна из пяти цифр: 1, 2, 3, 4, 5, т. е. я, = 5. Второй цифрой — одна из шести цифр: 0, 1,2, 3, 4, 5. Таким образом, п₂ = 6. Третьей и четвертой цифрой числа может быть также одна из шести цифр: 0, 1,2, 3, 4, 5. Поэтому п₃ - 6 и п₄ - 6. Откуда все количество чисел Пу п₂ •п₃ -п₄ = 5-6-6-6 = 1080.

Для пункта в) первой цифрой числа может быть одна из пяти цифр 1, 2, 3, 4, 5, т. е. п_х - 5, а последней цифрой числа — одна из цифр 1, 3, 5, так как числа должны быть нечетными. Поэтому п_х п₂ •«з •п₄ = 5-6-6-3 = 540.

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

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

На место командира имеется четыре претендента: а_х, а₂, а₃, а₄. На места бортинженера и врача есть по три претендента: Ь_{, Ь₂, Ь₃ и Су, с₂, с₃. Известно также, что командир а у психологически совместим с инженерами Ь_х и Ь₃ и врачами с₂, и с₃, командир а₂ — с инженерами: Ь_х и Ь₂ и всеми врачами, командир а₃ — с инженерами Ъу и Ь₂ и врачами с,, с₃, командир а₄ — со всеми инженерами и врачом с₂. Кроме того, установлено, что инженер Ъ_х психологически несовместим с врачом с₃, инженер Ь₂ — с врачом с,, инженер Ь₃ — с врачом с₂.

Так как при назначении командира корабля имеется выбор из четырех кандидатов, от корня дерева (рис. 3.2) проведем четыре ветви, обозначенные соответственно а у, а₂, а₃, а₄. В результате получим одноярусное поддерево с четырьмя вершинами, каждая из которых фиксирует выбор соответствующего претендента (командира корабля).

Корень Ярус

Построение вершин второго яруса дерева следует проводить с учетом психологической совместимости командира корабля с бортинженерами. В результате на втором ярусе поддерева получим десять вершин, в частности, вершина я₄ порождает ветви: Ь_х, Ь₂, Ь₃. Последний ярус вершин дерева (листьев) строится с учетом психологической совместимости командира корабля, бортинженера и врача.

Так как командир я, не совместим с врачом с,, а бортинженер с врачом с₃, то ветвь я, Ь_х заканчивается вершиной с₂, а ветвь я, Ь₃ в виду несовместимости бортинженера Ь₃ с врачом с₂ — вершиной с₃.

Аналогичным образом составляются ветви а₂Ь_хс_х, а₂Ь_хс₃, а₂Ь₂с₂, а₂Ь_хс₃, а₃Ь_хс_х, а₃Ь₂с₂. Что касается ветвей, исходящих из вершины я₄, то ветвь я₄ Ь₂ должна быть отброшена в виду того, что бортинженер Ь₃ не совместим с врачом с₂, а командир корабля совместим только с этим врачом. В результате получаем дерево с десятью комбинациями, используя которое легко выбрать тот или иной экипаж корабля. Заметим, что если бы не было ограничений на психологическую совместимость, число комбинаций можно было бы найти по правилу произведения п = п_х -п₂ п₃ = = 4-3-3 = 36.

Метод включения и исключения основан на использовании формулы для подсчета числа элементов объединения (суммы) множеств (гл. 1, п. 1.1). Рассмотрим такой пример. В некотором научно-исследовательском институте работают 67 сотрудников, 47 из которых владеют английским языком, 35 — немецким, а 23 сотрудника знают тот и другой язык. Требуется установить, сколько сотрудников института не владеют ни одним из указанных иностранных языков?

Пусть А и В — множества сотрудников, владеющих соответственно английским и немецким языком. Тогда число сотрудников института, владеющих языками, на основании формулы суммы определится так: А[] В = А +1 В - |ЛП В| = 47 + 35 - 23 = 59. Откуда число сотрудников, не владеющих языками, равно 67 - 59 = 8.

Аналогичным образом может быть решена следующая задача. Из ста студентов некоторого университета английский язык знают 28 студентов, немецкий — 30 студентов, французский — 42 студента. Кроме этого, английский и немецкий языки знают 8 студентов, английский и французский — 10 студентов, немецкий и французский — 5 студентов, а все три языка знают 3 студента. Требуется определить, сколько студентов университета не знают ни одного языка.

Пусть А, В, С — множества студентов, знающих соответственно английский, немецкий и французский языки. Тогда АГВ — множество студентов, знающих английский и немецкий языки, АГС — множество студентов, знающих английский и французский языки, В ПС — множество студентов, знающих немецкий и французский языки, а АРВРС — множество студентов, знающих все три языка. На основании формулы суммы получаем количество студентов, владеющих иностранными языками:

AJBUC = А + В + С-АПВ-АС)С-ВГС + АГВГС =

= 28 + 30 + 42 - 8 - 10 - 5 + 3 = 80.

Таким образом, не владеют ни одним из иностранных языков 100 - 80 = 20 студентов.