Диаграмма Хассе частичного порядка "быть фрагментом" Мухина Светлана Анатольевна

Содержание к диссертации

Введение

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 g-ичный алфавит 10

2 Бинарный алфавит 14

2.1 Основные понятия и определения 14

2.2 Метод коэффициентов 17

2.3 Установление связи между характеристиками частичного порядка "быть фрагментом" 19

2.3.1 Независимость от вида фрагмента

2.3.2 Рекуррентное соотношение для F/r(га, п) 22

2.3.3 Точное соотношение для F/v(m, п, к) 23

2.3.4 Следствия 28

2.3.5 Примеры 34

3 д-ичный алфавит 40

3.1 Основные понятия и определения 40

3.2 Число слов, содержащих в качестве фрагмента фиксированное слово 42

3.3 Серийное представление слов 45

3.4 Число фрагментов g-ичного слова 49

3.5 Композиция слов 51

3.6 Примеры 59

3.7 Мощность антицепей 60

Заключение

• Длины цепей, соединяющих две вершины
• Установление связи между характеристиками частичного порядка "быть фрагментом"
• Точное соотношение для F/v(m, п, к)
• Число слов, содержащих в качестве фрагмента фиксированное слово

Введение к работе

1.1 Диаграмма Хассе

Комбинаторика слов представляет собой важный раздел дискретной математики, имеющий глубокое внутреннее содержание, разнообразные связи со многими классическими областями современной математики и многочисленные приложения в теории информации, математической генетике, структурной лингвистике и т.д.

Основным объектом исследования являются слова, множества слов, части слова, связь частей слова, упорядоченность на множестве слов.

Итак, пусть В — {ai, 0,2,..., a_q} - g-ичный алфавит и В* - множество всех слов конечной длины над алфавитом В. Если а Є В*, то любое слово а/, полученное из а удалением некоторых букв, называется фрагментом слова а. Это отношение задает частичный порядок на В*, который мы будем обозначать стандартным образом

а' < а, (1.1)

есди а' - фрагмент а.

Геометрически отношение (1.1) описывается с помощью диаграммы

Хассе, которая представляет собой граф с множеством вершин X = В*, смежность которых определяется понятием "покрытия". Другими словами а и Ъ - смежны, если а < 6 и не существует вершины z с условием а < z < Ъ. Таким образом, смежными на диаграмме Хассе являются "ближайшие" сравнимые вершины. Ниже изображена часть диаграммы Хассе для бинарных слов длины ^ 3.

Важнейшими понятиями, связанными с частичным порядком (1.1) и диаграммой Хассе, являются следующие:

а) степени вершин;

б) длины цепей, соединяющих вершины а и 6;

в) мощность антицепей.

1.1.1 Степени вершин

Описание степеней вершин связано с разложением произвольного слова на произведение блоков или, что то же самое, с серийным представлением слов из Б*.

Определение 1.1 Пусть v\ = г^г^+і... V{_1+r - подслово (фактор) слова v. Подслово Vi называется серией v, если

a) v_h = v_h+i = ... = v_il+r = a_s Є В;

6) v_h-i ф a_s, Vi_l+r+i ф a_s.

Ясно, что каждое подслово v Є В* имеет единственное представление в виде произведения (конкатенации) серий. Пример 1.1

а) Если q = 2, то серийное представление любого слова в бинарном
алфавите имеет вид: а = 7^7^²... 7^ifc- Здесь 7 - логическое отрицание
7 и к - число серий слова а.

б) Если q = 3 и а = (0,1,1, 2,1, 2,2,2,0,0), то серийное представление
а имеет следующую форму: а = 01²212³0².

1.1.2 Длины цепей, соединяющих две вершины

Если а, Ъ Є В* и а < 6, то любое множество элементов

а ^ &1 < Ь₂ < . - - < Ь_к ^ Ь (1.2)

называется цепью. Цепь (1.2) называется максимальной или насыщенной, если в нее нельзя "вставить" ни одного элемента из В*.

