- •Н.А. Ююкин
- •Введение
- •1. Элементы комбинаторики
- •1.1. Простейшие комбинаторные конфигурации
- •Основные правила комбинаторики
- •Выборки элементов без повторений
- •Выборки элементов с повторениями
- •Латинские прямоугольники, конечные проективные плоскости и блок-схемы
- •1.2.1. Латинские прямоугольники
- •1.2.2. Конечные проективные плоскости
- •1.2.3. Блок-схемы
- •Формула включений и исключений
- •1.3.1. Объединение комбинаторных конфигураций
- •1.3.2. Принцип включения и исключения
- •1.3.3. Число булевых функций, существенно зависящих от всех своих переменных
- •1.3.4. Решето Эратосфена
- •1.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-плоскости по любому замкнутому контуру в области сходимости, охватывающему начало координат.
- •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.2. Моделирование автоматной функции с помощью схемы из функциональных элементов и задержки
- •2.4.3. Эксперименты с автоматами
- •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. Нечеткая логика
- •Заключение
- •Библиографический список
- •Оглавление
- •1. Элементы комбинаторики 7
- •2. Теория автоматов 58
- •3. Введение в нечеткую математику 106
Выборки элементов с повторениями
Размещением(упорядоченной выборкой)с повторениямиизnэлементов поmназывается любой упорядоченный набор, элементы которого могут повторяться. Поскольку в упорядоченном наборе может находиться любой изnэлементов, то число размещений с повторениями (обозначение такого числа) равноnm. Таким образом:
Пример. Из чисел 1, 2, 3, 4 составляются трехзначные числа. Сколько чисел можно получить таким образом.
.
Сочетанием(неупорядоченной выборкой) с повторениями изnэлементов поm элементов называется множество, состоящее из элементов, выбранныхmраз из множестваM. При этом допускается выбирать элемент повторно.
Число сочетаний с повторениями из nэлементов поmобозначается.
Пример. Сколько существует различных результатов бросания двух одинаковых кубиков.
Выбор элементов |
Упорядоченная |
Неупорядоченная |
Без повторений | ||
С повторениями |
Латинские прямоугольники, конечные проективные плоскости и блок-схемы
1.2.1. Латинские прямоугольники
Пусть дано множество S из n элементов. Латинский прямоугольник, основанный на множестве S, есть прямоугольная таблица.
Каждая строка – упорядоченная выборка элементов множества S длины s, каждый столбец – упорядоченная выборка элементов множества S длины r, причем , .
Обозначим элементы S через 1,2,..,n. Предположим, что s = n. Тогда латинский прямоугольник содержит в каждой строке перестановку элементов 1,2,..,n. Эти перестановки выбраны так, что ни один столбец не содержит повторяющихся элементов.
Латинский прямоугольник называется нормализованным, если его первая строка записана в естественном порядке 1,2,..,n.
Теорема 1.Для любых чисел существует латинскийпрямоугольник.
Доказательство. Будем «заселять» нашm-этажный «дом» с верхнего этажа. Наm-м этаже «расселим» числа 1, 2, 3,...,nв их естественном порядке. На(т—1)-м этаже «расселение» начнем с двойки: 2, 3,...,п,1; на (т—2)-м этаже — с тройки: 3, 4, ...,п,1, 2, и так далее; наконец, нат-м этаже «расселение» начнем с числат: т,т+1, ...» ",1. 2,...,т—1. Тогда «дом» будет «заселен» так, как это сделано в таблице. Ясно, что при таком «заселении» нет двух одинаковых «жильцов», находящихся на одном «этаже» или в одном «подъезде». Следовательно, перед нами — «т-этажный» латинский прямоугольник длинойп.Значит,тхп-прямоугольники существуют.
Перейдем теперь к подсчету числа латинских прямоугольников. Особенно просто решается задача для одноэтажных прямоугольников.
Теорема 2.Число латинских 1хn-прямоугольников равно
Доказательство. Латинский 1хn– прямоугольник - это просто произвольная перестановка изпчисел. Таких перестановок всегоп!(на первое место ставили любое изпчисел, на второе - любое из (п-1) оставшихся, на третье - любое из (п-2) оставшихся после этого и т. д.).
Перейдем к 2хn - прямоугольникам. Верхняя строка этого прямоугольника - любая перестановка.
Нижняя строчка - перестановка, в которой на каждом месте стоит число, не равное числу, стоящему на том же месте в первой перестановке. Если мы произвольным образом переставим столбцы нашего прямоугольника, он останется латинским, и при этом верхнюю перестановку можно сделать любой. Из этого видно, что какую бы конкретную перестановку мы ни взяли, число латинских прямоугольников, у которых верхняя строчка совпадает именно с этой перестановкой, будет одним и тем же для всех перестановок. Назовем латинский 2хn-прямоугольникнормализованным, если в его верхней строчке числа стоят подряд: 1, 2, 3, ..., (п-1),п.Из сказанного видно, что числоL(2,п)латинских 2хn-прямоугольников равно числунормализованных латинских 2хn-прямоугольников, умноженному на число перестановокпчисел, т. е.
Для числа нормализованных латинских 2хn-прямоугольников имеется несколько изящных формул.
Теорема 3. (Формула Эйлера).
Таблица
1 |
2 |
3 |
… |
|
n |
2 |
3 |
4 |
… |
n |
1 |
… |
… |
… |
… |
… |
… |
m |
|
|
… |
|
|
Это, как говорят, рекуррентная формула: если мы знаем и, а, очевидно,=0 и=1, то мы можем найти с ее помощью последующие:
и т. д.
Доказательство. Всякую перестановку можно записать как систему циклов. Это делается так. Пусть, скажем, на 1-м месте стоит ,пишем. Если на-м месте стоит, напишем.Затеми так до тех пор, пока мы снова не дойдем до единицы. Затем берем самое маленькое из чисел, не вошедших в наш цикл, и строим цикл, начиная с него. В конце концов всепчисел окажутся стоящими в циклах. Число циклов может быть любым от 1 доn, и длина цикла может быть любой от 1 доп.Наше условие - что ни одно число не стоит на своем месте - запрещает циклы длиной 1.
Теперь построим по нашей перестановке перестановку длиной п-1 илип-2 и тоже без циклов длиной 1. Найдем на одном из циклов числоп. Если длина этого цикла больше двух, мы просто выбросимпи соединим «накоротко»pсq. Если жепвходит в цикл длиной 2, например в изображенный на рисунке 5, мы просто выбросим этот цикл и уменьшим все числа отk+1доп-1на единицу:
,.
В первом случае получится перестановка (п-1) чисел, во втором случае – перестановка (п-2) чисел. Сколькими способами у нас может получиться перестановка (п-1) чисел? Ясно, что (п-1) способами: чтобы вернуться к перестановке длинойп,мы должны разорвать любую стрелку(а их (п-1) пар) и вставить тудап:. Сколькими способами получается перестановка (п-2) чисел? Снова (п-1) способами: мы добавляем цикла, гдеk- любое число от 1 до (п-1), и увеличиваем на единицу числа.Значит
что и требовалось.
Обозначая через L(r, n) число латинских прямоугольников, аK(r, n) – число нормализованных латинских прямоугольников.
Задача о перечислении латинских прямоугольников не решена в общем случае.
Формула для K(3, n) имеет сложное выражение.
Если s=r=n, то латинский прямоугольник называется латинским квадратом порядкаn.
Латинский квадрат может рассматриваться, как таблица умножения в общих алгебраических системах.
In– число квадратов порядкаn, в которых элементы первой строки и первого столбца расположены в естественном порядке.
n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
In |
1 |
1 |
1 |
4 |
56 |
9408 |
16947080 |
Латинские квадраты и называются ортогональными, если упорядоченная пара при, где . где
- элемент, расположенный на пересечении i-й строки и j-го столбца матрицы, полученной наложением латинских квадратов A и B. Для всех есть пары ортогональных квадратов. Для n= 6 таких пар нет.
Несколько латинских квадратов одного порядка называются попарно ортогональными, если любые 2 из них ортогональные.
Существует ряд методов построения ортогональных латинских квадратов. Они предназначены для получения возможно большого числа попарно ортогональных латинских квадратов порядка n. Такие латинские квадраты применяются в математической статистике, теории информации, планировании экспериментов.