Книги по разным темам Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |   ...   | 12 |

По формуле бинома имеем коэффициент un при xn :

1 1 1 (2 -1)L(2 - n +1)(-4x)n (- ) 13L(2n - 3) 2n-2 un = = = n! n! или, умножая и деля на (n - 1) !, получаем 1 3L(2n - 3) 2 4L(2n - 2) (2n - 2)! = = n!(n - 1)! n!(n - 1)! Поскольку при x < ряд для F(x) сходится, то все производимые операции законны и значит Tn = un+1.

Следовательно, 2n Tn = n + 1 n Полученные числа Tn называются числами Каталана. Они появляются во многих комбинаторных задачах. Приведем таблицу первых значений чисел Tn.

n 0 1 2 3 4 5 6 Tn 1 1 2 5 14 42 132 Таблица. Числа Каталана Пример. Найти число способов вычисления неассоциативного произведения x1 x2 Е xn с помощью бинарных умножений.

Решение. Пусть un - число способов вычисления данного произведения.

Имеем x1 x2 = (x1 x2) и u2 = x1 x2 x3 := ((x1 x2) x3), (x1 (x2 x3)) и u3 =Произведение x1 x2 Е xn вычисляется на последнем этапе как произведение результата вычисления умножения первых r символов и соответствующего результата для последних n - r символов для некоторого r, т.е.

x1 Е xn = (x1 Е xr)( xr+1 Е xn) Первые r символов перемножаются ur способами, последние n - r un-r способами. В итоге можно написать соотношение un = u1 un-1 + u2 un-2 + Е + un-1 u1 (8) Положим u1 = 1.

Аналогично тому, как сходное соотношение решалось в теореме (4), образуем производящую функцию f(x) = u1 x + u2 x2 + Е + un xn + Е Возвышая в квадрат f(x) и пользуясь соотношением (8) имеем f2(x) = f(x) - x Решая квадратное уравнение, получаем 1- (1- 4x)1/f(x) = (т.к. f(0) = 0, то берем знак минус) Отсюда получаем, что 2n (2n - 2)! 1 - un = = n!(n -1)! n n -Широкая область приложений производящих функций - получение формул обращения.

Рассмотрим примеры.

Теорема 5. Пусть имеем две последовательности {un} и {vn}, связанные соотношением для некоторого натурального t t un = (-1)k v (9) n n-k k= k тогда t + k - vn = un-k (10) n k= k Обратно равенство (10) влечет (9).

Рассмотрим производящие функции u(x) = unxn и v(x) = v xn n n=0 n=и рассмотрим тождество t (1 - x)t = (-1)k xk t k= k Отсюда v(x)(1 - x)t дает R(x) = a0 + a1x + Е + anxn + Е t где an = (-1)k v согласно (9) и значит v(x)(1 - x)t = u(x) n n-k k= k Следовательно, v(x) = u(x) (1 - x)-t t + k (-t)(-t - 1)L(-t - k + 1) - Поскольку (1 - x)-t = (-x)k = xk k=k=k! k t + k - то vn = un-k n k= k Теорема 6. Пусть имеем две последовательности {an} и {bn}, связанные соотноn шением bn = (11) a n-k n k= k n Тогда an = (-1)k bn-k (12) n k= k Обратно, равенство (12) влечет (11).

Рассмотрим экспоненциальные производящие функции a bn A(x) = n xn и B(x) = xn n=0 n=n! n! и возьмем ряд x x2 xn ex = 1 + + +K+ +K 1! 2! n! Рассмотрим произведение f1 f2 fn ex A(x) = F(x) = f0 + x + x2 +K+ xn +K 1! 2! n! fnn-k 1 a где = n k=n! k! (n - k)! откуда n fn = a n-k = bn n k= k Значит F(x) = B(x) = ex A(x) Откуда A(x) = e-x B(x) a bn-k xk n Имеем e-x = (-1)k. Следовательно, или = (-1)k n k=0 k=k! n! k! (n - k)! Утверждения теорем 5 и 6 называются формулами обращения.

з 4. Обращение Мебиуса.

1. Напомним сначала определение важной теоретико-числовой функции Мебиуса:

1, если n = (n)=0, если существует простое число p, p2 n (-1)k, если n = p1Е pk - произведение k различных простых множителей.

Докажем основное свойство функции Мебиуса:

Теорема 1.

1,МЦСП n = (1) 0,МЦСП n > (d) = d n Если n = 1, то единственный делитель d = 1 и (1) верно, т.к. (1) = 1.

Пусть теперь n > 1. Представим его в виде s n = p11ps2 Kpsk, 2 k d где pi, i 1, k - простые числа, si - их степени. Если d - делитель n, то d = p11pd2 Kpdk, 2 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 kk (d) = 1 - +K+(-1)k = 0.

