В.А. Носов - Комбинаторика и теория графов (1023552), страница 10

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

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

f(0) = 0, то берем знак минус)Отсюда получаем, чтоun =(2n − 2) ! 1  2n − 2= n !(n − 1)! n  n − 1 Широкая область приложений производящих функций - получение формул обращения.Рассмотрим примеры.Теорема 5. Пусть имеем две последовательности {un} и {vn} , связанные соотношением для некоторого натурального t tnun =∑ k=0 (−1) k  k v n− kvn =∑ k=0 (9)тогдаn t + k − 1 u n− kk (10)Обратно равенство (10) влечет (9).61♦ Рассмотрим производящие функцииu(x) =∞∑ n=0 u n x nи v(x) =∞∑ n=0 v n x nи рассмотрим тождество(1 - x)t = tt∑ k=0 (−1) k  k x kОтсюдаv(x)(1 - x)tгде an = tnR(x) = a0 + a1x + … + anxn + …дает∑ k=0 (−1) k  k v n− kсогласно (9) и значит v(x)(1 - x)t = u(x)Следовательно, v(x) = u(x) (1 - x)-tПоскольку (1 - x)-t = ∑ ∞k =0n( − t )( − t − 1)L ( − t − k + 1)( − x) k =k!∞ t + k − 1 kxk ∑ k=0  t + k − 1 u n− k ♦k ∑ k=0 то vn =Теорема 6.

Пусть имеем две последовательности {an} и {bn}, связанные соотношениемbn =n n∑ k=0  k a n− kТогдаan =(11) nn∑ k=0 (−1) k  k b n− k(12)Обратно, равенство (12) влечет (11).♦ Рассмотрим экспоненциальные производящие функцииA(x) =∞a∑ n=0 nn! x nи B(x) =∞∑ n=0bn nxn!и возьмем рядx x2xne =1+ ++K++Kn!1! 2 !xРассмотрим произведениеfffex A(x) = F(x) = f0 + 1 x + 2 x 2 +K+ n x n +K1!2!n!гдеfn1 a n− kn= ∑ k=0n!k ! (n − k)!откуда62fn =n n∑ k=0  k a n− k = b nЗначит F(x) = B(x) = ex A(x)Откуда A(x) = e-x B(x)Имеем e-x =ka∞k x(−1).

Следовательно, или n =∑ k=0n!k!n∑ k=0 (−1) k1 b n− kk ! (n − k)!Утверждения теорем 5 и 6 называются формулами обращения. ♦63§ 4. Обращение Мебиуса.1. Напомним сначала определение важной теоретико-числовой функции Мебиуса:1, если n = 1µ(n)=0, если существует простое число p, p2  nk(-1) , если n = p1… pk - произведение k различных простыхмножителей.Докажем основное свойство функции Мебиуса:Теорема 1.1, Њ–‘Џ n = 1∑ µ (d ) = 0, Њ–‘Џ n > 1d n(1)♦ Если n = 1, то единственный делитель d = 1 и (1) верно, т.к. µ(1) = 1.Пусть теперь n > 1. Представим его в видеsssn = p11 p 22 K p kk ,dddгде pi, i ∈1, k - простые числа, si - их степени.

Если d - делитель n, то d = p 1 1 p 2 2 K p k k ,где 0 ≤ di ≤ si, i ∈1, k . Если di > 1 для некоторого i ∈1, k , то µ(d) = 0. Значит в (1) нужнорассмотреть только такие d, для которых di ≤ 1, ∀ i ∈1, k . Каждый такой делитель состоит из произведения r различных простых чисел, где r ∈1, k , причем его вклад в сумму k(1) равен (-1)r и всего их   . Таким образом, получаем r k 1 k k∑ µ(d ) = 1 −   +K+( −1) k   = 0. ♦dnТеорема 2. (Формула обращения Мебиуса). Пусть f(n) и g(n) - функции натурального аргумента.

