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

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

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

Пусть имеем соотношениеun = a1un-1+ … + akun-kс начальными условиями u1, … , uk . Тогда справедливо соотношение при всехn≥k a1 a 21 00 1..0 0a300.0........... ak. 0. 0. . 1 0n−k u k   un   u k −1   u n −1  .  = .   .   .   u1   u n − k +1 (8)♦ Доказательство индукцией по n. При n = k равенство (8) справедливо.

Пустьоно верно при n. При n + 1 имеем53 a1 a 21 00 1..0 0a300.0...... ak. 0. 0. . 1 0.....n +1− k uk  u k −1  . = .  u1 . ak. 0. 0. . 1 0 a1 a 21 0= 0 1..0 0a3 .0 .0 .. .0 ....... a k   a1 a 2. 0  1 0. 0  0 1. .  ..1 0  0 0 a1 a 21 0= 0 1..0 0a300.0...... a k   u n   u n +1  . 0   u n −1   u n . 0  .  =  .  ♦ .

.  .   .  1 0   u n − k +1   u n − k +2 .....a3 .0 .0 .. .0 ......n−k uk  u k −1  . = .  u1 В большинстве случаев, однако, при изучении перечислительных задач возникают нелинейные рекуррентные соотношения, для разрешения которых используютсяспецифические приемы. Некоторые из них будут рассмотрены в дальнейшем.

Приведемважный пример нелинейного рекуррентного соотношения.Теорема 7. Пусть C(n, k) - число подстановок n-элементного множества, имеющих точно k циклов. Тогда справедливоC(n, k) = C(n - 1, k - 1) + (n - 1)C(n - 1, k)(9)C(0, 0) = 1, C(0, 1) = 0♦ Разобьем множество подстановок множества X = {1, 2, … n,} имеющих точноk циклов, на два класса - подстановки, в которых элемент n содержится в единичномцикле, и подстановки, в которых элемент n находится в цикле длины l, l > 1. В первомслучае число подстановок совпадает с числом подстановок множества X′ = {1, 2, …, n 1}, имеющих k - 1 циклов, т.е. C(n - 1, k - 1). Во втором случае, удаляя элемент n, получаем подстановку множества X′ = {1, 2, …, n - 1} с k циклами, число которых равноC(n - 1, k).

Выясним теперь, каким числом способов в подстановку степени n - 1 с k циклами можно добавить элемент n. Если имеется цикл длины i, то это можно сделать i способами. Общее число способов равно i1 + … + ik , где i1, … , ik - длины циклов подстановки.

Однако i1 + … + ik = n - 1. Значит число подстановок второго класса равно(n - 1)C(n - 1, k). Отсюда и получаем (9). ♦54Полученные числа C(n, k) связаны с известными числами Стирлинга первогорода sn,k , которые определяются так:sn,k = (- 1)n+k C(n, k)Приведем таблицу нескольких первых значений чисел sn,k .nsn,0sn,1sn,2sn,3sn,4sn,50100000101000020-11000302-310040-611-6105024-5035-10160-120274-22585-15Табл. Числа Стирлинга первого рода55§ 3. Производящие функции и формулы обращения1. Пусть a0, a1, … , an, … некоторая последовательность чисел.

Свяжем с этойпоследовательностью рядR(x) = a0 + a1x + … + anxn + …называемый производящей функцией для последовательности {an}. Если ряд R(x) сходится в некотором круге радиуса R > 0 к некоторой функции F(x), то функцию F(x) также называют производящей для {an}.Если R(x) и Q(x) - производящие функции для последовательностей {an}и {bn}соответственно, то естественным образом определяются операции:а) Умножение на константу. Если α - некоторая константа, тоαR(x) = αa0 + αa1x + … + αanxn + … , т.е.

