Диаграмма Хассе частичного порядка быть фрагментом

Оглавление
1 Введение 4
1.1 Диаграмма Хассе............................................. 4
1.1.1 Степени вершин ...................................... 5
1.1.2 Длины цепей, соединяющих две вершины................. 6
1.1.3 Мощность антицепей................................... 8
1.1.4 Геометрические свойства диаграммы Хассе.............. 9
1.2 Бинарный алфавит............................................ 9
1.3 д-ичный алфавит............................................ 10
2 Бинарный алфавит 14
2.1 Основные понятия и определения ............................ 14
2.2 Метод коэффициентов........................................ 17
2.3 Установление связи между характеристиками частичного порядка
“быть фрагментом”.......................................... 19
2.3.1 Независимость от вида фрагмента..................... 19
2.3.2 Рекуррентное соотношение для /^(т, га, к)........... 22
2.3.3 Точное соотношение для ^(гд, га,к).................. 23
2.3.4 Следствия........................................... 28
2.3.5 Примеры ............................................ 34
3 д-ичный алфавит 40
2
3.1 Основные понятия и определения ............................. 40
3.2 Число слов, содержащих в качестве фрагмента фиксированное
слово а...................................................... 42
3.3 Серийное представление слов................................. 45
3.4 Число фрагментов д-ичного слова............................. 49
3.5 Композиция слов............................................. 51
3.6 Примеры .................................................... 59
3.7 Мощность антицепей.......................................... 60
3
Глава 1
Введение
1.1 Диаграмма Хассо
Комбинаторика слов представляет собой важный раздел дискретной математики, имеющий глубокое внутреннее содержание, разнообразные связи со многими классическими областями современной математики и многочисленные приложения в теории информации, математической генетике, структурной лингвистике и т.д.
Основным объектом исследования являются слова, множества слов, части слова, связь частей слова, упорядоченность на множестве слов.
Итак, пусть В — {ах, аг,..., ая) - д-ичный алфавит и В* - множество всех слов конечной длины над алфавитом В. Если а € В*, то любое слово а', полученное из а удалением некоторых букв, называется фрагментом слова а. Это отношение задает частичный порядок на который мы будем обозначать стандартным образом
а1 < а, (1.1)
есди а' - фрагмент а.
Геометрически отношение (1.1) описывается с помощью диаграммы
Хассе, которая представляет собой граф с множеством вершин X = В*, смежность которых определяется понятием “покрытия”. Другими словами а и Ь - смежны, если а < Ь и не существует вершины z с условием а < z < Ь. Таким образом, смежными на диаграмме Хассе являются “ближайшие” сравнимые вершины. Ниже изображена часть диаграммы Хассе для бинарных слов длины < 3.
ООО 001 010 100 011 101 110 111
Важнейшими понятиями, связанными с частичным порядком (1.1) и диаграммой Хассе, являются следующие:
а) степени вершин;
б) длины цепей, соединяющих вершины а и Ь\
в) мощность антицепей.
1.1.1 Степени вершин
Описание степеней вершин связано с разложением произвольного слова на произведение блоков или, что то же самое, с серийным представлением слов из В*.
Определение 1.1 Пусть ... г>,1+г - подслооо (фактор) слова
у. Подслоев У{ называется серией V, если
а) г*, = и*1+1 = ... = ?Л1+Г = а3 в В;
5
б) Щ\-1 Ф asi ^ii+r+l Ф as-
Ясно, что каждое подслово v G Вж имеет единственное представление в виде произведения (конкатенации) серий.
Пример 1.1
а) Если q = 2, то серийное представление любого слова в бинарном алфавите имеет вид: а = 7^7^ ... 7**. Здесь 7 - логическое отрицание 7 и к - число серий слова а.
б) Если q = 3 и а = (0,1,1,2,1,2,2,2,0,0), то серийное представление а имеет следующую форму: а = 012212302.
1.1.2 Длины цепей, соединяющих две вершины
Если а, 6 G В* и а < 6, то любое множество элементов
а ^ 61 < 62 < ... < bk ^ b (1.2)
называется цепью. Цепь (1.2) называется максимальной или насыщенной, если в нее нельзя “вставить” ни одного элемента из В*.
Пример 1.2 Цепь С\ = {0,10,101} является максимальной, а цепь С2 = {1,111} - нет.
Определение 1.2 Длина 1(С) конечной цепи С определяется равенством 1{С) — \С\ — 1.
Определение 1.3 Если а, 6 G В*, то говорят., что элемент b покрывает элемент а, если а < b и ни один элемент z G В* не удовлетворяет условию а < z < 6.
Определение 1.4 Элемент a G В* называется максимальным (минимальным), если из того, что а ^ х (ж < а), х G В*, следует. а = х.
б