КОМБИНАТОРИКА ЧИСЛА И КОНФИГУРАЦИИ

2.1. Правило суммы

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

Рассмотрим  следующую задачу.

Задача 2.1.1. В студенческом буфете на одном подносе стоит 24 стакана чая, а на другом – 18 стаканов сока. Сколькими способами можно выбрать стакан чая либо стакан сока?

Задача решается просто. Стакан чая можно выбрать 24 способами, а стакан сока – 18 способами. Следовательно, стакан чая либо стакан сока можно выбрать 24 + 18 = 42 способами.

Пусть  – n-множество (конечное множество, состоящее из n элементов), условимся обозначать это следующим образом: . Тогда правило суммы можно записать так:

Если  и  – конечные непересекающиеся множества такие, что , , то .

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

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

Иными словами, если  – конечные непересекающиеся множества, т.е.  при , то

.[10]

2.2. Правило произведения

Рассмотрим следующие задачи.

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

Задача 2.2.2. Сколько трехзначных чисел начинаются с цифр 4 или 5?

Первая задача решается просто. Стакан чая можно выбрать 24 способами, а стакан сока – 18 способами. Следовательно, стакан чая либо стакан сока можно выбрать 24 + 18 = 42 способами.

Во второй задаче обозначим конверты буквами , , ,
а марки цифрами – 1, 2. Рассмотрим множества , и . Выпишем все возможные пары , в которых  и :

, , , , , .

Очевидно, каждой такой упорядоченной паре  соответствует способ выбора конверта с маркой, т.е. существует 6 способов выбора.

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

Другими словами, декартово произведение  состоит из  элементов.

Действительно, обозначим через , , , ...,  элементы множества , через , , , ...,  элементы множества. Выпишем все возможные пары , где  и :

, , ..., ,

, ,  ..., ,

................................…………..

, ,  ..., .

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

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

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

Правило произведения также допускает обобщение. Рассмотрим три следующие задачи.

Задача 2.2.3. В трёх группах курса 23, 24 и 25 студентов. Сколькими способами можно выбрать трёх представителей курса по одному из каждой группы?

Решение. Выбор представителя  от первой группы можно сделать 23 способами. Для каждого представителя  существует 24 способа выбора представителя  второй группы. По правилу произведения число таких пар  представителей равно . Наконец, после выбора двух представителей из первых двух групп представителя  из третьей группы можно выбрать 25 способом. Поэтому по правилу произведения тройку  представителей курса можно выбрать  способами.

Задача 2.2.4. Сколько четырёхзначных чисел можно записать с помощью цифр 1, 2, 3?

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

Задача 2.2.5. Имеется девять карточек, на которых написаны цифры от 1 до 9. Сколько четырёхзначных чисел можно составить с помощью этих карточек?

Решение. В качестве первой цифры числа можно взять любую из цифр 1, …, 9, т.е. она может быть выбрана 9 способами. После этого для выбора второй цифры остается 8 возможностей (одна цифра уже использована). Значит, теперь первые две цифры числа можно выбрать  способами. Третья цифра числа может быть выбрана 7 способами, а после этого последняя, четвертая, – 6 способами. Следовательно, число способов, которыми с помощью имеющихся карточек можно составить четырехзначное число, равно .

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

Теорема 2.2.1. (обобщенное правило произведения). Если элемент  может быть выбран  способами, после этого элемент  может быть выбран  способами, а для любого  после выбора элементов  элемент  может быть выбран  способами, то выбор упорядоченной последовательности  из m элементов может быть осуществлён  способами.

Доказательство. Воспользуемся методом математической индукции.

 Для , т.е. для упорядоченных пар элементов, утверждение справедливо.

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

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

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

Таким образом, утверждение теоремы справедливо для , а из предположения его справедливости для  следует справедливость для . Значит, теорема имеет место для любого натурального . [10]

Скачано с www.znanio.ru