αR(x) - производящая функция для последовательности {αan}.в) Сложение.R(x) + Q(x) = (a0 + b0) + (a1 + b1)x + … + (an + bn)xn + …т.е. R(x) + Q(x) - производящая функция последовательности {an + bn}.с) Умножение.nR(x)⋅ Q(x) = a0 b0 + (a0b1 + a1b0) x + … + ( ∑i =0 a i ⋅ b n −i )x n + …и значит R(x)⋅ Q(x) - производящая функция свертки последовательностей {an}и {bn}.Обратной к производящей функции R(x) называется функция Q(x) такая, чтоQ(x)⋅R(x) = 1.Теорема 1. Обратная функция к R(x) существует тогда и только тогда,когда a0 ≠ 0.♦ Действительно, запишем условия обращения функции R(x)a0b0 = 1a0b1 + a1b0 = 0(1)……n∑ i =0 a i ⋅ b n − i=0Легко видеть, что система (1) разрешима относительно b0, b1, … , bn, … тогда итолько тогда, когда a0 ≠ 0 .56a1, b1 = - 1 .a0a 20Решением в этом случае служит: b0 =Если b0, b1, … , bn-1 уже определены, тоbn =1(-a1bn-1 - … - anb0).

♦a0Экспоненциальной производящей функцией для последовательности{an}называется рядE(x) = a0 + a1x + … +an nx +…n!(2)Операция сложения, умножения на константу для экспоненциальных производящихфункций определяются так же, как и для обычных производящих функций.Произведение их определяется так: Если Ea(x), Eb(x) - экспоненциальные производящие функции для последовательностей {an} и {bn} соответственно, тоEa(x)⋅ Eb(x) = c0 + c1x + … +cn nx +…n!(3) n nгде cn = a0bn +   a1bn-1 + … +   akbn-k + … + anb0. 1 kПроизводящие функции являются полезным инструментом для решения перечислительных задач, получения различных тождеств и решения рекуррентных соотношений.Пример. Найти последовательность an , n = 0, 1, … , для которой функция(1 - 4x)-1/2 является производящей.Решение.

