1. Правила равенства, суммы и произведения
Очень многие комбинаторные задачи решаются применением трех простых правил, названных в заголовке.
Пусть A и B - конечные множества, f - функция, определенная на A со значениями в B. Напомним, что f называется биекцией или взаимно однозначным отображением, если выполняются условия
1) любые два различных элемента из A отображаются в различные элементы множества B (функция, удовлетворяющая этому условию, называется инъекцией);
2) для любого yB существует такой ,что (такая функция называется сюръекцией).
Если существует биекция из A в B , то говорят также, что между A и B имеется взаимно однозначное соответствие.
Правило равенства. Если между конечными множествами A и B есть взаимно однозначное соответствие, то .
Правило суммы. Если A и B – конечные множества и , то .
Правило произведения. Для любых конечных множеств A и B имеет место равенство .
Первые два правила очевидны, третье следует из того, что при каждый элемент множества A образует b пар с различными элементами множества B, поэтому, если , то всего будет пар.
Правила суммы и произведения обобщаются на случай любого числа слагаемых или сомножителей. Для правила суммы обобщение очевидно: мощность объединения любого числа попарно непересекающихся множеств равна сумме их мощностей. Докажем обобщенное правило произведения.
Теорема 1. Для любых конечных множеств имеет место равенство .
Д о к а з а т е л ь с т в о. Мы видели, что при k = 2 это справедливо. Для большего числа сомножителей доказываем индукцией по k. Элементами множества являются наборы вида , где , . Каждый такой набор можно рассматривать как состоящий из двух частей: и . Первая часть – элемент множества , вторая – элемент множества . Таким образом, имеется взаимно однозначное соответствие между множеством и прямым произведением двух множеств: и . По правилу равенства , по правилу произведения для двух сомножителей , а по предположению индукции .
Применяя теорему 1 и правило равенства, докажем формулу для числа подмножеств конечного множества.
Теорема 2. Для любого конечного множества A имеет место равенство .
Д о к а з а т е л ь с т в о. Пусть . Каждому подмножеству X множества A поставим в соответствие двоичный набор , где , если , , если . Этот набор называют характеристическим вектором множества X. Очевидно, что по характеристическому вектору множество X можно определить однозначно. Следовательно, имеет место взаимно однозначное соответствие между и . Из правила равенства и теоремы 1 следует, что .
В теореме 1 речь идет о числе способов выбрать упорядоченный набор , где каждый элемент выбирается из множества независимо от всех остальных элементов. Иногда множество, из которого выбирается , зависит от того, какие элементы были выбраны в качестве , но число элементов в этом множестве, т.е. число вариантов для выбора , остается постоянным. В этом случае правило произведения также применимо, но в более общей формулировке.
Общее правило произведения. Пусть упорядоченный набор формируется в результате последовательного выбора элементов , причем для любого и любых элемент можно выбрать способами. Тогда весь набор может быть выбран способами.
Задачи
1. Имеется разных книг одного автора, – второго и – третьего. Каким числом способов можно выбрать
а) одну книгу?
б) две книги разных авторов?
в) три книги разных авторов?
2. Каким числом способов можно заполнить анкету, содержащую n вопросов, если на каждый вопрос можно ответить
а) “да” или “нет”?
б) “да”, “нет”, “не знаю”?
3. Сколько слов длины n можно составить, если в алфавите q букв? Сколько среди них палиндромов (слов, читающихся одинаково слева направо и справа налево)?
4. Сколько матриц с m строками и n столбцами можно составить из элементов 0 и 1 ?
5. Сколько слов длины n в q–буквенном алфавите, в которых любые две соседние буквы различны?
6. Каким числом способов можно на обычной шахматной доске разместить белую и черную ладьи так, чтобы они не атаковали друг друга?
7. Сколько бинарных отношений можно определить на множестве из n элементов? Сколько среди них
а) рефлексивных?
б) симметричных?
в) антисимметричных?