- •Введение в дискретный анализ
- •Глава 1. Введение в теорию множеств
- •Тема 1.1. Множества и операции над ними
- •1.1.1. Основные понятия
- •1.1.2. Операции над множествами
- •1.1.3. Векторы и прямые произведения
- •Вопросы для повторения
- •Резюме по теме
- •Тема 1.2. Отношения
- •1.2.1. Основные понятия и определения
- •1.2.2. Бинарные отношения. Основные определения
- •1.2.4. Эквивалентность и порядок
- •Вопросы для повторения
- •Резюме по теме
- •Тема 1.3. Соответствия и функции
- •1.3.1. Соответствия и их свойства
- •1.3.2. Взаимно однозначные соответствия и мощности множеств
- •1.3.3. Функции и отображения
- •1.3.4. Операции
- •1.3.5. Гомоморфизмы и изоморфизмы
- •Вопросы для повторения
- •Резюме по теме
- •Глава 2. Математическая логика
- •Тема 2.1. Логика высказываний
- •2.1.1. Логические связки
- •2.1.2. Основные схемы логически правильных рассуждений
- •2.2.2. Булева алгебра
- •2.2.3. Эквивалентные преобразования
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.3. Полнота и замкнутость
- •2.3.1. Функционально полные системы
- •2.3.2. Алгебра Жегалкина и линейные функции
- •2.3.3. Замкнутые классы и монотонные функции
- •2.3.4. Теоремы о функциональной полноте
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.4. Нечеткая логика
- •2.4.1. Основные понятия теории нечетких множеств
- •2.4.2. Логические операции над нечеткими множествами
- •2.4.3. Свойства логических операций над нечеткими множествами
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.5. Нечеткие модели управления
- •2.5.1. Нечеткие операторы
- •2.5.2. Нечеткая и лингвистическая переменные
- •2.5.3. Нечеткий логический вывод
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.6. Логика предикатов
- •2.6.1. Предикаты. Основные понятия
- •2.6.2. Кванторы
- •2.6.3. Выполнимость и истинность
- •2.6.4. Эквивалентные соотношения. Префиксная нормальная форма
- •Вопросы для повторения
- •Резюме по теме
- •Глава 3. Комбинаторика
- •Тема 3.1. Комбинаторные конфигурации
- •3.1.1. Принципы сложения и умножения
- •3.1.2. Перестановки
- •3.1.3. Размещения
- •3.1.4. Сочетания
- •3.2.2. Полиномиальная формула
- •3.2.3. Формула включений и исключений
- •Вопросы для повторения
- •Резюме по теме
- •Глава 4. Теория графов
- •Тема 4.1. Основные понятия и операции на графах
- •4.1.1. Основные понятия
- •4.1.2. Способы задания графов
- •4.1.3. Операции над частями графа. Графы и бинарные отношения
- •Вопросы для повторения
- •Резюме по теме
- •Тема 4.2. Маршруты и деревья
- •4.2.1. Маршруты, пути, цепи, циклы
- •4.2.2. Дерево и лес
- •5.1.2. Способы задания автоматов
- •5.1.3. Взаимосвязь между моделями Мили и Мура
- •Вопросы для повторения
- •Резюме по теме
- •Тема 5.2. Детерминированные конечные автоматы
- •5.2.1.Основные понятия детерминированных конечных автоматов
- •5.2.2. Схема доказательства правильности конечного автомата
- •5.2.3. Произведение автоматов
- •5.3.2. Детерминизация нка
- •Вопросы для повторения
- •Резюме по теме
3.1.3. Размещения
Упорядоченные выборки объемом m из n элементов (m n), где все элементы различны, называются размещениями. Число размещений из n элементов по m обозначается .
Теорема 3. =
Обозначим x = . Тогда оставшиеся (n – m) элементов можно упорядочить (n – m)! способами. По принципу произведения, если объект A можно выбрать x способами, объект B (n – m)! способами, то совместный выбор “A и B” можно осуществить x (n – m)! способами, а выбор “A и B” есть перестановки и Pn = n! Отсюда x = =
Рассуждая иначе: первый элемент выбираем n способами, второй – (n – 1) способами и т.д. , m–й элемент выбираем (n – m + 1) способом. По принципу произведения вновь имеем: n(n – 1)...(n – m +1), что совпадает с .
Пример 3.
Группа из 15 человек выиграла 3 различных книги. Сколькими способами можно распределить эти книги среди группы?
= 15 14 13 = 2730.
Рассмотрим размещения, которые не являются подмножествами.
Упорядоченные выборки объемом m из n элементов, где элементы могут повторяться, называются размещениями с повторениями. Их число обозначается (n).
Теорема 4. (n) = nm.
Доказательство. Первый элемент может быть выбран n способами, второй элемент также может быть выбран n способами и так далее, m -й элемент также может быть выбран n способами. По принципу произведения получаем nm .
Пример 4.
Кодовый замок состоит из четырех разрядов, в каждом разряде независимо от других могут быть выбраны цифры от 0 до 9. Сколько возможных комбинаций?
Здесь n = 10, m = 4 и ответом будет 104.
3.1.4. Сочетания
Неупорядоченные выборки объемом m из n элементов (m n) называются сочетаниями. Их число обозначается .
Теорема 5.
Доказательство. Очевидно, Действительно, объект A – неупорядоченная выборка из n элементов по m, их число . После того, как эти m элементов отобраны, их можно упорядочить m! способами (в роли объекта B выступает “порядок“ в выборке). Совместный выбор “A и B“ – упорядоченная выборка.
Пример 5.
Группа из 15 человек выиграла 3 одинаковых книги. Сколькими способами можно распределить эти книги?
Рассмотрим сочетания, которые не являются подмножествами.
Пусть имеется n типов элементов, каждый тип содержит не менее m одинаковых элементов. Неупорядоченная выборка объемом m из имеющихся элементов (их число mn ) называется сочетанием с повторением. Число сочетаний с повторениями обозначается (n).
Теорема 6. (n) = .
Доказательство. Пусть в выборку вошло m1 элементов первого типа, m2 элементов второго типа, ...mn – n-го типа. Причем каждое 0 m i m и m1+m2+ ...+ mn= =m. Сопоставим этой выборке вектор следующего вида: Очевидно, между множеством неупорядоченных выборок с повторениями и множеством векторов {bn} существует биекция (докажите это!). Следовательно, (n) равно числу векторов bn. “ Длина вектора” bn равна числу 0 и 1, или m+ +n–1. Число векторов равно числу способов, которыми m единиц можно поставить на m + n 1 мест, а это будет .
Пример 6.
В кондитерской имеется 7 видов пирожных. Покупатель берет 4 пирожных. Сколькими способами он может это сделать? (Предполагается, что пирожных каждого вида 4).
Число способов будет
Пример 7.
Пусть V = {a, b, c}. Объем выборки m = 2. Перечислить перестановки, размещения, сочетания, размещения с повторениями, сочетания с повторениями.
1. Перестановки: {abc, bac, bca, acb, cab, cba}. P3=3!=6.
2. Размещения: {(ab), (bc), (ac), (ba), (cb), (ca)}.
3. Сочетания: {(ab), (ac), (bc)}.
4. Размещения с повторениями: {(ab), (bc), (ac), (ba), (cb), (ca), (aa), (bb), (cc)}. (3)= 32 = 9.
5. Сочетания с повторениями: {(ab), (bc), (ca), (aa), (bb), (cc)}.
Вопросы для повторения
1.Чем занимается комбинаторика?
2.Кем впервые был введен термин комбинаторика?
3.В чем заключается смысл правила суммы и произведения?
4.Что представляет собой выборка?
5.Когда используются перестановки?
6.Назовите отличие размещения от перестановки?
7.В чем особенность размещений с повторениями?
8.Что такое сочетание?
Резюме по теме
Показано назначение комбинаторики. Применение комбинаторики в менеджменте в явном виде практически не используется, но при применении статистики или же при решении задач линейного программирование аппарат комбинаторики приходится к месту. Рассмотрен принцип сложения и умножения. Показаны перестановки, размещения и сочетания.
Тема 3.2. Разбиения. Включения и исключения
Цель: ознакомиться с понятиями комбинаторики разбиения, включения и исключения.
Задачи:
Рассмотреть разбиения.
Рассмотреть полиномиальную формулу.
Рассмотреть формулы включения и исключения.
3.2.1. Разбиения
Пример 1.
Подсчитаем число разбиений конечного множества Х, где , на k подмножеств Х1, Х2, …, Хk таких, что каждое Хi содержит ni элементов, т.е.
, при , , i=1, 2, .., k. (1)
Очевидно, что при этом n1+n2+…+nk=n. Отметим, что для некоторых номеров i возможно . Число указанных разбиений при фиксированных ni обозначается .
Замечание. В данном случае набор подмножеств множества Х в разбиении является упорядоченным, т.е. Х1, Х2, …, Хk – упорядоченная последовательность множеств.
Лемма. .
Доказательство: Множество Х1 может быть выбрано . После выбора Х1 множество Х2 можно выбрать способами (т.к. и ) и т.д. Тогда по правилу произведения выбор упорядоченной последовательности множеств Х1, Х2, …, Хk можно произвести способами.
Теорема 1. .
Доказательство: [после сокращений]= , что и требовалось доказать.
Пример 2.
Требуется найти число размещений с повторениями из n элементов по k элементов, в которых первый элемент встречается ровно n1 раз, второй элемент встречается ровно n2 раз, …, k–ый элемент встречается ровно nk раз (n1+n2+…+nk=n).
Теорема 2. Число таких размещений равно .
Доказательство. Каждому размещению указанного типа поставим в соответствие разбиение множества номеров элементов в выборке на подмножества Х1, Х2, …, Хk, где Хi – множество номеров элементов i–го типа в выборке. Очевидно, что при этом выполняются условия (1). Указанное соответствие между размещениями данного типа и разбиениями, удовлетворяющими (1), является взаимно однозначным (биективным). Следовательно, в силу теоремы 1, теорема 2 верна.
Пример 3.
Сколькими способами можно разбить конечное множество Х, где , на подмножества, среди которых для каждого i=1, 2,…, n имеется подмножеств с i элементами, где ? Заметим, что в отличие от задачи 1 набор подмножеств в разбиении не является упорядоченным (т.е. порядок подмножеств в разбиении не является существенным). Обозначим число указанных неупорядоченных разбиений множества Х через .
Теорема 3. .
Доказательство. Каждое из неупорядоченных разбиений, рассмотренных при определении величины , можно, нумеруя блоки этого разбиения, привести способами к упорядоченным разбиениям вида
, …, , , …, , …, , …, ,
где , ,…, .
При этом объединение получаемых таким образом попарно непересекающихся множеств является совокупностью всех возможных разбиений множества Х. Следовательно, по правилу суммы, используя теорему 1, получим:
(где суммирование производится по всем рассматриваемым неупорядоченным разбиениям), откуда и следует справедливость доказываемого утверждения.
Пример 4.
Сколькими способами из группы в 25 человек можно сформировать 5 коалиций по 5 человек?
Пусть Х – множество людей в группе, – число коалиций по i человек, где i =1, 2, …, 25. Тогда из условия задачи следует, что , , а для других i , и, таким образом, искомое число равно .