- •Часть 2
- •Часть 2
- •Введение
- •1. Элементы комбинаторики
- •1.1. Простейшие комбинаторные конфигурации
- •Основные правила комбинаторики
- •Выборки элементов без повторений
- •Выборки элементов с повторениями
- •Латинские прямоугольники, конечные проективные плоскости и блок-схемы
- •1.2.1. Латинские прямоугольники
- •1.2.2. Конечные проективные плоскости
- •1.2.3. Блок-схемы
- •Формула включений и исключений
- •Объединение комбинаторных конфигураций
- •1.3.2. Принцип включения и исключения
- •1.3.3. Число булевых функций, существенно зависящих от всех своих переменных
- •1.3.4. Решето Эратосфена
- •Рекуррентные уравнения
- •1.4.1. Определение рекуррентного уравнения
- •1.4.2. Решение линейного однородного рекуррентного уравнения
- •1 (2) .4.3. Решение линейного неоднородного рекуррентного уравнения
- •1.5. Производящие функции
- •1.5.1. Общие сведения о производящих функциях
- •1.5.2. Производящая функция для биноминальных коэффициентов
- •1.5.3. Производящая функция для чисел Фибоначчи
- •1.6.1. Определение z – преобразования
- •1.6.2. Обратное z – преобразование
- •В правой части этого равенства стоит контурный интеграл в z-плоскости по любому замкнутому контуру в области сходимости, охватывающему начало координат.
- •1.6.3. Свойства z-преобразования
- •1.6.4. Использование z-преобразований для решения рекуррентных уравнений
- •1.6.5. Таблица односторонних z-преобразований
- •1.7. Трансверсали и перманенты
- •1.7.1. Множества и мультимножества
- •1.7.2. Трансверсали
- •1.7.3. Пермамент матрицы
- •1.7.4. Число трансверсалей
- •1.8. Матрицы Адамара
- •1.8.1. Определение матрицы Адамара и ее свойства
- •1.8.2. Эквивалентные преобразования матриц Адамара
- •1.8.3. Построение матриц Адамара
- •2. Основы теории конечных автоматов
- •2.1. Понятие конечного автомата
- •2.1.1. Общие сведения о конечных автоматах
- •2.1.2. Абстрактное определение конечного автомата
- •2.2. Эквивалентности в автоматах
- •2.2.1. Основные определения
- •2.2.2. Покрытия и морфизмы
- •2.2.3. Эквивалентные состояния автоматов
- •2.3. Процедура минимизации конечных автоматов
- •2.4. Автоматные функции и эксперименты с автоматами
- •2.4.1. Понятие ограниченно детерминированной функции
- •2.4.2. Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •2.4.3. Пример реализации конечного автомата с помощью сфэз
- •2.4.4. Эксперименты с автоматами
- •2.5. Автоматные языки
- •2.5.1. Представление о формальных языках
- •2.5.2. Алфавит, слово, язык
- •2.5.3. Классификация грамматик и языков
- •2.5.4. Понятие формальной грамматики
- •2.5.5. Автоматные грамматики
- •2.6. Модификации конечных автоматов
- •2.6.1. Частичные автоматы
- •2.6.2. Понятия недетерминированного и вероятностного автоматов
- •2.7. Процедура минимизации частичного автомата
- •2.7.1. Совместимые состояния
- •2.7.2. Техника определения совместимых состояний
- •2.7.3. Построение минимального автомата
- •3. Введение в нечеткую математику
- •3.1. Нечёткие множества
- •3.2. Нечеткие отношения
- •3.3. Нечеткая логика
- •Заключение
- •Библиографический список
- •Оглавление
- •2.7.3. Построение минимального автомата 98
- •Часть 2
- •394026 Воронеж, Московский просп., 14
- •Часть 2
1. Элементы комбинаторики
1.1. Простейшие комбинаторные конфигурации
Комбинаторика – раздел математики, связанный с решением задач выбора и размещения элементов конечного множества в соответствии с заданными правилами.
Каждое правило определяет способ построения некоторой конструкции из элементов исходного множества. Полученные конструкции называются комбинаторными конфигурациями.
Цель комбинаторного анализа заключается в изучении комбинаторных конфигураций, алгоритмов их построения, а также решении задач по их перечислению.
Основные правила комбинаторики
Большинство комбинаторных задач решается с помощью двух основных правил – правила суммы и правила произведения.
Правило суммы. Пусть A, B – конечные множества, |A| = n, |B| = m.
,
следовательно
.
Комбинированная интерпретация.
Если некоторый объект A можно выбрать n способами, а другой объект B можно выбрать m способами, то выбор «либо A, либо B» можно осуществить n+m способами.
Правило произведения. Если мощность |A| = n, |B| = m, то .
Комбинаторная интерпретация.
Если объект A можно выбрать n способами, а после каждого такого выбора другой объект B можно выбрать (независимо от выбора объекта A) m способами, то пары объектов A и B можно выбрать способами.
Пусть , и |А| - число элементов множества A. Составим декартово произведение множеств A и B, т.е. множество пар .
Тогда правило произведения записывается следующим образом:
Пример. Сколько всего существует двузначных чисел?
Решение. Поскольку в двузначном числе цифра, обозначающая число десятков, должна быть отлична от нуля, то A = {1, 2, …, 9}, B = {0, 1, 2, …, 9} и ,
Выборки элементов без повторений
Простейшими комбинаторными конфигурациями являются перестановки, размещения и сочетания.
Перестановки. Пусть . Перестановкой элементов множества M называется любой упорядоченный набор элементов , состоящий из n различных элементов множества M.
Перестановки отличаются друг от друга порядком следования элементов.
Теорема. Число всех перестановок равно n!
Доказательство. На первом месте можно разместить n элементов, на втором – любой из оставшихся (n-1) элементов и т.д. Для последнего места остается 1 элемент. В силу правила произведения имеем:
.
Пример. Сколькими способами можно разместить 5 студентов при наличии 5 мест?
.
Размещения. Пусть множество M состоит из n элементов. Размещением (упорядоченной выборкой) из n элементов по m элементов называется любой упорядоченный набор элементов , состоящий из m различных элементов множества M.
Теорема. Число размещений n элементов по m элементов обозначается . . Справедлива формула:
Доказательство. Размещение M элементов множества M можно представить, как заполнение некоторых m позиций элементами множества M. При этом первую позицию можно заполнить n способами, вторую позицию (n-1) способами. Последнюю позицию можно заполнить (n-m+1) способами.
Пример. Из 10 книг производным образом берутся 3 книги и ставятся на полку. Сколько существует способов такой расстановки книг?
.
Заметим, что размещение из n элементов по n элементов представляет собой перестановку, т.е.:
Сочетания. Сочетанием (неупорядоченной выборкой) из n элементов по m, где , называется неупорядоченное подмножество множества M, состоящее из n различных элементов.
Теорема. Число сочетаний из n элементов по m обозначается как и определяется по формуле:
Доказательство. Если объединить размещения из n элементов по m, которые состоят из одних и тех же элементов (то есть не учитывать порядка расположения элементов), то получим сочетание из n элементов по m. Так как для каждого такого сочетания можно получить n! размещений. Тогда и, следовательно:
.