Вопросы для самоконтроля

1. Что называется графом? Примеры.

2. Какой граф является связным?

3. Дерево исходов.

4. Эйлеровы графы, необходимые и достаточные условия.

5. Примеры Гамильтоновых графов.

6. Ориентированные графы.

7. Вероятностные графы и порядок их построения.

8. Приведите примеры вероятностных деревьев.

3. Принцип сложения и принцип умножения

Пример 3.1. Из пункта Х в пункт У можно доехать либо автобусом (5 рейсов), либо самолетом (3 рейса). Тогда из пункта Х в пункт У можно доехать 5 + 3 = 8 различными способами.

Пусть множество А={a₁,a₂...a_n} состоит из m элементов, а множество B={b₁,b₂,...b_n} состоит из n элементов, причем ни один из элементов множества А не совпадает ни c одним элементом множества В.

Выбрать один элемент из множества А можно m различными способами, один элемент из множества B можно выбрать n различными способами.

Один элемент из множества A или множества B можно выбрать m + n различными способами.

Это утверждение составляет содержание так называемого принципа сложения.

Рассмотрим теперь множество C, элементами которого являются всевозможные пары (a_i ;b_j), где a_i A, bj B

C={(a₁,b₂ ), (a₁,b₂)….(a₁,b_n),

(a₂,b₁, ), (a₂,b₂)….(a₂,b_n),

……………………………

(a_m,b₁), (a_m,b₂), … (a_m,b_n)}.

Множество С состоит из (m n) элементов. Это утверждение называется принципом умножения.

Принципу умножения можно придать другую форму. Пусть множество A состоит из m подмножеств A₁, A₂……A_m , не имеющих общих элементов, каждое из подмножеств A_i состоит из n элементов a_i1, a_i2, … a_in.

Тогда справедливо утверждение: множество А состоит из (m n) элементов.

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

Принцип умножения может быть проиллюстрирован следующим образом. Пусть необходимо выполнить одно за другим какие-то К действий. Если известно, что первое действие можно выполнить n₁ способами, после чего второе действие можно выполнить n₂ способами, после чего третье действие можно выполнить n₃ способами. и так далее до К -го действия, которое можно выполнить n_k способами, тогда все К действий вместе могут быть выполнены n₁ n₂ n₃ … n_k способами.

Построим “дерево”, иллюстрирующее принцип умножения для n₁=2 , n₂=3 , n₃=2. Общее число путей вдоль ветвей дерева от начала к его правой крайней вершине равно n ₁n₂ n₃=2 3 2=12.

Заметим, что принцип умножения учитывает порядок объектов в перестановках.

Рис.6

Пример 3.2. Номер автомобиля состоит из двух букв, за которыми следует трехзначное число. Сколько существует различных автомобильных номеров?

Решение. Мы можем считать, что номер автомобиля состоит из пяти мест, на первые два из которых надо поставить буквы, а на остальные – цифры. Первое место можно заполнить любой из 28 букв алфавита (ё, й, ь, ъ не входят), то есть 28 способами. После этого мы снова 28 способами можем заполнить второе место (повторения букв разрешается). Аналогично третье место можно заполнить 10 способами, четвертое – 10 способами и пятое – 10 способами. Используя принцип умножения, получаем ответ

n=28 28 10 10 10=784000.

4. Размещения, перестановки и сочетания

без повторений

Конечное множество, состоящее из n элементов, называется упорядоченным, если его элементы каким либо образом занумерованы числами 1, 2, 3, …n.

Элементы упорядоченного множества расположены в определенном порядке. Одно и то же множество можно упорядочить различными способами. Например, множество студентов группы можно упорядочить по росту, по весу, по алфавиту фамилии и так далее.

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

Определение 1. Пусть дано конечное множество М, состоящее из n элементов. Размещением из n элементов по m элементов называется всякое упорядоченное подмножество множества М, состоящее из m элементов.

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

Теорема 1. Число различных размещений из n элементов по m элементов вычисляется по формуле

A =n (n-1) (n-2)…(n-m+1). (1)

Доказательство. Число размещений из n элементов по 1 элементу, очевидно, равно n: A =n. Чтобы получить размещения из n элементов по 2 элемента, можно к каждому размещению по 1 элементу присоединить один элемент из оставшихся (n-1) элемента множества M . Таким образом, по каждому размещению по одному элементу можно построить (n-1) размещений по два элемента. По принципу умножения отсюда следует, что A = n (n - 1).

По каждому размещению по два элемента можно построить (n - 2) размещения по три элемента. Следовательно, A = n (n - 1) (n - 2).

Продолжая эти рассуждения, получим, что A = n (n - 1) (n - 2)…(n – m + 1)

Формулу (1) для вычисления числа размещений из n элементов по m элементов можно записать в виде

A = (2)

где n!=1 2 3…n - произведение всех натуральных чисел от 1 до n.

Замечание. 0!=1; 1!=1.

Пример 4.1. Сколькими способами можно составить трёхцветный флаг (три горизонтальных цветных полосы равной ширины), если имеется материал пяти различных цветов.

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

A =

Пример 4.2. Сколько различных натуральных чисел можно составить из цифр 0, 1 , 2 , 3 , 4 , если в каждое число входит каждая из данных цифр не более одного раза.