Пример 1.2 Цепь С\ = {0,10,101} является максимальной, а цепь С₂ = {1,111}-нет.

Определение 1.2 Длина 1(C) конечной цепи С определяется равенством 1(C) — \С\ — 1.

Определение 1.3 Если а, 6 Є В*, то говорят, что элемент Ъ покрывает элемент а, если а < b и ни один элемент z Є В* не удовлетворяет условию а < z <Ь.

Определение 1.4 Элемент а Є В* называется максимальным (минимальным), если из того, что а ^ х (х ^ а), х Є В*, следует а = х.

Определение 1.5 Частично-упорядоченное множество (ч.у.

множество) Р = (М, ^) называется градуированным ранга п, если каоюдая максимальная цепь имеет одну и ту же длину п. В этом случае существует единственная ранговая функция р : В* —$ {0,1,...,п} такая, что р(а) = 0, если а - минимальный элемент В*, и р(Ь) = р{а) + 1, если b покрывает а в В*.

В нашем случае множество (5*, ^) является градуированным, и ранговая функция слова х Є В* - это просто длина слова х, т.е. р(х) = \х\.

По определению длина интервала [х,у], где х ^ у, - это максимальная длина цепи, принадлежащей этому интервалу, т.е. 1(х, у) = р(у) — р(х) =

\у\ - W-

Значительный интерес для последних исследований представляет мощность интервала [х,у]. Если

1, х^у, (я,2/) = {

О, если не так,

то имеет место стандартное представление

²(я,2/)= ]Г 1 = |[a?,j/]| = Card[x,y],

x^z^y

где свертка ²{х,у) определяется стандартным способом

f-g(x,y)= ^2 f(^xi^zM*>y):

x^z^y

или в нашем случае

²_{^х_{,у) = X) ^}^ж_' ^z_№^z_>^у_)-

Пример 1.3

а) Если х = Р, у = I⁵, то \[х,у]\ = q — р+ 1.

б) Если х = 0Р¹1⁹¹, у = {F²1^Q2 и pi < p₂, q\ < #2, то любой элемент

Интервала [Ж, у] ИМееТ ВИД О^І"², ГДЄ Р\ ^ V\ ^ >2, <7i ^ ^2 ^ #2-

Таким образом, искомое число равно (/ — Р\ + 1)(#2 —

Если опять обратиться к диаграмме Хассе, то мощность интервала [х,у] при х < у равна общему числу вершин, лежащих на всех путях, соединяющих х и у.

1.1.3 Мощность антицепей

Пусть В = {ai, 02,..., a_q} - g-ичный алфавит с частичным порядком "быть фрагментом" (^).

Определение 1.6 Антицепь есть подмножество А ч.у. мноэюества Р, в котором любые два элемента несравнимы.

Определение 1.7 Мощность антицепи V - число элементов в ней.

Пример 1.4 Рассмотрим в качестве примера множество всех бинарных слов длины п ^ 3 с частичным порядком "быть фрагментом". Множество В^^ъ состоит из следующих элементов: 0,1,00,01,10,11,000,001,010,011,100,101,110,111. В В^^ъ можно выделить, например, следующие антицепи:

а) \V\ = 2: {0,1}, {1,00}, {0,11}, {01, 111};

б) |V|=4: {00,01,10,11};

в) \V\ = 5: {00,011,101,110, 111}, {01, 000,100,110, 111};
r) \V\ = 8: {000,001,010,011,100,101,110, 111}.

1.1.4 Геометрические свойства диаграммы Хассе

Геометрия диаграммы Хассе частичного порядка "быть фрагментом" следующая:

а) Если вершина х лежит на к-м слое диаграммы Хассе, т.е. \х\ = к, то
из нее "исходит" ровно (к + 1)(д — 1) + 1 ребер.

б) Если вершина х лежит на к-м слое диаграммы Хассе, то в нее "входит"
ровно s(x) ребер, где s(x) - число серий слова х.

