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

• Автор: Мухина, Светлана Анатольевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 64 с.

Оглавление
1 Введение
1.1 Диаграмма Хассе
1.1.1 Степени вершин
1.1.2 Длины цепей, соединяющих две вершины
1.1.3 Мощность антицепей
1.1.4 Геометрические свойства диаграммы Хассе
1.2 Бинарный алфавит
1.3 д-ичный алфавит
2 Бинарный алфавит
2.1 Основные понятия и определения
2.2 Метод коэффициентов
2.3 Установление связи между характеристиками частичного порядка
“быть фрагментом”
2.3.1 Независимость от вида фрагмента
2.3.2 Рекуррентное соотношение для п,&)
2.3.3 Точное соотношение для 7дг(т, п, к)
2.3.4 Следствия
2.3.5 Примеры
3 д-ичный алфавит

3.1 Основные понятия и определения
3.2 Число слов, содержащих в качестве фрагмента фиксированное
слово а
3.3 Серийное представление слов
3.4 Число фрагментов д-ичного слова
3.5 Композиция слов
3.6 Примеры
3.7 Мощность антицепей

Глава
Введение
1.1 Диаграмма Хассе
Комбинаторика слов представляет собой важный раздел дискретной математики, имеющий глубокое внутреннее содержание, разнообразные связи со многими классическими областями современной математики и многочисленные приложения в теории информации, математической генетике, структурной лингвистике и т.д.
Основным объектом исследования являются слова, множества слов, части слова, связь частей слова, упорядоченность на множестве слов.
Итак, пусть В — {01,02,, ая} - ц-ичный алфавит и В* - множество всех слов конечной длины над алфавитом В. Если а € В*, то любое слово а', полученное из а удалением некоторых букв, называется фрагментом слова а. Это отношение задает частичный порядок на В*, который мы будем обозначать стандартным образом
а' < а, (1.1)
есди а' - фрагмент а.
Геометрически отношение (1.1) описывается с помощью диаграммы
веса Хэмминга т, содержащих в качестве фрагмента заданное слово длины п и веса Хэмминга к.
Пример 2.6 Пусть к — 0. Тогда справделиво
при N — т п,
Кт; (2.19)
0, при N — т < п.
Рм(т,п, 0)
Данное соотношение следует из примера 2.5 (случай к = 0 и а = 0", см. раздел 2.3.3) и независимости функции Р(т,п, к) от вида фрагмента. Пример 2.7 Пусть к = 1. Тогда справделиво
1)=(т)-(т+т”2)' (2'20)
Действительно, при к — 1 имеем:
**»» и - х? (;:!) (*-„:*+0 (2-21)
у=п—1 4 ' 4 '
Подробное вычисление суммы (2.21) представлено в примере 2.5 (случай к = 1 и а = 0П_11, см. раздел 2.3.3).
Пример 2.8 Пусть к = 2. Тогда справедливо
„ , /т + п — 3 (т + п- 4
ЗДт.п,2)=(Д-( т т_1 (ЛГ-т.-гг+З). (2.22)
Действительно, при к — 2 ’’явное” выражение для функции Ддг(т, п, 2) принимает вид:
ТМт, п, 2) = СУ ~ 0 ( АГ М ~ У )
+ Vп — 3 / ЛГ — тп — п + 2
у=п-2 4
т+п-4 / 1 / дг
/2/ — 1Л