1 k d n Теорема 2. (Формула обращения Мебиуса). Пусть f(n) и g(n) - функции натурального аргумента. Тогда равенство g(n) = f(d) (2) dn справедливо тогда и только тогда, когда справедливо равенство n f(n) = (d)g(d) (3) dn Пусть (2) справедливо для любого n. Тогда n g( ) = f(d) d n d d Подставляя в правую часть (3), получаем n (d) f(d) (d)g(d) = n dn dn d d Двойное суммирование справа проводится по всем парам d, d, таким, что n ddn. Если выбрать d, то d будет пробегать все делители. Таким образом d n f(d) (d)g(d) = (d) n dn d n d d 0 при n > d Но согласно (1) имеем (d) = n 1 при n = d d d Значит, равенство (3) установлено. Пусть теперь (3) справедливо для любого n. Тогда d f(d) = = (d)g(d), d d d - является делителем n и двойная сумма может dn dn d d быть переписана в виде g(d) (d)g(d) = (d) n n d nd d n d d d Согласно (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 периодическое тогда и только тогда, когда оно вырождено.

Ясно, что если w периодическое, то оно вырождено. Пусть w вырождено.

Пусть p - минимальное целое, такое, что w = wp. Тогда если w = a1 a2 Е an, то wp = a1+p a2+p Е an+p (индексы по модулю n). Отсюда получаем, что в n качестве u можно взять a1 a2 Е ap, а в качестве m =. (Легко видеть, что pn). Обоp значим через M(d) - число квадратов, которые содержат d слов. Из предыдущего имеем dn. Таким образом, справедлива формула dM(d) = sn.

dn Применим формулу обращения Мебиуса для случая g(n) = sn, f(d) = dM(d). Тогда получаем n d nM(n) = (d)s dn или n d M(n) = (d)s n dn Таким образом, M(n) - интересующее нас число. Если n = p - простое число, то M(p) = (sp - s) p Имеется мультипликативный вариант обращения Мебиуса. Справедлива Теорема 4. Пусть f(n) и g(n) - функции натурального аргумента, связанные соотношениями f(n) = g(d) (4) dn (nd) Тогда g(n) = f(d) (5) dn и обратно, из (5) следует (4).

Используя формулу обращения Мебиуса, можно решить важную в практическом отношении задачу о числе неприводимых многочленов фиксированной степени над конечным полем. Пусть GF(q) - поле из q элементов и m - натуральное число. Тогда для числа m(q) неприводимых многочленов над полем GF(q) справедлива формула m(q) = (6) (md)qd m dn Приведем таблицу нескольких первых значений функции m(2) m 1 2 3 4 5 2 1 2 3 6 m(2) з 5. Перманенты и их применение к перечислительным задачам.

1. Для решения многих комбинаторных задач используются перманенты. Рассмотрим числовую матрицу A = (ai, j), i = 1, n, j = 1, m, n m Перманент матрицы А (обозначение - per А) определяется равенством per A = a1j1 a2 j2 La (1) njn ( j1,K,jn) где суммирование производится по всем n-перестановкам из m элементов 1, 2,, m. Другими словами, перманент матрицы равен сумме произведений элементов, взятых по одному из каждой строки и разных столбцов.

Из формулы (1) следуют некоторые очевидные свойства перманента, аналогичные свойствам определителя для квадратных матриц.

1. Если одна из строк (nm)-матрицы А (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(AB) = detAdetB не выполняется для перманентов, и это обстоятельство сильно затрудняет их вычисление.

1 1 1 1 2 Например, = 1 1 1 1 2 1 1 2 per = 2, per = 1 1 2 1 1 1 1 2 Однако, 4 = per per per = 8 (3) 1 1 1 1 2 рассмотрим одно из важнейших применений понятия перманента в комбинаторных за дачах. Пусть X = {x1,, xm} - конечное множество, а X1, Е, Xn - система подмножеств множества X. Набор элементов x1,, xn называется системой различных представителей или трансверсалью для множеств X1, Е, Xn, если выполнены условия xi Xi, i = 1, n (4) xi xj при i j.

При этом говорят, что элемент xi представляет множество Xi. Необходимость нахождения системы различных представителей возникает при решении многих прикладных задач. Рассмотрим следующую задачу кодирования. Пусть имеется некоторое предложение, т.е. упорядоченный набор слов в некотором алфавите. Требуется закодировать данное предложение так, чтобы каждому слову ставилась в соответствие одна буква, причем эта буква должна входить в состав этого слова, а разным словам должны соответствовать разные буквы.

Пример: Предложение abc abd abe cde cde можно закодировать как abecd. В то же время, предложение ab ab bc abc bcd не может быть закодировано подобным образом, поскольку первые четыре слова в совокупности содержат только три буквы.

Для системы множеств X1, Е, Xn определим матрицу инцидентности A = (aij), i = 1, n, j = 1, m, где 1, если xi Xi aij = (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, то набор (xi1, xi2,K, xin ) элементов X является системой различных представителей для X1, Е, Xn в том и только в том случае, когда a1i1,a2i2,K,a = 1 и элеnin менты a1i1,K,a находятся в разных столбцах матрицы А. Суммируем числа nin a1i1,K,a по всем n-перестановкам элементов 1, 2, Е, m. Тогда получим с одной стоnin роны число систем различных представителей для X1, Е, Xn, а с другой - значение перманента матрицы А.

Следствие. Система различных представителей для X1, Е, Xn существует тогда и только тогда, когда для соответствующей матрицы инциденция А выполнено:

per A > 0 (7) Поскольку в формуле (1) m(m - 1) Е (m - n +1) членов, то вычисление перманента на основе определения затруднительно. Приведем для этой цели общую формулу.

2. Ограничимся рассмотрением квадратных числовых матриц А = (aij), i, j = 1, n.

Тогда per A = a1i1 a2i2 La nin (i1,K,in ) где сумма распространяется по всем перестановкам i1, Е, in элементов 1, 2, Е, n. Применим формулу включения-исключения для вычисления перманента матрицы А. Каждому набору i1, Е, in поставим в соответствие вес, равный a1i1,K,a.

nin Значит перманент А - это сумма весов тех наборов, которые соответствуют перестановкам. Введем n свойств P1, Е, Pn на множестве всех наборов i1, i2, Е, in из 1, 2, Е, n, где свойство Pi означает, что в наборе i1, Е, in нет элемента i. Таким образом, перманент А - это сумма весов наборов i1, Е, in, не обладающих ни одним из свойств P1, Е, Pn. Осталось определить сумму весов W( Pi1,K, Pik ) наборов, обладающих k свойствами Pi1,K, Pik. Имеем для суммы весов W(0) всех наборов i1, Е, ik.

W(0) = a1i1,K,a = (a11+L+a1n )(a21+L+a2n )L(a +L+a ) (8) nin n1 nn i1,K,in ^^ W(N(Pi)) = a1i1,K,a = (a11+L+ a1i +L+a1n )L(a +La +L+a ) (9) nin n1ni nn i1,K,in i где знак ^ над элементом матрицы А означает, что этот элемент следует опустить.

Аналогично для sij (i < j) имеем ^^ ^^ W(N(Pi, Pj)) = (a11+L+ a1i +L+ a1j +L+a1n )L(a +La +L+ a +L+a ) (10) nj n1ni nn Теперь, используя формулу включения-исключения, получаем формулу Райзера для перманента А:

n ^ n per A = (ai1+L+ain ) - (a +L+ a +L+a )+L+ i=1 n k1 ki kn k=i=^^ +(-1)s +L+ a +L+akn )+L (11) n (a k1+L+ a ki1 kis k=1i1

3. Выясним теперь вопрос об условиях равенства нулю перманента (0, 1)-матрицы. Ограничимся случаем квадратной матрицы.

Теорема 2. Пусть A = (aij), i, j = 1, n - (0, 1)-матрица порядка n. Тогда per A= 0 в том и только в том случае, когда в А существует подматрица из нулей размера s t, где s + t = n + 1.

Пусть такая нулевая подматрица в А существует. Поскольку перманент не меняется от перестановок строк и столбцов, то можно считать, что эта подматрица расположена в левом нижнем углу, т.е.

B C A = O D где О - (s t) - матрица из нулей, подматрица B имеет размер (n - s) t. Любой член перманента А должен содержать по одному элементу из первых t столбцов. Поэтому, если искать положительный член перманента, то элементы этих столбцов должны принадлежать попарно различным строкам с номерами 1, 2, Е, n - s. Однако n - s = t - 1 < t и поэтому данное условие выполнить нельзя, т.е. per A = 0.

Пусть теперь per A = 0. Доказательство теоремы проводим индукцией по n. При n = 1 утверждение очевидно (А = (0)). Пусть оно справедливо для всех порядков, меньших n. Если А - нулевая матрица порядка n, то утверждение очевидно. Если А - не нулевая матрица, то пусть aij = 1. Запишем разложение А по строке i:

per A = ai1Ai1 + Е + ainAin Поскольку per А = 0, то per Аij = 0. Но Аij имеет размер (n - 1) (n - 1) и по предположению индукции для нее существует подматрица из нулей размера s1 t1, причем s1 + t1 = n - 1 + 1 = n. Переставим строки и столбцы так, чтобы эта нулевая подматрица оказалась в нижнем левом углу:

Pages:     | 1 |   ...   | 5 | 6 | 7 | 8 | 9 |   ...   | 12 |    Книги по разным темам