в) Если рассматриваются g-ичные слова длины ^ п, то максимальная
длина антицепи в этом множестве есть qⁿ и эта единственная
антицепь совпадает с верхним слоем диаграммы Хассе.

1.2 Бинарный алфавит

В главе 2 рассматриваются бинарные слова с определенными характеристиками, а именно: слова конечной длины с заданным весом Хэмминга. Рассматривая частичный порядок "быть фрагментом", мы находим для указанных слов соотношения для числа слов, содержащих слово в качестве фрагмента. Для найденного соотношения устанавливается связь с ранее известными фактами, а также предоставляется ряд следствий.

Хорошо известным фактом является то, что число слов конечной длины п, содержащих в качестве фрагмента данное слово а, не зависит от вида слова и определяется лишь его длиной ([4], [5]). Формально это утверждение выглядит следующим образом:

ад = (?). ()

где |<2| - длина слова а.

В главе 2 этот факт получает дальнейшее развитие. Принимая во внимание структурный состав слов (как самих слов ж, так и заданного фрагмента а), а также учитывая тот факт, что число слов, которые содержат данное слово а в качестве фрагмента, определяется только структурой фрагмента, мы находим точное соотношение для определения данного числа слов.

у—п—к

где FN(m,n, к) - число слов длины N и веса Хэмминга т, содержащих в качестве фрагмента произвольное слово а длины п и веса Хэмминга к.

Далее, в качестве следствия доказывается утверждение, отражающее связь с ранее известным фактом (1.3).

В терминах диаграммы Хассе условие (1.3) выражает число путей из вершины о диаграммы Хассе частичного порядка "быть фрагментом" до вершин, расположенных на п-м слое диаграммы Хассе. Найденное условие (1.4) позволяет среди числа таких путей понять, сколько путей идет к вершинам, имеющим определенный вес Хэмминга т.

1.3 g-ичный алфавит

В главе 3 частичный порядок "быть фрагментом" рассматривается в спичном алфавите. Как и для случая бинарного алфавита, находится число путей из вершины а диаграммы Хассе до вершин, расположенных на п-м слое диаграммы Хассе. Это число выражается в следующем утверждении.

Теорема 1.1 Справедливо соотношение

г—к ^ч '

|2Г1 = Ё(?)(в-¹)"-'. (1-5)

где к = \а\.

Используя далее серийное представление слов, мы находим следующий параметр диаграммы Хассе - степень "захода" вершины а. Это число оказывается равным числу серий в слове а. Данное утверждение формально отображено в следующей лемме.

Лемма 1.1 Справедливо соотношение

r(a) = s(a),

где s(a) - число серий слова а.

Найденное отношение позволяет определить число слов длины п над g-ичным алфавитом, имеющих ровно к серий. Это число определяется в следующей лемме.

Лемма 1.2 Число слов длины п над алфавитом В, имеющих ровно к серий, равно q(q — l)*^_1(jlj)

Используя результаты леммы 1.2, мы далее определяем производящую функцию, математическое ожидание и дисперсию случайной величины _п, равномерно распределенной на множестве В^п, где В - g-ичный алфавит, и равной числу серий слова х Є В^п. Данные величины определяются следующими утверждениями.

Лемма 1.3 Производящая функция F_n{z) случайной величины _п имеет вид

