Новиков Ф.А. Дискретная математика для программистов (860615), страница 39
Текст из файла (страница 39)
Комбинаторика'ТЕОРЕМАС{2п,п) =С{п,А;)2.к=0ДОКАЗАТЕЛЬСТВОИмеем: (1 + х) 2 п = (1 + х) п (1 + х)п. Следовательно,2пСС(2п: i)xl =(п, W ' £ С(п, г)хгг=0г=0г=0Приравняем коэффициент при хп\С(2п, п) = £ С(п, к)С{п, п-к)fc=0= ^Г С(п, к)2.к=О•5.7.3. Числа ФибоначчиЧисла Фибоначчи1 F(n) определяются следующим образом:F(0) =f 1, F( 1) =f 1, F(n + 2) = f F(n + 1) + F(n).Найдём выражение для F(n) через п. Для этого найдём производящую функцию(р(х) для последовательности чисел F(n).
Имеем:ооооф ) = Y^ F(n)xn= F{0)x° + F(\)xl(F(n+71=0- 2) + F(n - !))хП=71 = 2ООооF= 1+ ж +(n- 2)хП +n=2F£( n - !)xn =n=2oooo= 1 + X + X2 Y^ F(n - 2)xn~2 + XF{n - l)xn~l= 1 + X + X271=2oo=71 = 2/ ooF{n)xnF{n)xn - F{ 0)71 = 0\7l=0=/= 1 + X + x2(/?(x) + X {(f(x) — 1).Решая это функциональное уравнение относительно <р(х), получаем, что=11 — 1X —гг-2Xz 'Последнее выражение нетрудно разложить в ряд по степеням х. Действительно,уравнение 1 - х - х 2 = 0 имеет корни х\ — - ( 1 + л/5)/2 и х 2 = - ( 1 - л/5)/2,причём, как нетрудно убедиться,2 n.
ч11 — х — х = (1 — Uах)(1— ох),* Фибоначчи (Лспардо Пизаиский, 1180-1228).1 + ^5где а = — - — ,1 — л/5о= —-—.2055.7. Производящие функцииДалее,1(1 — ах)(1 — Ьх)а/3+ ^, где а =1 — ах1 — Ьх'а-Ъпг, (3 =а —6'а—ЬИз математического анализа известно, что для малых хоо1Таким образом,•э=Т ^+ооооГ ^ =*!>"*"+п-0=°°У"—ла^ а-bп=Опхп-V°°=п=0h пхп—Ъ°°= V^^ а-Ьп=0п=О-—а-Ъ/i"+lхпОкончательно получаемч=a n + — 6n+7а—о1(1 + Vb\(1-VE=5.7.4.
Числа КаталанаЧисла Каталана1 С(п) можно определить следующим образом:71— 1С(0) = f 1, С(п) = fС{к)С(п - к - 1).к=ОЧисла Каталана используются при решении различных комбинаторных задач.Пример Пусть (S, *) — полугруппа и нужно вычислить элемент si * • • • * sn.Сколькими способами это можно сделать? То есть сколькими способами можнорасставить скобки, определяющие порядок вычисления выражения? Обозначимчисло способов С(п). Ясно, что С(0) = 1.
При любой схеме вычислений накаждом шаге выполняется некоторое вхождение операции * над соседними элементами и результат ставится па их место. Пусть последней выполняется товхождение операции *, которое имеет номер к в исходном выражении. При этомслева от выбранного вхождения знака * находилось и было выполнено к — 1 знаков операции *, а справа, соответственно, (n— 1) — (к— 1) = п — к знаков операции*. Тогда ясно, что7171— 1C kl C n kС{п) = J2 ( ~) ( ~ ) = J2 С ( к ) С ( п - к - !)'к=1fc=0и ответом на поставленный вопрос является число Каталана С(п).Числа Каталана выражаются через биномиальные коэффициенты. Получим этовыражение, используя метод производящих функций.1Евгений Чарльз Каталап (1814-1894).206Глава 5. Комбинаторика'ТЕОРЕМА=ДОКАЗАТЕЛЬСТВОНайдём производящую функцию для чисел Каталанап+ 1= f;c(n)x".п=0Для этого рассмотрим квадрат этой функции:£ С(п)хп= £ С(т)хт • £ С(п)хп =\п=0/т=0п=0оооо п=C(m)C{n)xm+n= J2^2c(k)c(n-k)xn=771,71=071 = 0 к=0ТП +1= £ с ( п + 1)х» = £ C ( n + l ) ^ - =71=071=0<р2 (х) == ^ f£х\п=О- С(0) ] = i (<^(х) - 1).Х/Решая уравнение <р(х) = х(р2(х) + 1 относительно функции </>(х), имеем:,1 ± у/1 - 4х=2х'Обозначим f(x): = у/1 - 4х и разложим f(x) в ряд по формуле Тейлора:чк=1Имеем:£ г ( 1 - 4-)» = 5 •- l)= -2k • 1 • 3( 5 - * + l ) • (1 - 4.)*"* • (-4) f e =(2fc-3)-(l-4a:)*-fc == -2 f c • (2k - 3)!! • (1 - 4*)i- f c = ~2 f e 2 l 2 2 f c ( fc! ) 2 ) | ( 1 "_~(2fe-2)l(fe-l)(fe-l)l(2fc - 2)(A: - l)!(fc - 1)!__4яг)*"*=^'= —2(к - 1)\С(2к - 2, к - 1)(1 - 4x)i" f c .Таким образом,/W(0)= —2(к — l)\C(2k — 2,k — l)иoo 1f{x) = 1 - 2 ^-C(2kk= 1- 2, к -l)xk..207УпражненияПодставляя выражение f(x) в формулу для <р(х), следует выбрать знак «минус»перед корнем, чтобы удовлетворить условию С(0) = 1.
Окончательно имеем:С(п)х- ф ) - - ^ - — --_п=ОП=171 = 0и по методу неопределённых коэффициентов С(п) = С(2п,п)/(п+1).•КомментарииСведения из области комбинаторного анализа в том или ином объёме приводятся в любом учебнике по дискретной математике (см., например, [11], [9]).Учебник [13] отличается особенно подробным и доходчивым изложением.
Явные формулы для комбинаторных чисел часто используются при оценке размерапространства поиска в переборных задачах программирования. Очень богатыйнабор полезных формул для комбинаторных чисел можно найти в книге [22]. Всеалгоритмы этой главы заимствованы (в модифицированном виде) из книги [8].Упражнения5.1. Доказать, что А(тп, п) = А(рг - 1, n) + nA(m — 1, п — 1).5.2. Доказать, что множество перестановок с чётным числом инверсий образует группу (альтернированную или знакопеременную подгруппу симметрической группы).5.3. Доказать, что т С ( т — 1, п — 1) = nC(m,n).5.4. Доказать, что число последовательностей длины п, составленных из элементов множества l..m и содержащих каждый элемент множества 1 , .
т покрайней мере один раз, равно m\S{n,m).5.5. Рассмотрим множество функций / : XX, где |Х| = п. Элемент х € Xназывается неподвижной точкой функции / , если f(x) = х. Пусть Нп —множество функций, не имеющих неподвижных точек. Определить, чемуравно \Н п \,5.6. Пусть р^ — число булевых функций, существенно зависящих от всех своихпеременных.
Очевидно, чтотгг=0Получить явную формулу для рп,используя формулы обращения.5.7. Доказать, что любое натуральное число можно представить как сумму попарно различных чисел Фибоначчи.Глава 6КодированиеВопросы кодирования издавна играли заметную роль в математике.Примеры1.
Десятичная позиционная система счисления — это универсальный способ кодирования чисел, в том числе натуральных. Римские цифры — другой способкодирования небольших натуральных чисел, причём гораздо более наглядный и естественный: палец — I, пятерня — V, две пятерни — X1. Однакопри этом способе кодирования трудно выполнять арифметические операциинад большими числами, поэтому он был вытеснен позиционной десятичнойсистемой.2. Декартовы координаты — способ кодирования геометрических объектов числами.Ранее средства кодирования играли вспомогательную роль и не рассматривалиськак отдельный предмет математического изучения, по с появлением компьютеровситуация радикально изменилась.
Кодирование буквально пронизывает информационные технологии и является центральным вопросом при решении самыхразных (практически всех) задач программирования. Вот несколько примеров:• представление данных произвольной природы (например чисел, текста, графики) в памяти компьютера;• защита информации от несанкционированного доступа;• обеспечение помехоустойчивости при передаче данных по каналам связи;• сжатие информации в базах данных.ЗАМЕЧАНИЕСамо составление текста программы часто и совершенно справедливо называют кодированием.1Плотники часто маркируют бревна сруба римскими цифрами, потому что их легко вырубитьтопором.Глава 6.
Кодирование209Не ограничивая общности, задачу кодирования можно сформулировать следующим образом. Пусть заданы алфавиты А = { a i , . . . , ап}, В = {&i,..., bm} и функция F: А* —• В*, причём D o m / = S, где S — некоторое множество слов в алфавите A, S С А*. Тогда функция F называется кодированием, элементы множестваS — сообщениями, а элементы /? = F(a), а Е S, /5 е В* — кодами (соответствующих сообщений). Обратная функция F~l (если она существует!) называетсядекодированием.
Если \В\ = т, то F называется т-ичным кодированием. Наиболее распространенный случай В = {0,1} — двоичное кодирование. Именно этотслучай рассматривается в последующих разделах; слово «двоичное» опускается.Типичная задача теории кодирования формулируется следующим образом: призаданных алфавитах А, В и множестве сообщений S пайти такое кодирование F,которое обладает определёнными свойствами (то есть удовлетворяет заданнымограничениям) и оптимально в некотором смысле.
Критерий оптимальности, какправило, связан с минимизацией длин кодов. Свойства, которые требуются откодирования, бывают самой разнообразной природы:• Существование декодирования, или однозначность кодирования: функция кодирования F обладает тем свойством, что а\ ф а2F ( a i ) Ф F(a2). Этоочень естественное свойство, однако даже оно требуется не всегда. Например,трансляция программы па языке высокого уровня в машинные команды — этокодирование, для которого не требуется однозначного декодирования.• Помехоустойчивость, или исправление ошибок: продолжение функции декодирования F~l обладает тем свойством, что F~l((3) = F~l(f3'), где /5 б I m F ,(3/ Е В* \ Im F, если (3' в определённом смысле близко к /3 (см.
6.3).• Заданная сложность (или простота) кодирования и декодирования. Например,в криптографии изучаются такие способы кодирования, при которых функцияF вычисляется просто, но определение значения функции F~l требует оченьсложных вычислений (см. 6.5.5).Большое значение для задач кодирования имеет природа множества сообщений S. При одних и тех же алфавитах А, В и требуемых свойствах кодирования Fоптимальные решения для разных S могут кардинально различаться. Для описания множества S (как правило, очень большого или бесконечного) применяютсяразличные методы:• теоретико-множественное описание, например S = {a | а € A* h |а| = п};• вероятностное описание, например S = А*, и заданы вероятности PI появлениябукв ai в сообщении,Р* =• логико-комбипаторпое описание, например S задано порождающей формальной грамматикой.В этой главе рассматривается несколько наиболее важных задач теории кодирования и демонстрируется применение большей части вышеупомянутых методов.210Глава 6.
Кодирование 2106.1. Алфавитное кодированиеКодирование F может сопоставлять код всему сообщению из множества S какединому целому или же строить код сообщения из кодов его частей. Элементарной частью сообщения является одна буква алфавита А. Этот простейшийслучай рассматривается в этом и следующих двух разделах.6.1.1. Таблица кодовАлфавитное (или побуквенное) кодирование задается схемой (или таблицей кодов) а\Defа = (oi -> Pi, ... ,апРп),ai € A, fa € В*.Множество кодов букв V = f {Pi} называется множеством элементарных кодов (множеством кодовых слов). Алфавитное кодирование пригодно для любогомножества сообщений S:F: А* -» В*,Примерau...aik=aeA*,F(a) =f ph ...
(3ik.Рассмотрим алфавиты А: ={0,1,2,3,4,5,6,7,8,9}, В : ={0,1} и схемусг 1 :=(0 —• 0,1 —* 1,2 —• 10,3 —• 11)4 —• 100,5 -> 101,6 ^ 110,7 —• 111,8 —• 1000,9 —> 1001).Эта схема однозначна, но кодирование не является взаимно однозначным:F ffl (333) = 111111 = F tTl (77),а значит, декодирование невозможно. С другой стороны, схемасг2 : =(0 -> 0000,10001,2 -> 0010,3 —• 0011,4 —• 0100,50101,6 -> 0110,7 —> 0111,8 —» 1000,9 —• 1001),известная под названием «двоично-десятичное кодирование», допускает однозначное декодирование.I6.1.2. Разделимые схемыРассмотрим схему алфавитного кодирования а и различные слова, составленныеиз элементарных кодов. Схема а называется разделимой, еслиРп ••• P%k = Pjx ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
