Таким образом, обосновано следующее

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

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

3. Размещения с повторениями.Рассмотрим следующую комбинаторную задачу: найти число упорядоченных наборов, содержащих по необязательно различных элементов -множества . Такие наборы называют размещениями с повторениями из элементов по и их число обозначают через (от французского слова arrangement – размещение; черта сверху поставлена, чтобы различать размещения без повторений, которые будут рассматриваться позднее). Легко понять, что равно числу элементов в -ой декартовой степени множества , т.е. во множестве = , где берется декартовым множителем раз, т.е. = . По теореме 2 имеем = и поэтому справедливо равенство

= . (9)

Итак, доказана следующая

Т е о р е м а 3.Число размещений с повторениями из элементов по равно .

Пример 1.Найти число пятизначных телефонных номеров.

□ 1-й способ. Любое пятизначное число можно записать в виде = , где – цифры, причем первая из них не равна 0. В силу основного принципа комбинаторики искомое число есть .

2-й способ. Число записей вида равно числу размещений из 10 цифр по 5, т.е. = 10⁵ = 100 000. Но при этом подсчитаны и те, которые содержат на первом месте цифру 0. Таких размещений будет столько, сколько можно составить размещений из 10 цифр по 4 (на последние 4 места), т.е. = 10⁴ = 10 000. Искомое число равно .

Замечание 1. Этотпример показывает, что для миллионного города пятизначных номеров недостаточно.

4. Число отображений k-множества в m-множество.Размещение с повторениями из элементов по представляет собой упорядоченный набор , который определяет отображение k-множества в m-множество , при котором 1 отображается в , 2 – в и т. д., – в . Верно и обратное утверждение: любое отображение ‑множества в -множества определяет размещение с повторениями из элементов по , причем различные отображения определяют различные размещения. Таким образом, между отображениями ‑множества в m‑множество и размещениями с повторениями из m элементов по существует взаимно однозначное соответствие и поэтому справедлива следующая

Т е о р е м а 4.Число отображений k‑множества в m‑множество равно .

Полученный результат можно сформулировать и иным образом. Если считать элементы k-множества «предметами», а элементы m‑множества «ящиками», то при каждом отображении во множество происходит распределение предметов по ящикам (некоторые ящики могут при этом оказаться пустыми, поскольку в некоторые элементы множества не отображается ни один элемент множества ). Поскольку число отображений k‑множества в m‑множество равно , то справедливо следующее утверждение:

Принцип ящиков.Число распределений k различных предметов по различным ящикам (некоторые ящики могут оказаться пустыми) равно .

Замечание 2. Очевидно, что если , то при любом распределении k предметов по ящикам, по крайней мере, в одном ящике окажется два предмета. Это высказывание называют иногда принципом Дирихле в честь немецкого математика П.Г.Л.Дирихле (1805-1859), широко пользовавшимся этим утверждениям в своих исследованиях.

5. Число подмножеств конечного множества.Результаты предыдущих разделов позволяют решить следующую комбинаторную задачу: найти число всех подмножеств (включая пустое) данного -множества .В самом деле, возьмем два числа 0 и 1 (или, если угодно, два ящика). Каждому подмножеству множества соответствует отображение , при котором элементы из отображаются в 1, а все остальные – в 0. Таким образом, существует взаимно-однозначное отображение между подмножествами множества и отображениями этого множества в 2-множество . Но число таких отображений согласно теореме 4 равно . Значит справедлива

Т е о р е м а 5.Число всех подмножеств -множества равно .

Напомним, что через В( ) обозначается булеан множества , т.е. множество всех подмножеств множества . Учитывая это обозначение, теорему 5 можно записать в виде

Т е о р е м а . = .

Пример 2. Проиллюстрируем теорему 5 на примере 3-множества . Оно должно иметь = 8 подмножеств. Ими являются , , , , , , и .

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

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

Т е о р е м а 6 .

. (10)

Здесь алгебраическая сумма распространена на все комбинации свойств (без учета их порядка), причем знак + ставится, если число свойств четно, и знак –, если это число нечетно. Например, входит со знаком +, а – со знаком –. Формулу (10) называют формулой исключений и включений – сначала исключаются все предметы, обладающие хотя бы одним из свойств , потом включаются предметы, обладающие по крайней мере двумя из этих свойств, исключаются имеющие по крайней мере три и т.д. Доказательство формулы (10) проведем индукцией по числу свойств.

□ База индукции. При имеем , так как каждый предмет либо обладает свойством , либо не обладает им.

Шаг индукции. Предположим, что формула (10) справедлива для свойств:

. (11)

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

. (12)

Вычтем равенство (12) из равенства (11). Легко видеть, что после вычитания в правой части получим то, что нам нужно – правую часть равенства (10) при . А в левой части получим разность

. (13)

Но – это число предметов, не обладающих свойствами и, быть может, обладающих свойством . А – это число предметов, которые не обладают свойствами , но наверняка обладают свойством . Значит, разность (13) как раз равна числу предметов, не обладающих ни одним из свойств из свойств . Иными словами

.

Таким образом, после вычитания получим формулу (10) при :

.

Вывод. Формула (10) справедлива при любом натуральном .

Пример 3. В одной научной организации среди 123 работающих 106 знают английский язык, 84 – немецкий язык и 77 – оба языка. Сколько научных сотрудников не знают ни английского, ни немецкого языков?

□ Пусть обозначает свойство: «Научный сотрудник знает английский язык», а – свойство: «Научный сотрудник знает немецкий язык». Запишем формулу (10) для нашего случая :