^) = ,(1 + ^-^-¹^. (1.6)

Следствие 1.1 Справедливы равенства:

q q^l

Если обозначить множество всех фрагментов g-ичного слова х Є В* через Т_х и рассмотреть слово х = 7^72² ---7^ ^{в ег0} серийном представлении, то можно найти верхнюю и нижнюю границу для числа фрагментом слова х.

Лемма 1.4 Справедливы неравенства

ti*2 ... *fc < И < (1 + *i)(l +1₂)... (1 + **) (1.7)

В главе 3 приводится аналог утверждения для функции F/v(m, п,/г) -числа слов длины N и веса Хэмминга га, содержащих в качестве фрагмента произвольное слово а длины п и веса Хэмминга к, для g-ичного алфавита. В случае g-ичного алфавита аналогом веса Хэмминга слова предлагается использовать понятие композиции слова, которая определяется следующим образом:

Определение 1.8 Пусть В = {ai, ^2,---, %} и а Є В*. Через Wk(a) мы обозначим число вхождений буквы а& в слово а. Тогда вектор w(a) = (wi_iW2, ,w_q) называется композицией слова а.

Вводя для g-ичного алфавита функцию F_n (a, wi,W2, ,w_q), которая определяет число слов длины п и заданной композиции w, содержащих в качестве фрагмента слово а, мы сначала доказываем по аналогии с бинарным алфавитом независимость данной функции от вида фрагмента а, т.е. F_n(a,w_uw_2l... ,w_q) = F_n(ti,t₂,... ,t_q,wi,w₂, . ,w_q), где w(a) = (ti,t2,... itq) - композиция слова a. Затем для функции F_n(ti, t₂,..., t_q, wi, W2-, , w_q) мы находим рекуррентное соотношение, которое отображено в следующей теореме:

Теорема 1.2 Справедливо рекуррентное соотношение

F_n{h,t₂,..., t_qt W_U w_2i..., w_q) =

⁼ Y1 2 \t -Ir _r)^Fn-y(Q>t2,-..,tq_iW₁-t₁,..._iW_q-r_q). (1.8)

y=*i r₂,...,r₉ ^ ^X ) 2» j g/

Индексы суммированияy,r₂,... ,r_q в (1.8) изменяются в тех пределах, для которых определены полиномиальный коэффициент и функция F_n-_y.

Используя полученные характеристики диаграммы Хассе частичного порядка "быть фрагментом" в теории антицепей, далее можно доказать теорему о мощности максимальной антицепи.

Теорема 1.3 Мощность максимальной антицепи ч.у. мноэюества (В^^п, ^) равна qⁿ, и эта единственная антицепь совпадает с верхним слоем диаграммы Хассе.

Длины цепей, соединяющих две вершины

Пусть В = {0,1} - двоичный алфавит, В - множество всех слов конечной длины над алфавитом В (пустое слово принадлежит В ). Длина слова х = (хі,Х2,-.., хп), ХІ Є В, - это число п букв в слове х. Длина слова х обозначается через ж, т.е. ж = п.

Расстоянием Хэмминга р(х,у) двух слов х = (хі,Х2,... ,хп) и у = ІУІ, У2, Уп) называется число позиций, в которых эти слова отличаются друг от друга. Например, если х = (0,1,1,0) и у = (1,1,1,0), то р(х, у) = 1.

