- •Введение
- •1. Элементы теории множеств
- •1.1. Основные понятия и определения теории множеств
- •1.2. Операции над множествами и их свойства. Диаграммы Эйлера-Венна
- •1.3. Мощность множества
- •1.4. Взаимно однозначное соответствие между множествами
- •1.5. Счетные и несчетные множества
- •Задачи и упражнения
- •2. Элементы теории отношений
- •2.1. Бинарные отношения. Свойства отношений
- •2.2. Отношение эквивалентности и разбиения
- •2.3. Отношения порядка. Диаграмма Хассе
- •Задачи и упражнения
- •3.Функции, отображения и операции
- •4. Элементы теории графов
- •4.1. Основные понятия и определения теории графов
- •4.2. Типы графов
- •4.3. Матричные представления графов
- •4.5. Операции над графами
- •4.6. Метрические характеристики графа. Расстояние в графах
- •Затем, изымая степень, соответствующую вершине , получим
- •4.8. Достижимость и связность
- •4.8.1. Основные определения
- •4.8.2. Матрицы достижимостей
- •4.8.3. Нахождение сильных компонент
- •Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов
- •Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
- •4.8.4. Базы и антибазы
- •4.9. Независимые и доминирующие множества
- •4.9.1. Нахождение всех максимальных независимых множеств
- •Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.
- •4.10. Покрытия и раскраски
- •4.11. Деревья, остовы и кодеревья
- •4.11.1. Основные определения
- •4.11.2. Алгоритм построения остова неорграфа
- •4.11.4. Обходы графа по глубине и ширине
- •Доказательство.
- •4.11.5. Упорядоченные и бинарные деревья
- •4.12. Эйлеровы циклы. Гамильтонов контур
- •4.12.1. Метод Флёри построения эйлерова цикла
- •Матрица м данного графа имеет вид
- •4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
- •4.13. Плоские и планарные графы
- •4.13.1. Формула Эйлера
- •4.13.2. Критерии анализа планарности
- •4.13.3. Алгоритм укладки графа на плоскости
- •Задачи и упражнения
- •5. Комбинаторика
- •5.1. Перестановки
- •5.2. Перестановки с неограниченными повторениями
- •5.3. Размещения
- •5.4. Сочетания
- •5.5. Сочетания с повторениями
- •5.6. Производящие функции для сочетаний
- •5.7. Производящие функции для перестановок
- •5.8. Циклы перестановок
- •Общее число дубликатов
- •5.9. Принцип включений и исключений
- •Почему появился ?
- •Задачи и упражнения
- •6. Алгебра высказываний
- •6.1. Операции над высказываниями
- •6.2. Правила записи сложных формул
- •6.3. Таблицы истинности
- •6.4. Равносильность формул
- •6.5. Дизъюнктивные и конъюнктивные нормальные формы
- •6.5.1. Алгоритм приведения пф к нормальным формам
- •6.5.2. Аналитический способ приведения к сднф
- •6.5.3. Табличный способ приведения к сднф
- •6.5.4. Табличный способ приведения к скнф
- •6.6. Логическое следствие
- •Задачи и упражнения
- •7. Разрешимые и неразрешимые проблемы
- •Заключение
- •Библиографический список
- •394026 Воронеж, Московский просп., 14
5.1. Перестановки
Пусть А - некоторое конечное множество, состоящее из n различных элементов:
Будем образовывать из элементов множества А упорядоченные множества. В качестве первого упорядоченного множества возьмем множество, в котором элементы расположены в порядке возрастания их номеров:
.
Второе упорядоченное множество можно образовать, поменяв местами элементы a1 и a2 , а все остальные элементы первого множества оставив на своих местах:
.
Аналогичным способом из элементов множества А можно строить и другие упорядоченные множества.
Примеры перестановок:
1) распределение n различных должностей среди n человек;
2) расположение n различных предметов в одном ряду, состоящем из n мест.
Перестановками из n элементов называются всевозможные конечные упорядоченные множества, содержащие n различных элементов, которые можно получить из некоторого данного множества, состоящего из n элементов.
Число перестановок n различных элементов обозначают Pn (читается Р из n ).
Пример. Пусть дано множество чисел {3;5;7}.Найти число перестановок.
Решение.
Этому множеству соответствует 6 перестановок: 357; 375; 537; 573; 753; 735.
Отметим, что перестановки состоят из одних и тех же элементов, но отличаются между собой порядком.
Теорема. Число перестановок n различных элементов равно n!, т. е.
(5.1)
Для пустого множества принимается соглашение: пустое множество можно упорядочить только одним способом; поэтому считается, что 0!=1.
Доказательство. Чтобы вывести формулу числа перестановок, представим себе n ячеек, пронумерованных числами 1, 2,..., n. Все перестановки будем образовывать, располагая элементы An в этих ячейках. В первую ячейку можно занести любой из n элементов (иначе: первую ячейку можно заполнить n различными способами). Заполнив первую ячейку, можно n-1 способом заполнить вторую ячейку (иначе: при каждом способе заполнения первой ячейки находится n-1 способов заполнения второй ячейки). Таким образом, существует n(n-1) способов заполнения двух первых ячеек. При заполнении первых двух ячеек можно найти n-2 способов заполнения третьей ячейки, откуда получается, что три ячейки можно заполнить n(n-1)(n-2) способами. Продолжая этот процесс, получим, что число способов заполнения n ячеек равно . Отсюда ,
Pn = n·(n - 1)·(n - 2)·...321 (5.2)
Число n·(n-1)·(n-2)·...321, то есть произведение всех натуральных чисел от 1 до n, называется «n-факториал»и обозначается n!. Отсюда Pn =n!
Пример. .
По определению считается: 1!=1; 0!=1.
Пример. Слова «барк» и «краб» образованы в результате перестановки букв, составляющих слово «брак». Определить число всевозможных перестановок букв в слове «брак».
Решение.
Так как исходное слово содержит 4 буквы, то число всевозможных перестановок вычисляется по формуле:
P4 = 4! = 4 · 3 · 2 · 1 =24.