В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Большая из этих трех вершин лежит в Bn10 . Тогда дополнением до квадрата, как легко видеть, будетслужить максимальная вершина соответствующей укороченной цепи.Bn+1`caBn10`acca``aa``aa``acBn+111a`a``aa`a``aПоскольку при индуктивном построении сначала обе цепи были одной длины, а затем первая из нихстала на одну вершину длиннее, а вторая — на одну вершину короче, то условие и в этом случае выполняется.Теорема доказана.Используя теорему Анселя можно получить верхнюю оценку на число монотонных булевых функций ψ (n). Действительно, покроем Bn цепями Анселя. Рассмотрим все цепи Анселя наименьшей длины (это либо 1, либо 2).

Определим на них не более, чем тремя способами монотонную функцию. Затем, возьмем на больших цепях (длины n − 2p + 1)три наименьшие вершины. Зная значения на всех цепях длины, не более, чем n − 2 (p + 1) + 1 по монотонности дополним их до квадрата и определим на них снова не более, чем тремя способами монотонную функцию. При этом, на всехвершинах, кроме двух функция определится однозначно, а на оставшихся останется как раз ровно три варианта.

Такимобразом, суммируя полученные результаты относительно ψ (n), можно утверждать, что( nn )( nn )( nn )2 b 2 c + 2 b 2 c+1 − 1 6 ψ (n) 6 3 b 2 c .Также можно показать, что ранее полученная нижняя оценка на сложность расшифровки монотонной булевойфункции ϕ (n) совпадает с верхней оценкой. Действительно, в случае нечетного n сначала узнаем значения на цепяхдлины 2 (при этом зададим не более, чем по два вопроса на каждую цепь). Затем, используя снова продолжения доквадрата, узнаем значения на цепях большей длины (при этом зададим снова не более чем по два вопроса для каждойцепи).

Итак, для нечетного случая nnnϕ (n) 6 2 · n = n + n .222 +1В четном случае узнаем сначала значения функции на цепях длины 1, задав по одному вопросу для каждой цепи. Затем,для цепей большей длины узнаем значения не более, чем на двух вершинах, используя продолжения до квадрата. Такимобразом, и в этом случае ϕ (n) не превосходит своей нижней оценки: nnnnnnnϕ (n) 6 1 ·−+2·=+=+.nnnnnnn22 −12 −122 −122 +1511.4. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВАИтак, окончательно можно утверждать, что nn+ n.ϕ (n) =n22 +1Алгебры инцидентности. Частичный порядок (P, 6) будем называть локально конечным, если любой интервалконечен. Пусть в дальнейшем F — некоторое бесконечное поле.Определение 1.4.13.

Алгеброй инцидентности частично упорядоченного множества (P, 6) называется множествоA (P) = f : P2 → F x y ⇒ f (x, y) = 0 .Алгебра инцидентности замкнута относительно операции сложения:( f + g) (x, y) = f (x, y) + g (x, y) ,операции умножения на число r ∈ F:(r · f ) (x, y) = r · f (x, y) ,а также операции свертки( f ? g) (x, y) =∑f (x, z) · g (z, y) .x6z6yНейтральным элементом по сложению является функция, тождественно равная нулю и очевидным образом принадлежащая алгебре инцидентности.

Свертка ассоциативна: f ? (g ? h) = ( f ? g) ? h. Действительно,( f ? (g ? h)) (x, y) =∑f (x, z) · (g ? h) (z, y) =x6z6y=∑x6z6y∑ ∑∑f (x, z)∑x6w6yg (z, w) · h (w, y)z6w6yf (x, z) · g (z, w) · h (w, y) =x6z6y z6w6y=!∑ ∑f (x, z) · g (z, w) · h (w, y)x6w6y x6z6y∑!f (x, z) · g (z, w) · h (w, y) =x6z6w∑( f ? g) (x, w) · h (w, y) = (( f ? g) ? h) (x, y) .x6w6yВ то же время операция некоммутативна. Действительно, пустьx l y, f (x, x) = f (x, y) = 0, f (y, y) = e, g (x, y) = a, где a ∈ F, e 6= 0.Тогда( f ? g) (x, y) = f (x, x) · g (x, y) + f (x, y) · g (y, y) = 0,(g ? f ) (x, y) = g (x, x) · f (x, y) + g (x, y) · f (y, y) = a2 6= 0.Последнее равенство вытекает из того, что в поле нет делителей нуля.Из определения свертки легко видеть, что она дистрибутивна относительно сложения:( f + g) ? h = f ? h + g ? h,f ? (g + h) = f ? g + f ? h.Нейтральной функцией по свертке будет дельта-функция: ∀ f ∈ A (P) ⇒ f ? δ = δ ? f = f , где(1, x = y,δ (x, y) =0, иначе.Иногда можно говорить об обратных элементах по свертке fΛ−1 и fΠ−1 (соответственно левом и правом обратных элементах), если fΛ−1 ? f = δ и f ? fΠ−1 = δ .

Не всякий элемент алгебры инцидентности имеет обратный, однако если он всеже существует, то левый обратный совпадает с правым обратным элементом:fΛ−1 = fΛ−1 ? δ = fΛ−1 ? f ? fΠ−1 = fΛ−1 ? f ? fΠ−1 = δ ? fΠ−1 = fΠ−1 .Теорема 1.12. Элемент f ∈ A (P) обратим тогда и только тогда, когда для любого x ∈ P выполняется f (x, x) 6=0.52ГЛАВА 1. КОМБИНАТОРИКА Док-во. Необходимость в данном случае очевидна: если f ∈ A (P) обратим, тоf −1 (x, x) · f (x, x) = 1по определению операции свертки и дельта-функции. Поскольку в поле нет делителей нуля, для любого x ∈ P выполняется f (x, x) 6= 0.Покажем достаточность.

Для этого определим для функции f обратную явным образом. Если x y, очевидно, опре1делим f −1 (x, y) = 0. Поскольку для любого x выполняется f −1 (x, x)· f (x, x) = 1 и f (x, x) 6= 0, определим f −1 (x, x) = f (x,x).Пусть теперь x < y и для любого z ∈ [x, y) обратная функция f −1 (x, z) уже определена. Тогда по определению свертки∑f −1 (x, z) · f (z, y) = δ (x, y) = 0 =⇒ f −1 (x, y) = −x6z6y1∑ f −1 (x, z) · f (z, y) .f (y, y) x6z<yПопутно доказано, что обратный элемент, если он существует, единственен.Теорема доказана.Перечислим теперь наиболее важные функции алгебра инцидентности.(1, x = y,1.

δ (x, y) =0, иначе.(1, x 6 y,2. ζ (x, y) =— дзета-функция.0, иначе(1, x = y, x l y,3. λ (x, y) =— лямбда-функция.0, иначе(1, x < y,4. η (x, y) = ζ (x, y) − δ (x, y) =— эта-фунция.0, иначе(1, x l y,5. κ (x, y) = λ (x, y) − δ (x, y) =— каппа-функция.0, иначе6. µ (x, y) = ζ −1 (x, y) — функция Мебиуса.7. ` (x, y) — длина максимальной (x, y)-цепи.Введем понятие монотонной нумерации частичного порядка. Нумерацией частично упорядоченного множества(P, 6) называется отображение n : P → N. Нумерация называется монотонной, если из p1 6 p2 следует n (p1 ) 6 n (p2 ).Алгоритм монотонной нумерации произвольного конечного частичного порядка чрезвычайно прост: на первом шагевыбираем произвольный минимальный элемент и нумеруем его единицей.

Затем, на каждом последующем шаге выбираем элемент, ниже которого лежат только помеченные элементы, и нумеруем его следующим натуральным числом.Очевидно, выполняется x < y ⇒ n (x) < n (y). Рассмотрим это на примере. Пусть P = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, а отношение частичного порядка задается диаграммой Хассе, представленной на рисунке.7a`A10a`@4 a`A @a` 9A Aa`A6a` Aa`3@ 8A@a`Aa`2@5@a`1Вершины частичного порядка пронумерованы, как легко проверить, монотонно. Важнейшим свойством монотоннойнумерации является то, что матрицы введенных нами ранее функций имеют верхний треугольный вид.

Так например,531.4. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВАматрица дзета-функции выглядит так (номера строк соответствуют номерам x, а номера столбцов — номерам y в монотонной нумерации):1 1 1 1 1 1 1 1 1 10 1 1 1 0 1 1 0 0 10 0 1 1 0 0 1 0 0 00 0 0 1 0 0 1 0 0 00 0 0 0 1 1 1 1 1 1ζ =0 0 0 0 0 1 1 0 0 10 0 0 0 0 0 1 0 0 00 0 0 0 0 0 0 1 1 10 0 0 0 0 0 0 0 1 10 0 0 0 0 0 0 0 0 1Также можно найти матрицу функции Мебиуса, которая также будет иметь верхний треугольный вид:1 −1 00 −1 100000 1 −1 00 −1 10000 01 −1 0000000 00100 −1 0000 0001 −1 0 −1 01µ =0001 −1 00 −10 00 0000010000 0000001 −1 0 0 00000001 −10 000000001Пусть частично упорядоченное множество (P, 6) локально конечно и имеет наименьший элемент. Пусть F : P → F— некоторая функция, определенная на этом частичном порядке.

Предположим, что вместо F известны значениясуммирующей функции:SF (x) = ∑ F (y) .y6xЗадача заключается в расшифровке исходной функции по известным значениям суммирующей функции. Задача решается следующим образом: введем новую функцию(F (z) , x = 0, y = zf (x, y) =0,иначе.Выполним свертку этой функции и дзета-функции:SF (x, y) =∑f (x, z) · ζ (z, y) = ( f ? ζ ) (x, y) .x6z6yОчевидно, что SF (0, x) = SF (x). Поскольку дзета-функция обратима, и обратной к ней является функция Мебиуса,можно выполнить следующую операцию, приводящую к обращению Мебиуса: f (x, y) = (SF ? µ) (x, y).

Отсюда получаем основную формулу, определяющую значения F через значения суммирующей функции:F (x) = f (0, x) =∑ SF (0, y) · µ (y, x) = ∑ SF (y) · µ (y, x) .y6xy6xРассмотрим конечный алфавит {a1 , . . . , ar } , r > 2. Построим все rn слов над этим алфавитом длины n и разобьемиз на классы эквивалентности. Прежде всего определим понятие периода: слово (b1 , . .

. , bn ) имеет период d|n, если длялюбого i выполняется bi = bi+d (i + d (mod n)) и для любого d 0 < d это неверно. Классом эквивалентности являетсямножество слов, получающихся одно из другого циклическим сдвигом.Рассмотрим пример: пусть r = 2, n = 4. Всего существует 16 слов длины 4 над двухбуквенным алфавитом (пусть это{0, 1}). Два из них имеют период 1: это (0000) и (1111), два слова имеют период 2: это (0101) и (1010), остальные жеслова имеют период 3. Всего 6 классов эквивалентности:(0000)(1111)(0101) , (1010)(0001) , (1000) , (0100) , (0010)(0011) , (1001) , (1100) , (0110)(0111) , (1011) , (1101) , (1110)54ГЛАВА 1.

КОМБИНАТОРИКАОбозначим через M (d) число классов эквивалентности слов периода d. Так, для r = 2, n = 4 M (1) = 2, M (2) =1, M (4) = 3. Нас будет интересовать вопрос, чему же равно M (n). В данном случае легко построить суммирующуюфункцию, после чего можно выполнить обращение Мебиуса:nn∑ d · M (d) = rn =⇒ M (n) · n = ∑ rd · µ (d, n) = ∑ rd · µ d = ∑ r d · µ (d) .d|nd|nd|nd|nОтсюда получаем окончательную формулуM (n) =n1r d µ (d) .n∑d|nЭто число замечательно тем, что оно равно числу неприводимых нормированных многочленов степени n над Fp [x], еслитолько r = p — простое.

Характеристики

Список файлов книги