Тогда равенствоg(n) =∑ f (d)(2)dnсправедливо тогда и только тогда, когда справедливо равенствоf(n) =∑ µ(d)g( dn )(3)dn♦ Пусть (2) справедливо для любого n. Тогда64g( dn ) =∑ f (d ′)d′ndПодставляя в правую часть (3), получаем∑ µ(d)g( dn ) = ∑ µ(d) ⋅ ∑ f (d ′)dndnd′ndДвойное суммирование справа проводится по всем парам d, d′ , таким, чтоd⋅d′n .

Если выбрать d′, то d будет пробегать все делителиn. Таким образомd′∑ µ(d)g( dn ) = ∑ f (d ′) ⋅ ∑ µ(d ′)d′ ndnНо согласно (1) имеем∑ µ(d ′)d′nd′d′nd′п ри n > d ′п ри n = d ′0= 1Значит, равенство (3) установлено. Пусть теперь (3) справедливо для любого n. Тогда∑ f (d)=dn∑ ∑ µ(d ′)g( dd′ ) , d ′′ = d d ′dn- является делителем n и двойная сумма можетd′ dбыть переписана в виде∑∑ µ(d ′)g(d ′′)d′′ n d′ nd′′=∑ g(d ′′) ⋅ ∑ µ(d ′)d′′ nd′ nd′′Согласно (1) последняя сумма превращается в единицу в случае d′′ = n, в остальных случаях она есть ноль. Это доказывает (2).

♦2. Рассмотрим приложение обращения Мебиуса.Пусть дан алфавит А из s букв. Имеется sn слов длины n в данном алфавите. Длякаждого слова w0 = a1 a2 … an можно определить n - 1 словw1 = a2 a3 … ana1, w2 = a3 a4 … a1 a2 , … , wk-1 = an a1 … an-1, , получаемых один из другогоциклическими сдвигами. На множестве всех sn слов введем отношение эквивалентности:два слова объявим эквивалентными, если один из другого получается циклическимсдвигом. Нас будут интересовать число классов, которые содержат точно n слов. Такаязадача возникает в теории синхронизирующих кодов.Будем называть слово w вырожденным, если класс эквивалентности, содержащий w, состоит из менее, чем n слов.

Назовем w периодическим, если существует словоu и натуральное число m, такое, что w = u u … u (m раз).Теорема 3. Слово w периодическое тогда и только тогда, когда оно вырождено.65♦ Ясно, что если w периодическое, то оно вырождено. Пусть w вырождено.Пусть p - минимальное целое, такое, что w = wp. Тогда еслиw = a1 a2 … an, то wp = a1+p a2+p … an+p (индексы по модулю n). Отсюда получаем, что вкачестве u можно взять a1 a2 … ap, а в качестве m =n.

(Легко видеть, что pn). ♦ Обоpзначим через M(d) - число квадратов, которые содержат d слов. Из предыдущего имеемdn. Таким образом, справедлива формула∑ dM(d) = sn.dnПрименим формулу обращения Мебиуса для случая g(n) = sn, f(d) = dM(d). Тогда получаем∑ µ(d)snM(n) =nddnилиn1µ (d)s d∑ndnM(n) =Таким образом, M(n) - интересующее нас число. Если n = p - простое число, то1 p(s − s)pM(p) =Имеется мультипликативный вариант обращения Мебиуса. СправедливаТеорема 4. Пусть f(n) и g(n) - функции натурального аргумента, связанные соотношениямиf(n) =∏ g(d)(4)dnТогдаg(n) =∏ f (d)µ (n )d(5)dnи обратно, из (5) следует (4).Используя формулу обращения Мебиуса, можно решить важную в практическом отношении задачу о числе неприводимых многочленов фиксированной степени над конечным полем.

