Дискретная математика (стр. 9 )

f Y f : Х Y.

Множество Y называют множеством степень.

Для множества степень справедливо следующее утверждение:

Теорема. Пусть Х и Y – конечные непустые множества. Тогда Y– конечное множество, и его размерность равна

| Y| = | Y |.

Пример. В НИИ работают 4 курьера – А, В, С, D. Сколько существует способов разослать 7 писем в 7 различных организаций, если доставка осуществляется только указанными курьерами?

Решение

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

|К| = |К| = 4= 16 384.

2.5 Правило суммы

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

Теорема (правило суммы). Пусть А, А, …, А – конечные непересекающиеся множества (т. е. А А = Ø, при i j). Тогда

|А А,…,А| = |А| + |А| + … + |А|.

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

Решение. Выбор одной девочки из десятых классов (или гуманитарного, или экономического, или естественнонаучного) можно сделать 32 способами, так как объединение множеств девочек во всех трех классах содержит 32 элемента. Действительно, в гуманитарном классе – 14 девочек, в экономическом – 12, а в естественнонаучном – 6 девочек. Получаем: 14 + 12 + 6 = 32.

Ответ. 32.

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

Теорема (правило включения-исключения). Пусть А, А, …, А – конечные множества. Тогда

|А А…А| = (|А| + |А| + … + |А|) – (|АА| + |АА| + …

+ |АА|) + … + (–1) |АА…А| = – + …+ (–1) |АА…А|.

Пример. В классе 30 учеников. Известно, что 18 ребят имеют спортивный разряд по лыжам, а 16 – по плаванию. Десять (10) учеников не имеют разряда ни по плаванию, ни по лыжам. Сколько ребят имеют спортивный разряд и по плаванию, и по лыжам?

Решение. Пусть А – множество учеников, имеющих разряд по лыжам, а В – множество учеников, имеющих разряд по плаванию. Тогда в силу условия задачи |А| = 18, |В| = 16, а |АВ| = 30 – 10 = 20. Применив правило включения-исключения, получаем:

|АВ| = |А| + |В| – |АВ| = 18 + 16 – 20 = 14.

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

Ответ: 14.

3 КОМБИНАТОРИКА

3.1 Историческая справка. Виды выборок: с возвращением

и без возвращения, упорядоченные и неупорядоченные

Комбинаторными задачами принято называть задачи, в которых требуется выяснить, сколько различных комбинаций, удовлетворяющих тем или иным условиям, можно составить из заданных объектов (или, говорят еще, из элементов данного множества). Раздел математики, в котором изучаются методы решения комбинаторных задач, называется комбинаторикой (от латинского combinare – соединять, сочетать). Основным вопросом, на который дает ответ комбинаторика, является вопрос «сколько?» в различных вариантах. При этом основной способ ответа на данный вопрос – это установление взаимно однозначного соответствия между множеством в котором предстоит подсчитать количество элементов (т. е. ответить на вопрос «сколько?»), и множеством, в котором количество элементов известно. Этот принцип подсчета – основной принцип комбинаторики – весьма наглядно может быть проиллюстрирован следующей цитатой из переводов английской детской поэзии: