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

Если для какого-то множества Aeграфе неравенство нарушится, то оно нарушится и для A0 ∪ A в исходном графе. Значит, можно применитьпредположение индукции по-отдельности к множеству A0 и к его «дополнению». 1.3. Формальные степенные ряды и производящие функцииПроизводящие функции — это замечательный инструмент для того, чтобы что-нибудь посчитать. Чтобыиметь возможность что-либо про них говорить, нам нужны формальные степенные ряды.1.3.1.

Формальные степенные рядыПусть K — кольцо с 1. Рассмотрим последовательность {ai } ⊂ K. Построим формальное выражение∞Pai xi .i=0Его мы будем называть формальным степенным рядом над кольцом K. Множество формальных степенных рядов над кольцом K будем обозначать K [x] . Введём на этом множестве структуру кольца. Определим сложение степенных рядов естественным образом, а именно, если(A + B)(x) =∞X(ai + bi )xi , где A(x) =i=0∞Xai xi ,i=0B(x) =∞Xbi xi .(20)i=0Произведение определим так: будем говорить, что C(x) = A(x) · B(x), если коэффициенты ряда C(x) определяkPются по формуле ck =ai bk−i .

Два ряда будем называть равными, если у них равны все коэффициенты приi=0соответствующих степенях. Итак, мы получили кольцо формальных степенных рядов с единицей.Заметим, что подстановка вместо переменной x какого-либо значения вообще лишена смысла. Однако удобносчитать, что подстановка нуля даёт коэффициент a0 , поэтому будем по определению считать, что A(0) = a0 для∞Pстепенного рядаai xi .i=0Отметим простые свойства полученного кольца.

• Если кольцо K было ассоциативным (коммутативным), то кольцо K [x] тоже будет ассоциативным (коммутативным). • Если в K нет делителей нуля, то их нет и в K [x] .Замечание.Эти свойства, очевидно, выполнены и в обратную сторону, поскольку K является подкольцом в K [x] .Далее мы будем считать, что K — ассоциативное коммутативноекольцо с 1 и без делителей нуля, то есть область целостности. Выясним, какие элементы в кольце K [x] обратимы.Определение.

Если A(x) · B(x) = 1, то говорят, что B = A−1 .Утверждение 1.18. Ряд A(x) обратим тогда и только тогда, когда A(0) обратим в кольце K. Попробуем найти коэффициенты ряда B(x) := A−1 (x) в явном виде. Для этого приравняем коэффициенты:a0 b0 = 1,a0 b1 + a1 b0 = 0,(21)...a0 bk + . . .

+ ak b0 = 0,Ясно, что эта система разрешима тогда и только тогда, когда a0 обратим в кольце K — в этом случае всекоэффициенты последовательно выражаются через предыдущие:bk = −a−10 (a1 bk−1 + . . . + ak b0 ),(22)что и требовалось доказать. Следствие 1.2.

Если K — поле, то обратимые элементы — это ряды с ненулевым свободным членом.Пример 3.1.1.(23)1−xЗаметим, что это чисто алгебраический результат. Никаких геометрических прогрессий мы здесь не суммируем.(1 + x + x2 + x3 + . . .) =10Определение. Пусть дана последовательность {ai }. Производящей функцией этой последовательности называется формальный ряд∞Xai xi .(24)i=0Биномиальные коэффициенты. Пусть x1 , . . . , xn — формальные объекты. Пусть X = {x1 , .

. . , xn }. Рассмотрим всевозможные k-элементные подмножества в множестве X. Это всевозможные выборки xi1 , . . . , xik .Выпишем соответствующую производящую функцию:(1 + x1 ) · (1 + x2 ) · . . . · (1 + xn ) =n X YX(25)xj .k=0 S⊂X xj ∈S|S|=kЧто такое произвольное подмножество в X? Всякий элемент xk либо входит в него (этому соответствует слагаемое xk в соответствующем множителе), либо не входит (этому соответствует слагаемое 1). А теперь, посколькунас интересует только количество k-элементных подмножеств, можно подставить xi = x и получить искомуюпроизводящую функцию:nX(1 + x)n =Ckn xk .(26)k=0Сочетания с повторениями.

В этом случае каждый элемент может встречаться уже не один раз, а сколькоугодно. Значит, каждая скобка должна содержать формальную сумму всех степеней переменной xi :(1 + x1 + x21 + x31 + . . .) · (1 + x2 + x22 + x32 + . . .) · . . . · (1 + xn + x2n + x3n + . . .) =∞Xk=0Xsi >0s1 +...+sn =kxsi 1 · . . . · xsnn (27)После подстановки xi = x получаем производящую функцию:(1 + x + x2 + x3 + . .

. )n =∞XCCkn xk .(28)k=0Теперь заметим, что у нас слева стоит произведение формальных рядов. А их мы уже умеем сворачивать.Получаем∞X(1 − x)−n =CCkn xk .(29)k=0Теперь получим формулу бинома Ньютона для отрицательных степеней:∞XCCkn αk xk .(30)(k + n − 1) · . . . · (k + 1),(n − 1)!(31)(1 − αx)−n =k=0Отметим одно полезное свойство числа сочетаний:CCkn = Cn−1n+k−1 =то есть это многочлен по переменной k степени n − 1.Теперь рассмотрим ещё один содержательный пример, в котором используются производящие функции.Рассмотрим сначала такую простенькую задачу. Найти число un последовательностей длины n, в которых нетдвух нулей, стоящих подряд. Идея решения состоит в том, чтобы выразить un через числа uj с меньшиминомерами (написать рекуррентное соотношение).

