Материал: baldin_kv_red_matematika_dlia_gumanitariev
ментов, поэтому ребра будут ориентированными (обозначим их стрелками). В результате получим следующий граф (рис. 1.9).
1 |
2 |
|
|
|
|
|
4 |
||
|
|
|
||
|
|
|
|
|
|
7 |
|
|
5 |
|
|
|
|
8 |
|
6 |
|
|
|
|
|
10 |
|
9 |
|
|
|
|
Рис. 1.9
В случае х1 = х2 получим петлю.
Наконец бинарное отношение можно представить в виде матрицы, т. е. прямоугольной таблицы размера n m, где n — количество строк, а m — количество столбцов. Например, если
имеем два множества Х = {х1, х2, …, хn}, Y = {у1, у2, …, уm} и бинарное отношение на элементах этих множеств # Х Y = = {(ху) |
х[Х, у[Y}, то этому отношению соответствует матрица размера n m, состоящая из нулей и единиц. Единицами обозначаются пары (ху), входящие в отношение . (Более подробно о матрицах см. в главе 2 “Элементы линейной и векторной алгебры”.)
В данном примере имеем отношение # Х2, т. е. ему соответствует матрица размера 10 10, число строк и столбцов которой равно числу элементов в множестве Х (рис. 1.10).
|
1 |
2 |
|
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
2 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
4 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
26
|
1 |
2 |
|
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
|
|
|
|
|
|
|
|
|
8 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Рис. 1.10
В заключение рассмотрим функцию как отношение. Отношение f между элементами множеств Х и Y называ-
ется функцией, определенной на множестве Х и принимающей значение на множестве Y, если
;х[Х '! у[Х | (х,у)[f. |
(1.1) |
В этом случае пишут f: Х У, а вместо (х,у)[f обычно пишется у = f(х); у называют значением функции f на элементе х, так как для функциональных отношений в силу (1.1) f-образная одноэлементного множества {х} будет одноэлементное множес-
тво {f(х)}.
Заметим, что (1.1) эквивалентно выполнению двух условий:
f -1(У) = Х; |
(1.2) |
у1 = f(х) и у2 = f(х) у1 = у2. |
(1. ) |
Иногда отношения называют функцией, если выполнено только условие (1. ), а если выполнено и условие (1.2), то отоб-
ражением.
Часто слова функция и отображения используют как синонимы [18].
1.2.Основныепонятиякомбинаторики
Комбинаторика — часть математики, которая посвящена решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами, т. е. комбинаторика решает задачи выбора элементов из конечного множества и размещения этих элементов в каком-либо по-
рядке. [7, 8, 27].
27
Приведем правила сложения и умножения, которые применяются в комбинаторике. [7].
Правило сложения. Если выбор каждого из объектов Аi (
) можно сделать ni способами, то выбор или А1 или А2, …,
или Аk можно произвести |
способами. |
Правило умножения. Если выбор каждого из k объектов Вi (
) можно сделать mi способами, то выбор и В1, и В2, …, и Вk
можно осуществить |
способами. |
Приведем конкретные примеры применения этих правил. Пример1.4.Из Москвы в Санкт-Петербург можно добраться самолетом, поездом, автобусом. Есть пять автобусных мар-
шрутов, два авиамаршрута, один железнодорожный. Поэтому общее число маршрутов между Москвой и Санкт-Петербургом равно: n = 5 + 2 + 1 = 8
Пример 1.5. Из пункта А в пункт В можно доехать по 5 дорогам, из В в С — по трем дорогам, а из С в D — по четырем дорогам (рис. 1.11). Сколькими способами можно проехать из А в D через В и С?
A B C D
Рис. 1.11
По правилу произведения получаем N = 5 · · 4 = 60.
Размещения
Дано множество, состоящее из n элементов. Размещением из n элементов по m элементам (0 # m # n) называется любое упорядоченное подмножество, содержащее m различных элементов исходного множества. Все эти подмножества отличаются друг от друга или составом элементов, или порядком их распределения. [7, 8, 27].
28
Обозначим размещения из n элементов по m
где n! = 1 2 … n (читается n факториал). Принимается, что 0! = 1 и 
Пример 1.6. В футбольной премьер-лиге РФ участвует
16 команд. Сколькими способами можно распределить три первых призовых места?
Так как в данном случае порядок команд имеет значение, то имеем дело с размещениями, т. е.
Число размещений по m элементов с повторениями из n элементов равно nm, т. е.
Пример 1.7. Сколько трехзначных чисел можно составить из цифр 5,6,7,8. 
трехзначных числа.
Перестановки
Перестановкой из n элементов называется размещение из n элементов по n элементов [7, 8]. Так как каждая перестановка содержит все n элементов исходного множества, то различные перестановки отличаются друг от друга только порядком следования элементов, т. е.
Пример 1.8. Расставить четыре книги на полки можно P4 = = 1 2 4 = 24 способами.
Если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида, …, ni элементов i-го вида, то число перестановок с повторениями находится по формуле
29
Пример1.9.Сколько различных шестизначных чисел можно записать с помощью цифр: 2, 2, , , 4, 4. В данном случае n = 6, n1 = 2, n2 = 2, n = 2, т. е.
Сочетания
Дано множество, состоящее из n элементов. Сочетанием из n элементов по m элементам (0 # m # n) называется любое подмножество, которое содержит m различных элементов исходного множества. Различными подмножествами считаются только те, которые отличаются по составу элементов. [8, 27].
Обозначив число сочетаний через 
получим
Пример 1.10. В бригаде 25 человек. Надо найти четырех человек для работы в ночную смену. Сколькими способами это можно сделать.
Так как порядок выбранных четырех рабочих не имеет значения, то имеем
Число сочетаний с повторениями из n элементов по m находятся по формуле
Пример 1.11. Число различных бросаний трех одинаковых кубиков равно
0