Решение. Очевидно, что однозначных натуральных чисел всего 4 . Это 1, 2, 3, 4. Составляя остальные числа мы должны учитывать, что числа не должны начинаться с 0 и что для чисел перестановка элементов в соединении меняет смысл самого соединения, например, из трех цифр 1 , 2 , 4 можно составить следующие числа; 124 , 142 , 214, 241, 412 , 421 . Учитывая сказанное, можно дать ответ: из цифр 1, 2, 3, 4 можно составить:

однозначных натуральных чисел – 4;

двухзначных – ;

трехзначных – ;

четырехзначных – ;

пятизначных – .

Определение 2. Перестановками из n элементов называются различные упорядочения данного множества M , состоящего из n элементов.

Так как само множество М является подмножеством множества М, то можно сказать, что перестановки из n элементов это размещения из n элементов по n элементов.

Различные перестановки из n элементов состоят из одних и тех же элементов и отличаются только порядком входящих в них элементов.

Число всевозможных перестановок из n элементов обозначается через Pn.

Полагая в формуле (1) m =n получим

(3)

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

Теорема 2. Число возможных перестановок из n элементов вычисляется по формуле

. (4)

Решение задачи о распределении обязанностей старосты, профгрупорга и кассира между тремя студентами (рассмотренной выше) можно записать по формуле

Точно также в задаче о количестве натуральных чисел, которые можно составить из цифр 0, 1, 2, 3, 4 , число всевозможных пятизначных натуральных чисел правильней посчитать по формуле

Пример 4.3. Сколько различных пятизначных чисел без повторения цифр можно составить из цифр 1, 2, 3, 4, 5 так, чтобы четные цифры не стояли рядом.

Ответ: n=5! - 2 4! =72

Выбрасываем число, перестановок из элементов 1, 24, 3, 5 и 1, 42, 3, 5.

Пример 4.4. Для культпохода куплено 2n билетов в театр на места, находящиеся в одном ряду партера (в ряде 2n мест). Сколькими способами можно распределить эти билеты между лицами данной группы, состоящей из n - мужчин и n-женщин, чтобы не сидели рядом двое мужчин или две женщину?

Решение. Занумеруем места ряда числами 1, 2, 3,...(2n-1), 2n. Предположим, что мужчины занимают места с нечетными номерами, тогда мужнин можно рассадить n₁=n! способами; точно так же на четных местах женщин можно рассадить n₂=n!, исходя из принципа умножения при исходном предположении, что мужчины занимают нечетные места, общее количество способов рассадить мужчин и женщин равно N₁ = n₁ n₂, то есть N₁ = n! n!

Но мужчины могут сидеть на четных местах, а женщины на нечетных, в этом случае количество вариантов рассадки равно N₂ = n! n! . А так как может выполняться или тот иди другой способ, то

N = N₁ + N₂ = 2 n! n!

Определение 3. Пусть дано конечное множество M , состоящее из n элементов. Сочетанием из n элементов по m элементов называется любое подмножество множества M , состоящее из m элементов.

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

Число различных сочетание из n элементов по m элементов обозначается .

Теорема 3. Число всех сочетании из n элементов по m элементов равно числу всех размещение из n элементов по m элементов, деленному на число всех перестановок m элементов

(5)

Доказательство. Рассмотрим множество А всевозможных размещений из n элементов по m элементов. Разобьем на непересекающиеся множества A_i, каждое из которых состоит из размещений, отличающихся друг от друга только порядком входящих в него элементов. Число таких подмножеств равно – числу сочетаний из n элементов по m элементов:

Число размещений, входящих в каждое из подмножеств A, равно P_m - числу перестановок из m элементов. По принципу умножения отсюда следует, что

Следовательно,

(6)

что и требовалось доказать.

Формулу (5) можно записать в виде

(7)

или

(8)

Отметим соотношение, которым часто приходится пользоваться при вычислениях:

(9)

Пример 4.5. Найти число сочетаний из n элементов по n элементов. По формуле (6)

Этот результат можно получить из формулы (7), если считать, что 0!=1:

До сих пор мы считали, что . Ради симметрии формулы (8) введём понятие сочетания из n элементов по 0 элементов. Тогда по формуле(8)

Этот результат можно понимать так, что число пустых подмножеств, содержащихся в множестве М, равно 1.

Размещения, перестановки, сочетания называются общим термином – соединения.

Пример 4.6. Сколькими способами можно выбрать три различные краски из имеющихся пяти.

Решение. Обозначим краски номерами 1, 2, 3, 4, 5 и перечислим все возможные исходы:

{(1, 2, 3); (1, 2, 4); (1, 2, 5); (1, 3, 4); (1, 3, 5); (1, 4, 5); (2, 3, 4); (2, 3, 5); (2, 4, 5); (3, 4, 5)}

Если проанализировать эти соединения, то видим, что друг от друга они отличаются, по крайней мере, одним элементом, при этом очевидно, что записать элемент ( 1, 2, 3 ) или ( 2, 3, 1) – это одно и тоже. По содержанию задачи ясно, что смысл соединения не меняется от перестановки элементов в нем. Выбрать белую, чёрную и красную краски или красную, белую и чёрную, очевидно, одно и тоже

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

Решение. Назовем преподавателей условно буквами А , В и С . Очевидно, кому из них приписать букву А и соответственно А и С безразлично. А может выбрать классы

способами, способами,

способами.

На каждый из 15 вариантов для А имеется 6 вариантов для В, то есть для А и В имеется 90 способов и на каждый из них 1 вариант для С: