О.Б. Лупанов - Курс лекций по дискретной математике, страница 5

. . .14(62)Приравнивая коэффициенты при подобных членах, получаемXpk =mIm .(63)m|kВыведем сначала несколько простых следствий.1◦ Без всяких формул ясно, что Ik > 0.2◦ Ясно, что I1 = p (это многочлены вида x + a, a = 0, . . . , p − 1).kk3◦ Из 2◦ и (63) сразу следует, что при k > 2 имеем Ik 6 p k−p < pk .4◦ Заметим, что если k — простое число, то слагаемых в сумме всего два, поэтому Ik =5◦ Получим оценку снизу для чисел Ik :pk = kIk +X!mIm < kIk +k/2Xpk −pk .pm < kIk + pk/2 + 1.(64)m=0m|km<kЗдесь переход «!» следует из оценки, полученной в 3◦ . Стало быть,Ik >pk − pk/2+1.k(65)6◦ Из неравенства, полученного в 5◦ , следует, что Ik > 0, то есть существуют неприводимые многочленылюбой степени.Замечание. В курсе алгебры обычно доказывается, что над конечными полями существуют неприводимыемногочлены сколь угодно высокой степени.

Мы получили некоторое усиление этого утверждения, правда, недля всех конечных полей, а только для полей Fp .Мы ещё получим явную формулу для вычисления Ik , но для этого нам потребуется одна формула, оченьполезная в борьбе с производящими функциями.1.3.5. Формула обращения МёбиусаПусть f, g : N → R.mk1Определение. Пусть n = pm— разложение числа n на простые множители. Функция1 · . . . · pkn = 1,1,µ(n) := (−1)k , m1 = · · · = mk = 1,0иначе.(66)называется функцией Мебиуса.Лемма 1.22.Xµ(d) =d|n(1,0n = 1,иначе.mk1При n = 1 доказывать нечего. Пусть теперь n = pmb = p1 · .

. . · pk . Тогда1 · . . . · pk , а nXXXµ(d) +µ(d).µ(d) =d|nd|bn(67)(68)d|nd∤bnВторая сумма равна нулю, потому что если d|n и d ∤ nb, то у d есть делители в степенях, больших 1. А перваясумма соответствует неповторяющимся простым делителям. Количество слагаемых для s делителей, очевидно,равно Csk . Значит,Xµ(d) = 1 − C1k + C2k − C3k + · · · = (1 − 1)k = 0.(69)d|bnИтак, обе суммы в этом случае равны нулю, и лемма доказана. Теорема 1.23 (Формула обращения Мёбиуса). Если для всех n выполнено равенствоXf (n) =g(d),d|n15(70)тоg(n) =Xµ(d)fd|nnd(71).Для всякого делителя d числа n имеемfnd=Xbnd|dbg(d).(72)ОтсюдаXµ(d)fd|nnd=Xd|nµ(d)Xbnd|db =g(d)Xbd,db: dd|nb =µ(d)g(d)XXb d| nbd|ndb =µ(d)g(d)потому что в силу леммы выживет только то слагаемое, для которогоndbXbd|nbg(d)Xµ(d) = g(n),(73)d| nbdb = 1, то есть когда n = d.Следствие 1.3 (Формула для количества приведённых неприводимых многочленов).Ik =1Xµ(m)pk/m .k(74)m|kВ предыдущем разделе мы установили формулуXpk =mIm .(75)m|kПрименим формулу обращения к функциям f (k) = pk и g(k) = kIk .

ПолучимXkIk =µ(m)pk/m ,(76)m|kи осталось только разделить это равенство на k. 1.3.6. Тождества НьютонаСейчас мы применим технику работы со степенными рядами над кольцом K[α1 , . . . , αn ], где K — поле. Этотстрашный объект обозначается, ясное дело, K[α1 , . . . , αn ] [x] .Напомним, что многочлен f ∈ K[α1 , . . . , αn ] называется симметрическим, если он инвариантен относительнолюбых перестановок его переменных.Определим степенные суммы: Sk := αk1 + . . . + αkn .

Напомним, что элементарные симметрические многочленыот n переменных имеют видσ1 = −(α1 + . . . + αn ),σ2 = α1 α2 + α1 α3 + . . . ,...Xσk = (−1)kαi1 · . . . · αik ,(77)i1 ,...,ik...Рассмотримσn = (−1)n α1 · . . . · αn .S(x) =∞XSi xi .(78)k=1Рассмотрим многочленσ(x) = (1 − α1 x)(1 − α2 x) · .

. . · (1 − αn x) = 1 +Применим формулу логарифмического дифференцирования:nnk=1k=1nX(79)k=1Dσ(x) X D(1 − αk x) X −αk==.σ(x)1 − αk x1 − αk x16σk xk .(80)Домножая на x это равенство, получаемn xDσ(x) X1=1−.σ(x)1 − αk x(81)1= 1 + αp x + α2p x2 + α3p x3 + . . .

,1 − αp x(82)k=1Мы знаем, чтопоэтому1−откудаn Xk=11−11 − αk x1= −(αp x + α2p x2 + α3p x3 + . . . ),1 − αp x= − (α1 + . . . + αn )x + (α21 + . . . + α2n )x2 + . . . = −S(x).(83)(84)Комбинируя эту формулу с формулой (81), получаем, чтоS(x)σ(x) + xDσ(x) = 0.(85)Но продифференцировать многочлен σ(x) очень легко:xDσ(x) =nXkσk xk ,(86)k=1и окончательно получаем тождествоS(x)σ(x) =nXkσk xk .(87)k=1Приравнивая коэффициенты при степенях x, получаем формулы0 = S1 + σ1 ,0 = S2 + S1 σ1 + 2σ2 ,0 = S3 + S2 σ1 + S1 σ2 + 3σ3 ,...(88)0 = Sn + Sn−1 σ1 + Sn−2 σ2 + . .

. + S1 σn−1 + nσn ,...0 = Sn+i + Sn+i−1 σ1 + . . . + Si σn .Эти соотношения называются формулами Ньютона.Следствие 1.4. В случае, если char K = 0, многочлены σi выражаются через степенные суммы.Следствие 1.5. Всякий симметрический многочлен однозначно выражается через степенные суммы.1.3.7. Что ещё можно делать со степенными рядами?Так вот, степенные ряды так и тянет подставить один в другой.

Разберёмся, когда это можно делать.Пусть у нас есть ряд A(x), и мы хотим подставить в него ряд B(x). Ясно, что если B(0) 6= 0, то всё плохо:нулевой коэффициент результирующего ряда является бесконечной суммой, что не есть хорошо. Поймём теперь,почему в случае, когда B(0) = 0, всё будет хорошо.Действительно, если B(0) = 0, то deg∗ B(x)n > n → ∞ при n → ∞, поэтому со сходимостью ряда∞ XA B(x) =an B(x)nn=0проблем не будет.Пример 3.3. В качестве примера рассмотрим последовательность Фибоначчи. . .17(89)1.3.8.

Принцип включений и исключенийПусть имеются объекты x1 , . . . , xN и свойства p1 , . . . , pn . Через E(m) будем обозначать число объектов,обладающих ровно m свойствами, а через w(p1 , . . . , pk ) — число объектов, обладающих свойствами p1 , . . . , pk .ПоложимXW (k) :=w(pi1 , . . . , pik ).(90)(i1 ,...,ik )Утверждение 1.24. Имеет место формула для числа объектов, не обладающих никаким свойством:E(0) = N − W (1) + W (2) − W (3) + . . . + (−1)n W (n).(91) Рассмотрим два случая.

1◦ Пусть x1 не обладает никаким свойством. Тогда в левую часть формулы ондобавит единицу. А справа будем считать, что его единица входит в число N . 2◦ Пусть x1 обладает свойствамиpi1 , . . . , pik . Тогда вклад в левую часть есть 0. А в правую — 1 − C1k + C2k + . . . + (−1)k Ckk = (1 − 1)k = 0. 2. Кодирование2.1. Общая теория кодирования и сжатия информации2.1.1. Схемы кодирования. Коды с однозначным декодированиемПусть заданы два алфавита A = {a1 , . . . , ar } и B = {b1 , .

. . , bq }.Определение. Слово в каком-либо алфавите — это конечный упорядоченный набор символов этого алфавита. Множество всех слов алфавита A мы будем обозначать A∗ .Определение. Схема кодирования — это любое отображение ϕ : A → B ∗ , ϕ : ai 7→ Bi . Образ символа притаком отображении будем называть кодом этого символа.Такое отображение очевидным образом распространяется на множество всех слов над алфавитом A:(1)ai1 . . .

ais 7→ Bi1 . . . Bis .Пример 1.1. A = {a1 , a2 , a3 } , B = {0, 1}. Схему кодирования зададим следующим образом:a1 7→ 01,a2 7→ 010,(2)a3 7→ 101.Исходному слову a1 a1 a1 будет соответствовать кодовое слово 010101.Определение. Будем говорить, что некоторая схема кодирования допускает однозначное декодирование, если кодовые слова (то есть результаты кодирования) различны для любых несовпадающих кодируемых наборов.Нетрудно заметить, что схема кодирования в предыдущем примере не допускает однозначного декодирования, так как кодовое слово 010101 соответствует одновременно двум наборам — a1 a1 a1 и a2 a3 .2.1.2.

Неприводимые словаОпределение. Префиксной называют такую схему кодирования, в которой код ни одного из символов входного алфавита не является началом для кода другого символа.Замечание. Это условие является достаточным для однозначности декодирования, но не необходимым. Вкачестве примера можно рассмотреть схему a 7→ 0, b 7→ 01. Ясно, что это не префиксный код, но тем не менеедекодирование однозначно.Определение.

Слово, допускающее неоднозначное декодирование, называют неприводимым, если при удалении из него каких-либо символов полученное слово либо не является кодовым (то есть не допускает декодирования вообще), либо допускает только однозначное декодирование.Очевидно, что любой код, допускающий неоднозначное декодирование, содержит неприводимые слова.Определение.

Рассмотрим некоторое кодовое слово b1 . . . bm , допускающее неоднозначное декодирование.Схематически это можно изобразить следующим образом:ai1aj1ai2aj2ai3aj3ai4aj4ai5aj5Рис. 6. Примеры слов18aj6ai6aj7aj8ai7aj9Рассмотрим разбиение, полученное объединением верхнего и нижнего разбиений, получим набор отрезков.Если отрезок одного декодирования целиком содержится в некотором отрезке другого (как aj6 и aj8 на нашей схеме), его называют отрезком первого рода, иначе, то есть если он является началом отрезка при одномдекодировании и концом при другом (как пересечение отрезков ai4 и aj5 на рисунке) — отрезком второго рода.Лемма 2.1 (О неприводимом слове). В неприводимом слове все отрезки второго рода различны.

Предположим противное: пусть нашлось два одинаковых отрезка второго рода. Имеются четыре возможности их расположения:а)в)б)г)Рис. 7. Возможные расположения верхних и нижних словРазберем случай а), а для остальных случаев рассуждения аналогичны. Совпадающие отрезки второго родавыделены штриховкой. Удалим из слова все символы от начала первого отрезка до начала второго, и «склеим»оставшиеся слова. Полученное таким образом слово также будет допускать неоднозначное декодирование, а этопротиворечит предположению о том, что исходное слово было неприводимым.

2.1.3. Проверка однозначности декодированияМы хотим получить алгоритм проверки однозначности декодирования. Именно, эта процедура будет выглядеть примерно так: проверяем однозначность декодирования кодов, полученных из слов алфавита A длины неболее N , где N зависит только от схемы кодирования, и если это так, то заключаем, что и вся схема однозначна.Рассмотрим следующую схему кодирования: исходный алфавит A = {a1 , . . .

, ar }, конечный алфавит B, состоящий из q символов, причем каждому символу ai ∈ A ставится в соответствие слово Bi ∈ B ∗ длины li .Обозначим l := l1 + . . . + lr .Ясно, что нужно проверять только неприводимые слова. Сейчас мы покажем, что длина неприводимогослова ограничена константой. Её-то и возьмём в качестве числа N .Зафиксируем некоторое слово и его код, и мы хотим выяснить, может ли этот код быть неприводимымсловом.

Вначале убедимся, что оно допускает по крайней мере два декодирования. Потом выпишем оба декодирования, как на рис. 6.Под кодовым словом (или просто словом) будем понимать код символа. Посчитаем максимальное числокодовых слов одного декодирования, которые одновременно попадают внутрь некоторого слова другого декодирования (см. рис. 8)Рис. 8. Слова́ внутри другого сло́ва.