Попробуем сделать это: ясно, что u0 = 1 и u1 = 2. Далее, еслиу нас есть последовательность w длины n, то возможны два случая:w = 1∗. . ∗} ,| .{zn−1w = 01 ∗. . ∗} .| .{z(32)n−2На месте звёздочек могут стоять любые допустимые последовательности длин n − 1 и n − 2 соответственно.Таким образом, un = un−1 + un−2 . Мы получили линейное рекуррентное соотношение.

Давайте выясним, какойобщий вид могут иметь решения линейных рекуррентных соотношений.11Теорема 1.19. Пусть K = C. Пусть u0 , u1 , u2 , . . . — искомая последовательность. Пусть задано рекуррентное соотношениеun+r = a1 un+r−1 + . . . + ar un , ar 6= 0(33)и заданы начальные условия u0 , . . . , ur−1 . Тогда общий член последовательности un выражается в виде многочлена степени строго меньше r:sXun =Pi (n)αni .(34)i=1Рассмотрим производящую функцию этой последовательности:U (x) =∞Xun xn .(35)n=0Рассмотрим многочленG(x) := 1 − a1 x − a2 x2 − . .

. − ar xr .А теперь перемножим их:C(x) := G(x) · U (x) =Заметим, что∞X(36)cn xn .(37)n=0(38)cn+r = un+r − a1 un+r−1 − . . . − ar unпри всех n > 0. Но в силу имеющегося рекуррентного соотношения получаем, что все коэффициенты ряда,начиная с r-го, равны нулю. Значит, C(x) — это просто многочлен степени не выше r − 1.Рассмотрим многочленXF (x) = xr − a1 xr−1 − . . . − ar = (x − α1 )q1 · .

. . · (x − αs )qs ,qi = r.(39)Легко видеть, чтоG(x) = (1 − α1 x)q1 · . . . · (1 − αs x)qs .(40)В самом деле, из определения G ясно, что G(x) = xr F x1 , но выписанное произведение (40) тоже, очевидно,равно xr F x1 .Далее, посколькуr−1C(x) XU (x) ==ci xi (1 − α1 x)−q1 · . . . · (1 − αs x)−qs .(41)G(x)i=0А теперь применяем формулу для бинома с отрицательными степенями:un =min(n,r−1)Xi=0sYXcim1 ,...,ms >0, j=1m1 +...+ms =n−imjαj j CCm.qj(42)С другой стороны, вспомним теорему из анализа о разложении рациональных дробей в сумму простейших:deg C < deg G, поэтомуsqiXXC(x)C(x)βikU (x) ===.G(x)(1 − α1 x)q1 · . . .

· (1 − αs x)qs(1−αi x)ki=1(43)k=1Разлагаем в ряды наши «прогрессии» и приравниваем коэффициенты:U (x) =qi Xs X∞Xβik CCnk αni xni=1 k=1 n=0=s X∞XPi (n)αni xn .(44)i=1 n=0Здесь deg Pi 6 qi − 1 6 r − 1. Окончательно получаемun =sXPi (n)αni ,i=1что и требовалось доказать. 12(45)1.3.2. Формальное дифференцированиеЧтобы не напрягать себя лишними проблемами, будем далее считать кольцо K ассоциативным коммутативным кольцом, потому что ничего другого нам, по сути, и не потребуется.Определение. Пусть дан формальный ряд A(x).

Его формальной производной назовём рядDA(x) :=∞X(n + 1)an+1 xn .(46)n=0Очевидно, что производная — это линейная операция.Несложно проверить, что имеет место формула Лейбница(47)D(A · B) = DA · B + A · DB.Кроме того, если ряды A и B обратимы, то имеет место формула (правило логарифмического дифференцирования)D(A · B)DA DB=+.(48)A·BABЭтот результат немедленно следует из формулы Лейбница.Далее, эта формула без труда обобщается на произвольное количество слагаемых:D(A1 · . . . · An )DA1DAn=+ ...+.A1 · . . .

· AnA1An(49)Из формулы Лейбница легко выводится ещё одно полезное свойство:D(An ) = nAn−1 DA.(50)1.3.3. Сходимость в пространстве формальных рядовВерхние индексы будут обозначать не степень, а номер. Определение. Рассмотрим последовательность рядов Ai ⊂ K [x] . Будем говорить, что Ai → A, еслидля всякого n найдётся δ(n) такое что при всех i > δ(n) имеем ain = an . Иначе говоря, начиная с некоторогономера, n-й коэффициент предела стабилизируется.Определение. Будем говорить, что формальный ряд, составленный из рядов, сходится, если сходится последовательность его частичных сумм.∞P iPПример 3.2.

Рассмотрим ряды Ai (x) := ai xi . ТогдаA (x) = A(x) =ai xi .i=0∗Определение. Через deg A будем обозначать номер минимального ненулевого коэффициента ряда A.∞PУтверждение 1.20 (Критерий сходимости). РядAj (x) сходится тогда и только тогда, когдаj=0deg∗ Aj → ∞,(51)j → ∞.Очевидно. Определение. Пусть ряды B j таковы, что B j (0) = 0. Будем говорить, что B(x) =∞Qj=1последовательность частных произведенийiYj=1сходится к ряду B.1 + B j (x)1 + B j (x) , если(52)Утверждение 1.21.

Бесконечное произведение∞Yj=11 + B j (x)сходится тогда и только тогда, когда deg∗ B j → ∞ при j → ∞. Очевидно. 13(53)Эти свойства сходимости позволяют беспрепятственно перенести операцию дифференцирования на ряды ипроизведения. Так, для сходящихся рядов имеет место свойство:D∞X∞XAj =j=1DAj ,(54)j=1а для сходящихся произведений — формулаD∞Qj=1∞Qj=11 + B (x)j!1 + B j (x)∞XD 1 + B j (x)=.1 + B j (x)j=1(55)1.3.4. Подсчёт количества неприводимых многочленов над FpРассмотрим поле Fp и кольцо многочленов Fp [x].Определение.

Многочлен называется приведённым, если его старший коэффициент равен 1.Заметим, что произведение приведённых многочленов является приведённым многочленом. Мы будем здесьрассматривать только приведённые многочлены, поэтому слово «приведённый» часто будем опускать.Через Rk будем обозначать множество всех приведённых многочленов степени k. Заметим, что ck := |Rk | =pk , потому что старший коэффициент равен 1, а все остальные k коэффициентов произвольны. Рассмотримпроизводящую функцию для последовательности {ci }:CR (x) :=∞X∞Xck xk =k=0pk xk =k=01.1 − px(56)Через Im будем обозначать количество неприводимых многочленов степени m.

Вычислим нашу производящую функцию другим способом. Покажем, чтоCR (x) =∞Y(1 + xm + x2m + x3m + . . . )Im .(57)m=1Почему так? Всякий многочлен P как-то разлагается в произведение неприводимых, взятых в некоторых степенях. У нас есть большой выбор неприводимых многочленов: I1 видов веса 1, I2 видов веса 2 и так далее.Вес многочлена — это просто его степень, то есть тот вклад, который он вносит в степень многочлена P .

Чтокасается видов, то многочленов каждого вида у нас неограниченное количество (потому что, вообще говоря,степени сомножителей ничем не ограничены, и потому в каждой скобке бесконечное количество слагаемых).Множитель m-го веса k-го вида, взятый в степени s, соответствует одночлену xms из скобки с номером k в m-ммножителе бесконечного произведения.А теперь начинаем подсчёт. Сворачивая прогрессии и переходя к обратным рядам, получаем1 − px =∞Y(1 − xm )Im .(58)m=1Продифференцируем это тождество, применяя формулу (55):∞X−p−xm−1=mIm.1 − px m=11 − xmУмножим равенство на x:Выделяя целую часть в дробях, получаем∞X−xm−px=mIm.1 − px m=11 − xm∞X111−=mIm 1 −.1 − px m=11 − xm(59)(60)(61)Раскатывая слагаемые в левой и правой части в прогрессии, получаем∞Xk=1pk xk =∞Xm=1mIm xm + x2m + x3m + .