- •Богданов а.Е. Курс лекций
- •Содержание
- •§ 1. Основные понятия теории множеств
- •Основные понятия теории множеств
- •Способы задания множеств
- •Операции над множествами
- •§ 2. Соответствия. Функции. Отображения
- •§ 3. Понятие алгебры. Алгебра множеств кантора
- •Диаграмма Эйлера-Венна
- •§ 4. Бинарные отношения
- •Способы задания бинарных отношений
- •Свойства бинарных отношений
- •§ 5. Бинарное отношение эквивалентности
- •§ 6. Бинарное отношение порядка. Упорядоченные
- •§ 7. Решетки (структуры). Изоморфизм
- •Изоморфизм множеств
- •Дедекиндовые решетки
- •Дистрибутивные решетки
- •§ 8. Отношения (обобщение). Алгебраические
- •Операции над отношениями
- •Алгебраические системы
- •Глава ιι. Комбинаторный анализ
- •§ 1. Основные определения
- •Правила суммы и произведения
- •§ 2. Формулы расчета перестановок и сочетаний
- •§ 3. Бином и полином
- •§ 4. Подстановки
- •§ 5. Метод включений и исключений
- •§ 6. Метод производящих функций
- •§ 7. Комбинаторная мера информации. Вероятность искажения информации
- •Глава ιіі. Теория графов
- •§ 1. Первоначальные понятия теории графов
- •§ 2. Операции над графами. Способы задания графов Операции над графами
- •Способы задания графов
- •§ 3. Маршруты, цепи, циклы и другие характеристики графа
- •§ 4. Алгебраическая форма представления графа
- •Глава іv. Некоторые приложения графов
- •§ 1. Эйлеровы графы. Алгоритм флери. Гамильтоновы
- •Эйлеровы графы
- •Алгоритм Флери.
- •Метод построения эйлерового обхода двоичного куба
- •Гамильтоновы графы. Метод Робертса – Флореса
- •Метод перебора Робертса – Флореса
- •§ 2. Пространство циклов графа
- •§ 3. Независимое множество вершин графа
- •Алгоритм выделения пустых подграфов
- •§ 4. Вершинное число внешней устойчивости графа
- •§ 5. Плотность графа
- •Алгоритм выделения полных подграфов
- •§ 6. Раскраска графа
- •Оценки хроматического числа
- •Алгоритм минимальной раскраски вершин графа
- •§ 7. Планарность графа
- •Глава V. Оптимизационные алгоритмы теории графов
- •§ 1. Определение кратчайших путей. Алгоритм дейкстры
- •§ 2. Максимальный поток через сеть. Алгоритм
- •Алгоритм Форда – Фалкерсона
- •§ 3. Построение остова экстремального веса. Алгоритм краскала
- •§ 4. Метод ветвей и границ: задача коммивояжера. Общая модель задачи поиска
- •Дерево поиска частичных решений
- •§ 5. Применение ориентированных деревьев в задачах теории кодирования и диагностирования
- •§ 6. Построение оптимального дерева бинарного поиска. Алгоритм гильберта – мура
- •Алгоритм Гильберта – Мура построения оптимального дерева бинарного поиска Суть алгоритма
- •Алгоритм
- •§ 7. Сложность задач теории графов. Задача синтеза управляющих систем
- •Задача синтеза управляющих систем
- •Задача о выполнимости
- •Литература
- •Электронное пособие курс лекций
- •«Дискретная математика».
§ 3. Бином и полином
Запишем формулы бинома.
Для
(1)
Если заменить b на − b, то из формулы (1) следует:
, (2)
где коэффициенты называют биномиальными коэффициентами.
Для всех неотрицательных целых чисел п, k
(3)
Область определения биномиальных коэффициентов можно расширить:
для функция
(4)
является биномиальным коэффициентом.
Для целых оба определения для биномиальных коэффициентов совпадают.
Замечание: читается: С из п по k ; п над k .
Примеры.
□ 1)
2)
3)
4) . ■
Свойства биномиальных коэффициентов
Числа имеют ряд важных свойств:
10 для целых справедливо свойство симметрии
20 теоремы сложения:
из формулы бинома при а = 1, b = 1 следует:
,
это число равно числу всех возможных неупорядоченных подмножеств множества М, состоящего из п элементов (булеан),
при а = 1, b = −1 :
,
из этого равенства следует, что суммы биномиальных коэффициентов, стоящих на четных и нечетных местах, равны между собой и каждая равна ;
;
30 для теоремы сложения имеют вид :
.
Формула полинома является обобщением формулы бинома, т.е.
для любых действительных чисел а1, а2, … , ат не равных нулю и любого натурального числа п имеет место формула:
(5)
при этом суммирование распространяется на все наборы натуральных чисел для которых .
Коэффициенты
,
определенные для всех натуральных п и всех наборов неотрицательных чисел , для которых , называют полиномиальными коэффициентами.
Полиномиальные коэффициенты часто записывают в виде .
При формула (5) принимает вид
(6)
Пример. □
■
§ 4. Подстановки
Взаимно однозначное отображение конечного упорядоченного множества из n элементов на себя называется подстановкой n- й степени.
Пример.
□ Рассмотрим подстановку пятой степени
.
Здесь осуществляется отображение: число 1 первой строки переводится в число 3 второй строки; число 2 первой строки переводится в число 1 второй строки; число 3 – в 5; число 4 переводится в 4, как говорят, остается на месте; число 5 – в 2. ■
Часто подстановку задают только нижней строкой .
Подстановку, при которой на месте остаются все элементы, называют тождественной :
.
Подстановки можно перемножать. Операция произведения подстановок и состоит в последовательном их применении.
Пример. Найти произведение подстановок
□ Имеем
Здесь в первой подстановке 1 переходит в 2, а во второй подстановке 2 переходит в 1. Следовательно, в результирующей подстановке 1 будет переходить в 1. Аналогично поступают и с другими элементами. ■
Можно перемножать только подстановки одинаковой степени (совместимые ). Умножение подстановок n-й степени при некоммутативно.
Пример. Показать, что произведение подстановок из предыдущего примера некоммутативно.
□ Перемножим подстановки в обратном порядке :
Можно видеть, что результаты умножения не совпадают : . ■
Подстановки на множестве М = {1, 2, … ,n } образуют группу относительно операции произведения. Действительно, справедливы следующие утверждения:
1. Для любых двух подстановок элементов множества М = {1, 2, … ,n } произведение есть однозначно определенная подстановка;
2. Произведение подстановок ассоциативно, но не коммутативно:
;
3. Единичным элементом группы является тождественная подстановка :
;
4. Для любой подстановки существует обратная подстановка , т.е. если то существует обратная подстановка , при этом .
Группа подстановок на множестве М ={1,2,…, n} называется симметрической группой п-й степени и обозначается через Sn. Порядок симметрической группы п-й степени (число ее (группы) элементов) равен n!.
Пример.
□ Элементы симметрической группы S3 :
Порядок группы S3 равен 3! = 6. ■
Если в матрице подстановки элементов множества М={1,2, … ,n}
встречаются два столбца, для которых si < sj , ti > tj ( или si > sj , ti < tj ), то такая пара столбцов называется инверсией подстановки .
Подстановка называется четной или нечетной в зависимости от того, четно или нечетно число встречающихся в ней инверсий.
Пример. □ Пусть − число инверсий подстановки , то для подстановки из предыдущего примера будем иметь:
Подстановки − нечетные, − четные, тождественная подстановка не является четной или нечетной. ■
Неподвижной точкой подстановки называется элемент , для которого .
Например, в подстановках группы S3 ( см. выше ) имеет три неподвижные точки; − одну неподвижную точку 3; точку 2; и − не имеют неподвижных точек; − одну, равную 1.
Если матрицу подстановки перестановкой столбцов можно привести к виду
то задает взаимно однозначное отображение
множества на себя, которое называется циклом длины r и обозначается
Каждой неподвижной точке соответствует цикл длины 1. Каждую подстановку можно однозначно представить в виде произведения циклов, не имеющих общих элементов.
Пример. □ Данные подстановки можно записать в виде произведения следующих циклов:
■