В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 8
Текст из файла (страница 8)
Таким образом, v (x) — действительно производящая функция последовательностичисел Каталана. Сразу можно показать общую формулу для них:(2n − 2)!2n − 111 2n − 2un ==·=.n! (n − 1)!n2n − 1 n n − 1Числа Каталана играют важную роль во многих комбинаторных задачах. Так, например, если обозначить an —число способов разбить (n + 2)-угольник на треугольники, то оно будет являться числом Каталана индекса на единицубольше: n−1(2n)!12nan = ∑ al an−` , an = un+1 ==.n!(n+1)!n+1n`=1Другим примером является точная оценка числа деревьев (имеется ввиду их укладок на плоскости) на n вершинах.
Действительно, между последовательностями из нулей и единиц длины 2n, кодирующими деревья и расстановками скобокможно установить изоморфизм: в каждом префиксе число единиц (открывающихся скобок) не меньше числа нулей(закрывающихся скобок). Этот же результат может быть сформулирована по-другому: число путей в целочисленнойрешетке от вершины (0, 0) к вершине (n, n), проходящих под диагональю.Рассмотрим для последовательности {an }∞n=0 линейное неоднородное рекуррентное соотношение с постояннымикоэффициентами:an+r − p1 an+r−1 − · · · − pr an = f (n) .Общее решение неоднородного соотношения an представляется в виде суммы общего решения однородного соотношения a0n и некоторого частного решения неоднородного: an = a0n + a00n .
Частное решение ищется достаточно просто вслучае f (n) = λ n Pm (n). Тогда если h (λ ) = 0 кратности k, где h (x) = 0 — характеристическое уравнение, то частноерешение ищется в виде nk Qm (n) λ n , где Qm (m) — полином степени m.Рассмотрим некоторую последовательность чисел {an }∞n=0 из поля F. Наряду с обычной производящей функцией∞A (x) =∑ an xnn=0введем экспоненциальную производящую функцию:Ae (x) =∞an∑ n! xn .n=0∞∞Для производящих функций этих двух видов последовательностей {an }∞n=0 , {bn }n=0 , {cn }n=0 выполняются очевидныесвойства:A (x) = B (x) ⇐⇒ an = bn ,A (x) + B (x) = C (x) ⇐⇒ an + bn = cn ,nA (x) · B (x) = C (x) ⇐⇒∑ ak bn−k = cn ,k=0Ae (x) = Be (x) ⇐⇒ an = bn ;Ae (x) + Be (x) = Ce (x) ⇐⇒ an + bn = cn ;n neeeA (x) · B (x) = C (x) ⇐⇒ ∑ak bn−k = cn .k=0 k(1.25)(1.26)(1.27)Соотношение (1.25) называется также принципом равенства, а случай экспоненциальных производящих функций(1.27) легко запомнить, используя следующее мнемоническое правило: надо раскрыть правую часть (a + b)n = cn , используя формулу бинома Ньютона, и перевести все степени в индексы.
В случае полей R или C соответствующие бесконечные алгебры многочленов R [[x]] и C [[x]] получили название алгебры Коши, а Re [[x]] и Ce [[x]] — формальногоисчисления Блиссара.Принцип Лагранжа. Если формальные степенные ряды существуют в некоторой ненулевой окрестностинуля как аналитические функции, то над ними можно осуществлять любые допустимые операции как надфункциями.Из принципа Лагранжа вытекает в частности, что в случае сходимости ряда его можно дифференцировать по следующему правилу:∞∞dA (x) = ∑ an xn =⇒ A (x) = ∑ nan xn−1 .dxn=0n=1Это корректно в силу теоремы Коши-Адамара, утверждающей, что если степенной ряд сходится в некоторой ненулевойокрестности нуля, то он сходится абсолютно, и того факта, что сходимость ряда из производных равномерна.Пусть дана последовательность {an }∞n=0 чисел с известной производящей функцией A (x). Требуется найти последовательность Sn = a0 + a1 + · · · + an .
Легко видеть, что производящая функция этой последовательности будет выглядетьтак:A (x).S (x) =1−x271.2. ПРОИЗВОДЯЩИЕ ФУНКЦИИПусть для начала ai = i, ∀ i > 0. Для любого 0 < ε < 1 ряд A (x) сходится в окрестности нуля (−1 + ε, 1 − ε) к1dx1.A (x) = x ·= 0 + 1 · x + 2 · x2 + · · · + n · xn + · · · =dx 1 − x(1 − x)2ТогдаS1 (x) =иx(1 − x)3(n + 2) (n + 1)n+1(−3) (−3 − 1) · · · (−3 − n + 1)· (−1)n ==.n!2!2Sn1 =В качестве еще одного примера рассмотрим ai = i2 , ∀ i > 0. Для любого 0 < ε < 1 ряд A (x) сходится в окрестности нуля(−1 + ε, 1 − ε) кdd1x (x + 1)x·= 0 + 1 · x + 4 · x2 + · · · + n2 · xn + · · · =A2 (x) = x ·.dxdx 1 − x(1 − x)3ТогдаS2 (x) =x (x + 1)4(1 − x)= x2 + x∞(−4) (−5) · · · (−4 − n + 1)(−1)n xn =n!n=0∑x2 + x∞(n + 3) (n + 2) (n + 1) nx3!n=0∑и1n (n + 1) (2n + 1)((n + 2) (n + 1) n + (n + 1) n (n − 1)) =.66Сумму первых n кубов можно также найти, используя аппарат производящих функций, но есть и более изящный способ, основанный на тождестве, которое легко доказывается по индукции: (1 + 2 + · · · + n)2 = 13 + 23 + · · · + n3 , то естьn+1 23Sn =.2Sn2 =Основные свойства обычных производящих функций.fn1 = fn2fn =fn1 + fn2(0,Fn =fn−1n = 0,иначе;Fn = fn+1⇐⇒ f1 (x) = f2 (x) ;(1.28)⇐⇒ f (x) = f1 (x) + f2 (x) ;(1.29)⇐⇒ F (x) = x · f (x) ;(1.30)⇐⇒ F (x) =f (x) − f0,x( f0 = f (0)) ;(1.31)k−1f (x) − ∑ fr xrFn = fn+kFn = k · fnFn = α n fnFn = n · fnnFn =∑ frr=0(0,n = 1, k − 1,Fn =fn−k , n > k,r=0⇐⇒ F (x) =xk⇐⇒ F (x) = k · f (x) ;⇐⇒ F (x) = f (αx) ;d⇐⇒ F (x) = x f (x) ;dxf (x)⇐⇒ F (x) =;1−x;(1.32)(1.33)(1.34)(1.35)(1.36)⇐⇒ F (x) = xk f (x) ;(1.37)⇐⇒ F (x) = f (x) · g (x) ;(1.38)nFn =∑ fr gn−rr=0Fn = fn+1 − fn1 N∑ fnN→∞ Nn=0⇐⇒ F (x) =(1 − x) f (x) − f0;x1 Nlim (1 − x) · f (x) ;∑ fn = x→1N→∞ Nn=0∃ lim=⇒ lim∃ lim fn=⇒ lim fn = lim (1 − x) f (x) .n→∞n→∞x→1(1.39)(1.40)(1.41)28ГЛАВА 1.
КОМБИНАТОРИКАОсновные преобразования обычных производящих функций.(1,fn =0,(1,fn =0,n = 0,n > 1,⇐⇒ f (x) ≡ 1;(1.42)n = k,n 6= k,⇐⇒ f (x) = xk ;(1.43)1;1−x1f (x) =;1 − αxαxf (x) =;(1 − αx)2axf (x) =;(1 − x)21;f (x) =(1 − αx) p1f (x) =;(1 − αx) pdf (x) = x · g (x) , где gn = nk−1 ;dxαx (1 + αx)f (x) =;(1 − αx)3αx α 2 x + 4αx + 1f (x) =;(1 − αx)4df (x) = x g (αx) , где gn = nk−1 ;dxfn ≡ 1⇐⇒ f (x) =(1.44)fn = α n⇐⇒(1.45)fn = n · α n⇐⇒fn = a · n⇐⇒n+ p−1 nfn =α , n > 0, p > 1n⇐⇒fn = n2⇐⇒fn = nk⇐⇒fn = n2 α n⇐⇒fn = n3 α n⇐⇒fn = nk α n( kα n β k − n, k > n,fn = n0,n > k,(0,n = 0,fn = α nn , n > 1,(0,n — четное,fn = α n,n— нечетное,n(0,n = 0 ∨ n — нечетное,fn = α nn , n > 2 & n — четное,⇐⇒fn =fn =fn =αnn!(0,αnn! ,n — четное,n — нечетное,(0,n = 0 ∨ n — нечетное,n! , n > 2 & n — четное,αnfn =(ln α)nn!(1.48)(1.49)(1.50)(1.51)(1.52)(1.53)(1.54)⇐⇒ f (x) = − ln (1 − αx) ;(1.55)⇐⇒ f (x) = Arctg (αx) =11 + αxln;21 − αx(1.56)1⇐⇒ f (x) = − ln 1 − α 2 x2 ;2(1.57)⇐⇒ f (x) = eαx ;(1.58)⇐⇒ f (x) =eαx − e−αx= sh x;2(1.59)⇐⇒ f (x) =eαx + e−αx= ch x;2(1.60)⇐⇒ f (x) = α x ;⇐⇒ f (x) =fn = cos αn⇐⇒ f (x) =fn = a−β n cos αn(1.47)⇐⇒ f (x) = (β + αx)k ;fn = sin αnfn = a−β n sin αn(1.46)(1.61)x sin αx2 − 2x cos α + 1;1 − x cos α;x2 − 2x cos α + 1x sin α⇐⇒ f (x) = −β 2;a x − 2x cos α + aβaβ − x cos α;⇐⇒ f (x) = −β 2a x − 2x cos α + aβ(1.62)(1.63)(1.64)(1.65)291.2.
ПРОИЗВОДЯЩИЕ ФУНКЦИИx sh α;x2 − 2x ch α + 11 − x ch α⇐⇒ f (x) = 2;x − 2x ch α + 1x sh α⇐⇒ f (x) = −β 2;a x − 2x ch α + aβaβ − x ch α⇐⇒ f (x) = −β 2.a x − 2x ch α + aβ⇐⇒ f (x) =fn = sh αnfn = ch αnfn = a−β n sh αnfn = a−β n ch αn(1.66)(1.67)(1.68)(1.69)Примеры.1. Найти an по рекуррентным соотношениям и начальным условиям:(a) an+2 − 4an+1 + 3an = 0, a1 = 10, a2 = 16. Решение. Для начала найдем, что a0 = 8, и заменим начальные условия на эквивалентные a0 = 8, a1 = 10.Характеристическим уравнением этой последовательности является x2 − 4x + 3 = 0. Оно имеет два вещественных корня кратности один: α1 = 1, α2 = 3. Таким образом, общее решение данного линейного однородного рекуррентного соотношения с постоянными коэффициентами выписывается в виде an = C1 +C2 · 3n .
Изначальных условий получаем, что C1 +C2 = 8, C1 + 3C2 = 10 ⇒ C1 = 7, C2 = 1. Таким образом, окончательноan = 7 + 3n .(b) an+3 − 3an+1 + 2an = 0, a1 = a, a2 = b, a3 = c. Решение. Для начала найдем, что a0 = 3a−cи заменим начальные условия на эквивалентные a0 =23a−c32 , a1 = a, a2 = b. Характеристическим уравнением для последовательности является x − 3x + 2 = 0.
Оноимеет вещественный корень α1 = 1 кратности два и вещественный корень α2 = −2 кратности один. Такимобразом, общее решение данного линейного однородного рекуррентного соотношения с постоянными коэффициентами выписывается в виде an = C1 +C2 n +C3 (−2)n . Из начальных условий получаем, что, C1 = 14a−b−4c C1 +C3 = 3a−c92 ,C1 +C2 − 2C3 = a, ⇐⇒C2 = b−2a+c,3C1 + 2C2 + 4C3 = b;C3 = 2b−a−c18 .Таким образом, окончательно an =14a−b−4c9+ b−2a+cn + 2b−a−c(−2)n .318(c) an+2 − 2 cos αan+1 + an = 0, a1 = cos α, a2 = cos 2α.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