Согласно биномиальной теореме имеем(1 + x)α = 1 + ∑ r =1α (α − 1)L (α − r + 1) rxr!где верхний предел суммирования равен α, если α - положительное целое, и бесконеченв противном случае.Значит (1 - 4x)-1/2111∞ (− 2 )(− 2 − 1)... (− 2 − r + 1)= 1 + ∑ r=1(−4x) r =r!r 1 32r −1 )∞ 4 ( 2 )( 2 )... (2 r= 1 + ∑ r=1x =r!r∞ 2 ⋅ 1 ⋅ 3L( 2 r − 1) r= 1 + ∑ r =1x =1+r!r∞ 2 ⋅ r !⋅ 1 ⋅ 3L ( 2 r − 1) rx =∑ r =1r !⋅ r !57= 1 + ∑∞r =1(2 ⋅ 4L2 r )(1⋅ 3L (2 r − 1)) rx = 1+r!r!∞  2r∑ r=1  r  x rЗначит, данная функция будет обыкновенной производящей для последовательности 2nan =   , n = 0, 1, … и будет экспоненциальной производящей для последовательности n 2nbn= n!   , n = 0, 1, … . nТеорема 2. Для любого t справедливо тождествоt 2i  2t − 2it=4t−i ∑ i=0  i  (5) 2i♦ Действительно, согласно предыдущей задаче   - коэффициент при xi в i 2t − 2it-i-1/2разложении (1 - 4x)-1/2, а  - коэффициент при x в (1 - 4x) .

Значит левая часть t−i (5) - это коэффициент при xt в произведении (1 - 4x)-1/2 ⋅ (1 - 4x)-1/2. Но (1 - 4x)-1/2 ⋅⋅(1 - 4x)-1/2 = (1 - 4x)-1 = 1 + 4x + (4x)2 + … + (4x)t + …Отсюда получаем тождество (5).Теорема 3. Пусть дана рекуррентная последовательностьF(n) = F(n - 1) + F(n - 2) , F(0) = a, F(1) = bТогда функцияΦ(x) =a + (b − a )x1 − x − x2(6)является (обыкновенной) производящей функцией для чисел F(n).Напишем систему равенствF(0) = aF(1) = bF(2) = F(1) + F(0)…F(n) = F(n - 1) + F(n - 2)Умножаем i-ое уравнение на xi и полученные уравнения сложим. Слева получим функцию Ф(x). Справа получаем в первом столбце xФ(x) - xa + a, во втором столбцеxb + x2Ф(x).58Следовательно, Φ(x) = xΦ(x) - xa + a + xb + x2Φ(x)или (1 - x - x2)Φ(x) = a + (b - a)x, откуда и следует (6).

♦Аналогичным образом производящие функции применяются для решения произвольного линейного рекуррентного соотношения.Пусть дано линейное рекуррентное соотношениеun+k = a1un+k – 1+ ... +akun.Отсюда следует, что справедливы соотношения:uk = a1uk – 1+ ... +aku0uk+1 = a1uk+ ... +aku1. . .un+k = a1un+k – 1+ ... +akunПусть F( x ) =∑ n= 0 u n x n– соответствующая производящая функция. ТогдаимеемF(x) = u0+u1x+ ... +uk – 1xk – 1 +a1(uk – 1xk+ukxk+1+ ...)++a2(uk – 2xk+uk – 1xk+1+ ...)+.

. .+ak(u0xk+u1xk+1+ ...) == u0+u1x+ ... +uk – 1xk – 1 +a1x(uk – 1xk – 1+ukxk+ ...)++a2x2(uk – 2xk – 2+uk – 1xk – 1+ ...)+. . .+akxk(u0+u1x+ ...) == u0+u1x+ ... +uk – 1xk – 1 +a1x(F(x) – u0 – u1x – ... – uk – 2xk – 2)++a2x(F(x) – u0 – u1x – ... – uk – 3xk – 3)+. .

.+akxk(F(x)).Следовательно, справедливо соотношениеF(x)(1 – a1x – a2x2 – ... – akxk) = G(x), гдеG(x) – многочлен степени не выше k – 1, определенный начальными условиями.Отсюда следует равенствоF( x ) =G( x )1 − a1 x − a 2 x 2 −...− a k x kТеорема 4. Пусть дано рекуррентное соотношениеTn = T0 ⋅Tn-1 + T1 ⋅Tn-2 + … + Tn-1 ⋅T0,T0 = 1(7)59Тогда его решением является Tn =1  2 n .n + 1 n ♦ Составим производящую функциюf(x) = T0 + T1x + T2x2 + … + Tnxn + …и положимF(x) = x f(x) = xT0 + T1x2 + … + Tnxn+1 + …и возведем F(x) в квадрат.ИмеемF2(x) = T02 x 2 + (T0 ⋅T1 + T1 ⋅T0)x3 + … + (T0 ⋅Tn-1 + T1 ⋅Tn-2 + … Tn-1 ⋅T0)xn+1 + ...Откуда, используя рекуррентное соотношение, получаемF2(x) = T1x2 + T2x3 + … + Tnxn+1 + ... = F(x) - T0 ⋅xЗначит F2(x) - F(x) + x = 0Решая данное уравнение относительно F(x), получаемF(x) =1 − (1 − 4x)1/ 22(Знак “+” не годится, поскольку F(0) = 0).По формуле бинома имеем коэффициент un при xn :un =1 ( 1 − 1)L ( 1 − n + 1)( −4 x) n ( − 1 )2 222n!=1⋅ 3L (2 n − 3) ⋅ 2 n −1=n!или, умножая и деля на (n - 1) !, получаем=1 ⋅ 3L (2 n − 3) ⋅ 2 ⋅ 4L (2 n − 2) (2 n − 2) !=n !( n − 1)!n !( n − 1)!Поскольку при x <1ряд для F(x) сходится, то все производимые операции за4конны и значит Tn = un+1.Следовательно,Tn =1  2n  ♦n + 1 n Полученные числа Tn называются числами Каталана.

Они появляются во многихкомбинаторных задачах. Приведем таблицу первых значений чисел Tn.n01234567Tn11251442132429Таблица. Числа Каталана60Пример. Найти число способов вычисления неассоциативного произведенияx1 x2 … xn с помощью бинарных умножений.Решение. Пусть un - число способов вычисления данного произведения.Имеем x1 x2 = (x1 x2) и u2 = 1x1 x2 x3 := ((x1 x2) x3), (x1 (x2 x3))и u3 =2Произведение 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Решая квадратное уравнение, получаемf(x) =1 − (1 − 4x)1/ 22(т.к.

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

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