Пусть GF(q) - поле из q элементов и m - натуральное число. Тогда для числаΦm(q) неприводимых многочленов над полем GF(q) справедлива формулаΦm(q) =1∑ µ(m d)q dmdn(6)Приведем таблицу нескольких первых значений функции Φm(2)66m123456Φm(2)21236967§ 5. Перманенты и их применение к перечислительнымзадачам.1. Для решения многих комбинаторных задач используются перманенты. Рассмотрим числовую матрицуA = (ai, j), i = 1, n , j = 1, m , n ≤ mПерманент матрицы А (обозначение - per А) определяется равенствомper A =∑( j1 ,K, jn )a 1 j1 ⋅ a 2 j2 ⋅L a njn(1)где суммирование производится по всем n-перестановкам из m элементов 1, 2, , m.

Другими словами, перманент матрицы равен сумме произведений элементов, взятых по одному из каждой строки и разных столбцов.Из формулы (1) следуют некоторые очевидные свойства перманента, аналогичные свойствам определителя для квадратных матриц.1. Если одна из строк (n×m)-матрицы А (n ≤ m) состоит из нулей, то per A = 0.При n = m то же верно и для столбцов.2. При умножении всех элементов одной из строк матрицы А на некоторое число значение перманента А умножается на то же число.3.

Перманент не меняется при перестановке ее строк и столбцов.Обозначим через Aij - матрицу, полученную из А вычеркиванием i-ой строки и j-гостолбца.4. Справедлива формула разложения перманента по i-ой строкеper A = ai1 per Ai1 + ai2 per Ai2 + ... + aim per Aim (2)таким образом, многие свойства перманентов аналогичны свойствам определителей.Однако, основное свойство определителей det(A⋅B) = detA⋅detB не выполняется для перманентов, и это обстоятельство сильно затрудняет их вычисление.1 1 1 1  2 2Например,  ⋅ =1 1 1 1  2 21 1per  = 2, per1 1 2 2 =8 2 21 11 1Однако, 4 = per  ≠ per ⋅per 1 11 1 2 2 =8 2 2(3)рассмотрим одно из важнейших применений понятия перманента в комбинаторных за68дачах.

Пусть X = {x1, , xm} - конечное множество, а X1, … , Xn - система подмножествмножества X. Набор элементов x1, , xn называется системой различных представителейили трансверсалью для множеств X1, … , Xn , если выполнены условияxi ∈ Xi,i = 1, nxi ≠ xjпри i ≠ j.(4)При этом говорят, что элемент xi представляет множество Xi . Необходимость нахождения системы различных представителей возникает при решении многих прикладныхзадач. Рассмотрим следующую задачу кодирования.

Пусть имеется некоторое предложение, т.е. упорядоченный набор слов в некотором алфавите. Требуется закодироватьданное предложение так, чтобы каждому слову ставилась в соответствие одна буква,причем эта буква должна входить в состав этого слова, а разным словам должны соответствовать разные буквы.Пример: Предложение abc abd abe cde cde можно закодировать как abecd. Вто же время, предложение ab ab bc abc bcd не может быть закодировано подобнымобразом, поскольку первые четыре слова в совокупности содержат только три буквы.Для системы множеств X1, … , Xn определим матрицу инцидентности A = (aij), i = 1, n ,j = 1, m , гдеaij =1, если xi ∈ Xi(5)0, в противном случае.СправедливаТеорема 1.

Пусть A = (aij), i = 1, n , j = 1, m , (n ≤ m) матрица инцидентностимножеств X1, … , Xn , где Xi ⊆ X, i = 1, n , X = {x1, … , xm} . Тогда для числа систем различных представителей R(X1, … , Xn) множеств X1, … , Xn справедливо равенствоR(X1, … , Xn) = per A(6)♦ Действительно, поскольку в матрице А элемент aij = 1 , если xj ∈ Xi и aij = 0 ,если xj ∈ Xi, то набор ( x i1 , x i2 , K , x i n ) элементов X является системой различных представителей для X1, … , Xn в том и только в том случае, когда a 1i1 , a 2i2 ,K , a ni n = 1 и элементы a 1i1 , K , a ni n находятся в разных столбцах матрицы А.

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

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