Весом Хэмминга слова х называется число ненулевых жг-. Другими словами, вес Хэмминга - это число "единиц" в слове х. Вес Хэмминга обозначается через \\х\\. Например, если х — (0,1,1, 0,1,0), то \\х\\ = 3. Очевидно, что р(х, у) = \\х—у\\, т.к. обе части выражают число позиций, в которых различаются слова х и у. Фрагментом слова х = (х±,Х2,... ,хп) Є Вп называется произвольная подпоследовательность (ж , Х{2,..., Х{к) последовательности Отношение "быть фрагментом" задает на множестве В частичный порядок ( ), который можно записать в обычной форме а х если а есть фрагмент х. Пример 2.1 Пусть х = (0,1,1,1,0), ах = (0,1,1,0), а2 = (0,1,0,0), аз = (1,1,1). Тогда а\ х, а х, а3 х1 т.е. слова ai и аз являются фрагментами слова х, а слово а - не является. В процессе установления некоторых фактов далее будет использовано представление слов в виде серий, а именно где 7 Є В и 7 логическое отрицание 7- При этом говорят, что слово х состоит из т серий. Число U называется длиной г-й серии. Ясно, что справедливо следующее соотношение: т г=1 Пример 2.2 Если а; = (0,0,0,1,1,1,1,0), то х = 0 01. При этом, слово а: имеет 3 серии следующих длин: t\ = 3, 2 = 4, 3 — 1 Хорошо известен факт ([4], [5]), что число слов х Є Вп, содержащих в качестве фрагмента фиксированное слово а, зависит лишь от длины а и определяется соотношением В связи с данным фактом логично возникает следующая Проблема 1. Как связаны между собой характеристики рассматриваемого частичного порядка "быть фрагментом", а именно: длина слова а, вес Хэмминга слова а и число слов фиксированной длины и фиксированного веса Хэмминга, содержащих слово а в качестве фрагмента. Пример 2.3 Зафиксируем параметры частичного порядка "быть фрагментом". Пусть слово а имеет длину п и вес Хэмминга к. Пусть далее нас интересуют в качестве слов, для которых а является фрагментом, слова длины N и веса Хэмминга га. Тогда: - Если N = 4, т = 3, п = 2, к = 1, а — (0,1), то слово а в качестве фрагмента содержат следующие слова с заданными N и т: 1 = (0,1,1,1), х2 = (1,0,1,1), ж3 = (1,1,0,1), и, таким образом, число слов длины N = 4 и веса Хэмминга т = 3, содержащих в качестве фрагмента слово а = (0,1), равно 3. - Если N = 5, т — 3, п = 3, к — 1, а = (0,0,1), то слово а в качестве фрагмента содержат следующие слова с заданными N и га: 6 = (1,0,0,1,1), и, таким образом, число слов длины N = 5 и веса Хэмминга т = 3, содержащих в качестве фрагмента слово а — (0,0,1), равно 6. Необходимо отметить, проблема слов и их фрагментов довольно долгое время рассматривается в литературе ([2], [3], [7], [8], [12], [13], [16], [17]). Для поставленной проблемы 1 определения числа слов с заданными характеристиками, содержащих какое-то конкретное слово в качестве фрагмента, была предложена ([6]) рекуррентная формула для вычисления искомого числа слов и доказан существенный факт независимости указанного числа слов от вида фрагмента (результаты этого исследования будут изложены ниже). В настоящей работе поставленная проблема развита далее: предложена точная формула определения указанного числа слов, а также доказан ряд следствий. Прежде чем перейти к исследованию поставленной проблемы, необходимо привести описание одного из основных методов, который широко используется в комбинаторном анализе [1]. Производящей функцией числовой последовательности {a&}fc2 o называется ряд Две производящие функции А(ш) = X} akUk и В {и) = LJ Ь№к считаются равными тогда и только тогда, когда а& = 6 при всех к, \к\ 0. Обозначим через Н множество степенных рядов от ш над полем К действительных или комплексных чисел, содержащих лишь конечное число членов с отрицательными степенями. Множество Н будет кольцом по сложению и умножению.

Установление связи между характеристиками частичного порядка "быть фрагментом"

Пусть В — {ai, Gt2,..., aq} - g-ичный алфавит, В - множество всех слов конечной длины над алфавитом В (пустое слово принадлежит В ). Как и в бинарном случае, введем понятие фрагмента. Если a, b Є В и слово а может быть получено из Ъ удалением части букв, то говорят, что а есть фрагмент 6. Формально это определение звучит следующим образом.

Определение 3.1 Слово a = (аі,а:2,.. - , с ) в q-ичном алфавите В называется фрагментом q-ичного слова х = {х\ Х2,-.. хп), если последовательность « является подпоследовательностью жі, Ж2, , хп, т.е. а\а2 ...аіе — хігхІ2 ...хік.

Как и в двоичном случае, рассмотрим на множестве В отношение частичного порядка "быть фрагментом": если а есть фрагмент х. Степени "исхода" и "захода" на диаграмме Хассе частичного порядка (3.1) определяются числом решений неравенств Наряду с понятием фрагмента в комбинаторике слов широко используются и изучаются понятия подслова, префикса, суффикса. Определение 3.2 Слово х называется подсловом (соответственно, префиксом / суффиксом) слова у, если существуют слова а иЪ такие, что у = ахЬ (соответственно, у — хЪ / у — ах). Подслово (соответственно, префикс / суффикс) - собственное, если аЬ ф є (соответственно, Ь ф є / а фе). Необходимо отметить, что в исследованиях разных авторов названия одних и тех же понятий разнятся. Так, например, в монографии [17] вместо определенных выше понятий "подслово" и "фрагмент" используются термины "фактор" и "подслово" соответственно. Далее по тексту мы будем придерживаться введенной согласно определению 3.2 терминологии. Определим лексикографический порядок ( ). Определение 3.3 Слово х лексикографически меньше слова у (х у), если выполняется одно из следующих условий: - х - собственный префикс у; - существуют разлооїсения х — иах и у = uby , причем для букв а и Ъ выполняется условие а Ь. Лексикографический порядок - это обычный порядок упорядочивания по алфавиту, который применяется, например, в словарях. Перейдем к исследованию характеристик частичного порядка "быть фрагментом" для случая g-ичного алфавита. Проблема нахождения числа слов, содержащих заданное слово в качестве фрагмента, имеет большую важность с точки зрения ее приложения в теории информации. Эта проблема исследовалась ранее для двоичного случая (в том числе и в Главе 2 настоящей работы). В настоящем разделе поставленная проблема поиска числа слов, которые содержат фиксированное слово в качестве фрагмента, переносится на случай g-ичного алфавита. Решение, полученное в результате исследования, позволяет определить первый параметр диаграммы Хассе частичного порядка "быть фрагментом" - t(a) - степень "исхода" вершины а. Пусть В = {ai,a2,...,aq}, Вп = В х В х ... х Ву Пусть далее х Є п Вп, а Є Вк - слова в g-ичном алфавите В длины пик соответственно. Обозначим через Т: = {х Є Вп, х а} множество всех g-ичных слов длины п, которые содержат в качестве фрагмента заданное g-ичное слово а. Теорема 3.1 Справедливо соотношение Z—-K где к = \а\. Доказательство. Пусть а х. Рассмотрим множество М всех вхождений слова а в слово х в качестве фрагмента. Так как каждое такое вхождение задается последовательностью натуральных чисел (іі,І2,.. ,ik), то множество М можно лексикографически упорядочить. В соответствии с этим порядком произведем разбиение множества Т" на классы с одним и тем же минимальным вхождением фрагмента а. Эту минимальную последовательность обозначим через го, а соответствующий ей класс слов - через Т"(го). Таким образом, имеет место представление Пусть го = («і, «2,..., і к). Найдем мощность класса Т"(го). Рассмотрим разбиение интервала [1, тт.] точками набора го: Если х = (жі,Ж2,... ,хп) Є Т"(го), то распределение букв слова ж по интервалам (3.4) удовлетворяет следующим ограничениям. Пусть а = (аі,а2,... ,О;А;)- ПО определению го на местах с номерами из первого интервала (l,«i) в слове х может находиться любая буква, кроме «і, на местах с номерами из интервала (г і + 1, ) _ любая буква алфавита В, кроме а?2, и т.д. Последний интервал (ік + 1,п) заполняется произвольно. Из структуры этого распределения вытекает следующее выражение для мощности класса Т"(го):

Точное соотношение для F/v(m, п, к)

Доказательство. Пусть В—{0,1}. Пусть слово я; Є В%, и ж — т вес Хэмминга; слово а Є -В , и а = к - вес Хэмминга. Тогда в случае q = 2 имеем FN{tx,t2,w1,w2), где w;i+w2 = iV, i + 2 = п, G J = (4). и 2V-y(0, t2, «л - ь 2 - 2) = СД; -J Учитывая, что в случае q = 2 : t\ = п — к, t2 = к, w\ = N — т, w2 — га, получаем: ( v-i \ = (У-Л = ( у-1 \ ( N-y \(N-y\( N-y \ \w\ - ti, w2 - t2) \wi — ti) \N — m — n + kj Отсюда, переобозначая F/v(ii,h, u i,w2) = Fjsf(m,n, &), получаем (3.24). Пределы суммирования в (3.24) находятся, исходя из следующих соображений. Т.к. у - номер (п — к)-й слева позиции "нуля" в слове х, то подслово Х\... Ху содержит не менее (п — к) "нулей", что означает, что у п — к. С другой стороны, подслово xy+i ...хп содержит не менее, чем к "единиц". Таким образом, (N—y) — ((N—m) — (n—k)) к, т.е. у т+п—2к. Заметим, что формула (3.24) получена в Главе 2 настоящей работы. Следствие 3.5 Пусть В = {а\,а2,а%\, Пусть х Є Bn,w(x) = (wi:w2,ws), и пусть а Є Bk,w(a) = {h,t2,tz). Тогда справедливо равенство 2/1 - Л Л/1 - Л Л/2 - 2/1 -1 x . . ri J V h -1 J У1,У2,Г1,Г2 N Ч Fn(tht2,h,wuw2,w3) = ]P [f _i)[ х (уч — 2/1 — гЛ А п-уг \fn-y2-w1 + tl + r2\ . V r2 J \wi - h - r2) V w22-r1 ) Доказательство. Неравенство а а а . а1 а2 а3 можно "геометрически" представить в следующей форме. Пусть у\ - номер #1-й буквы а\ слева в слове х, а у2 - номер t2-B. буквы а2 слева в подслове хуі+і... хп слова х. Тогда: а) Подслово х\.. #Уі-і содержит (ti — 1) букв а\, г\ букв а2 и {у\ — t\ — 7 1) букв а . Согласно (3.15), число слов х\...#Уі-і определяется полиномиальным коэффициентом (. 1 У1 . ). б) Подслово хУі+і... хУ2-1 содержит г2 букв ai, ( 2 — 1) букв а2 и {у2—у\ — t2—7 2) букв (. Согласно (3.15), число слов а Уі+і... жУ2-і определяется полиномиальным коэффициентом ( , У2 У1 V в) Подслово жУ2+і.. -хп содержит (wi — t\ — 7 2) букв ai, (w2 — t2 — Г\) букв a2) (ги3 — т/2 + i + t2 -f n + r2) букв a3. Согласно (3.15), число слов Ху2+\... хп определяется полиномиальным коэффициентом ( П-У2 \ \Wii — r2,W22-ri,W3-y2+h+t2+ri+r2 Из а), б) и в) следует, что число решений неравенства а а22а а1 а2а3 определяется следующим выражением: п( 1 25 з,гУьгУ2,гУз) = = У ( У1 1 )( 2/2-2/1-1 \ т Ґ, го V 1 2/1 - 1 - Г1/ 4 2 — 1,2/2 — 2/1 — 2 — П / х( В_й V (3.26) \гні - іі - r2, w22- гь гу3 - 2/2 + i + 2 + П + V Далее, Vti-l.ri.j/ii-rJ V i-lA ri У v ; ( 3/2-2/1-1 \ = (у - v\ - Л /г/2 - г/1 - ,3 28ч V"2, 2 - 1,2/2 - 2/1 - 2 - Г2/ \ 2 - 1 / \ 2 У / тг - 2/2 \ _ \wi -h- r2, w22- ri, ги3 - 2/2 + i + 2 + П + r2/ / n - г/г \fn y2-wi + tl + r2\ \wi -h-r2J\ w22-n J Из (3.26), (3.27), (3.28) и (3.29) следует (3.25). Индексы суммирования у і, у2, ri, г2 в (3.25) изменяются в тех пределах, для которых определены биномиальные коэффициенты. 3.6 Примеры Использование формулы (3.21), как и формулы (3.25), более трудоемко по сравнению со случаем бинарного алфавита (формула 2.14). Приведем пример использования формулы (3.25) при заданных композициях слов х и фрагмента а. Пример 3.3 Пусть В = {О,1,2} - троичный алфавит и х Є В4, а Є В3, w(x) = (1,1,2) и w(a) = (1,1,1). Тогда: F4(l,l,l,l,l,2) = J2 ( г/1 -1\ (у\ - Л Л/2 - 2/1 - 1ч х 0 ) V J"i J V г2 У -Г)(4 -Г2)= т.к. единственное значение переменных ri и Г2, при котором имеют смысл биномиальные коэффициенты, есть 0. Далее, исходя из определения переменных 2/1 и у2 как номеров 1-й позиций 0 и 1 в словах Жіж2#з#4 и +1--- 4, получаем: 2/1 = 1,2 и 2/2 = 1,3 — 2/1- Окончательно: 2 З-2/i F4(l, 1,1,1,1,2) = 535-)1 = 3. 2/1=12/2=1 Действительно, в качестве фрагмента в примере 3.3 можно взять слово а = 012. Тогда словами х длины п = 4 и композиции w(x) = (1,1,2), содержащими слово а в качестве фрагмента, являются следующие слова: 0122, 0212, 2012.

Число слов, содержащих в качестве фрагмента фиксированное слово

Еще одним понятием, связанным с частичным порядком "быть фрагментом", являются антицепи и их мощность. Определение 3.7 Антицепь есть подмножество А ч.у. мнооюества Р, в котором любые два элемента несравнимы. Рассмотрим алфавит В = {ai, Z2,... ,ад} и все слова х є В п с отношением частичного порядка "быть фрагментом". Другими словами, мы рассматриваем все д-ичные слова длины, меньшей или равной п. Как было показано ранее, диаграмма Хассе частичного порядка "быть фрагментом" обладает следующими геометрическими свойствами. а) Степень "исхода" вершины а длины к на диаграмме Хассе частичного порядка "быть фрагментом" равна (к + 1)(# — 1) + 1. б) Степень "захода" вершины равна числу серий слова а. Теорема 3.4 Мощность максимальной антицепи ч.у. мнооюества (В п, ) равна qn, и эта единственная антицепь совпадает с верхним слоем диаграммы Хассе. Доказательство. Пусть В1, Б2,..., Вп - все "слои" множества В п и п антицепь V = \J V{, где V{ С Вг, і = 1,п. Пусть х Є 14 и 14 - первое непустое из множеств V{. Рассмотрим множество всех стрелок, идущих из точек множества Vk в слой Вк+1. Тогда общее число стрелок, идущих "вверх" из элементов Vk, равно Т41((/: + l)(q — 1) + 1). Оценим теперь число "образов" (или концов) этих стрелок на Вк+1, которое обозначим через Vk +V Множество всех стрелок, идущих "вниз" из точек Vk +V включает все стрелки, ведущие "вверх" из Vk, т.е. \Vk\((k + l)(g - 1) + 1) 5Z s« ( + г)\ук+і1 С3-30) где s(y) - число серий у слова у, и "верхняя" граница для s(y) равна s(y) \у\ = к + 1. Из неравенства (3.30) следует \Vk +\\ \Vk\ (q - ) \Vk\(q 1) \Vk\, q 2. (3.31) Сделаем теперь следующие преобразования с антицепью V: на слое Bk+l возьмем все вершины Vk v содержащие хотя бы одну из вершин Vk в качестве фрагмента, и рассмотрим новое множество V = (V\Vk) U +r Другими словами, вместо Vk включим в V все точки из Vk С Вк+1. Тогда: а) V - антицепь. Действительно, если у z для у Є V i и z Є V, то, выбрав для у его образ у из 14, получим: у У z, т.е. у z, что противоречит исходному предположению у , z Є V. 6) \V \ \v\. Данное условие вытекает из неравенства (3.31). Применяя определенные выше преобразования столько раз, сколько это возможно, мы придем к f?n, т.е. V \Вп\ = qn. Из приведенных выше рассуждений вытекает также, что Вп является единственной антицепью максимальной мощности в (? п, ), что и требовалось доказать.

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

Роль несобственных параметров порядка в феноменологической теории фазовых диаграммСергиенко Иван Александрович

Особенности фазовых диаграмм и аномалии свойств при фазовых переходах, описываемых несколькими параметрами порядка Кладенок Лариса Александровна