В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 7
Текст из файла (страница 7)
Поведение этих чисел22ГЛАВА 1. КОМБИНАТОРИКАможно показать на таблице.b kn b012345601000000123450000010000−110002 −3100−611−61024 −5035 −101−120 274 −22585 −1560000001........................×(1−n)......n−1, n−1,k−1kn,k...Из свойств коэффициентов перехода от одного базиса к другому вытекает справедливость равенства∞∑ s (n, k) S (k, m) = δnm .k=0Начальные условия в свою очередь могут задаваться двумя способами: s (0, 0) = 1,s (n, n) = 1, n > 0,s (n, 0) = 0, n > 1;или s (0, 0) = 1,s (0, k) = 0, k > 1s (n, 0) = 0, n > 1.Перед тем, как перейти к содержательному смыслу, связанному с числами Стирлинга первого рода, отметим, что ихмодулю растет достаточно быстро, значительно быстрей, чем числа Стирлинга второго рода.
Так, например, s (10, 3) =−1026576.Обозначим за c (n, k) число перестановок из n элементов, которые представляются в виде произведения k простыхциклов (перестановки вида π = [. . . ]1 [. . . ]2 · · · [. . . ]k ). Понятно, чтоc (n, n) = 1, c (n, 1) = n!/n = (n − 1)! = |s (n, 1)| .Далее, очевидно, чтоc (n, k) = c (n − 1, k − 1) + (n − 1) c (n − 1, k) .Это равенство доказывается тем же самым приемом с уникальным элементом, что и теоремы 1.3 и 1.5. В то же времяc (n, k) = (−1)n−k s (n, k) = |s (n, k)| .Таким образом, если знакопеременной двухиндексной последовательности чисел Стирлинга первого рода трудно приписать комбинаторный смысл, то модули этих чисел имеют вполне конкретный содержательный смысл: они выражаютчисло перестановок, представляющихся в виде произведения заданного числа циклов.Рекуррентные соотношения и производящие функции.
Пусть u0 , u1 , . . . , un , . . . — последовательность (например,из поля комплексных чисел). Тогда формальный степенной рядf (x) = u0 + u1 x + u2 x2 + · · · + un xn + · · ·называется производящей функцией последовательности {un }∞n=0 . Если этот степенной ряд сходится, то следующие формально введенные операции приобретают общепринятый смысл. Для производящей функцииg (x) = v0 + v1 x + v2 x2 + · · · + vn xn + · · ·последовательности v0 , v1 , . .
. , vn , . . . над тем же полем естественным образом вводятся линейные комбинации производящих функций α f (x) + β f (x), а также произведение:∞f (x) · g (x) = h (x) =∑ wn xn ,n=0231.2. ПРОИЗВОДЯЩИЕ ФУНКЦИИгдеnwn = u0 vn + u1 vn−1 + · · · + ui vn−i + · · · + un v0 = ∑ ui vn−i .i=0−1 (x): f (x) ·Если u0 6= 0, то для производящей функции последовательности {un }∞n=0 существует обратный элемент f−1f (x) = 1, формальный ряд которого определяется следующим образом:1u0v0 · u1⇒ v1 = −u0...u1 vn−1 + · · · + ui vn−i + · · · + un v0⇒ vn = −u0...0 = v0 · u0⇒ v0 =0 = v0 · u1 + v1 · u00 = u0 · vn + u1 vn−1 + · · · + ui vn−i + · · · + un v0Рассмотрим известный пример последовательности Фибоначчи F0 , F1 , . .
., задаваемой начальными условиями F0 =F1 = 1 и рекуррентным соотношением Fn+2 = Fn+1 + Fn . Первые ее пять членов будут равны:F0 = 1,F1 = 1,F2 = 2,F3 = 3,F4 = 5,F5 = 8.Найдем ее производящую функцию. Поскольку последовательность, легко видеть положительная и строго возрастающая (Fn+1 > Fn ), а Fn+1 = Fn + Fn−1 , легко заключить, что Fn+1 < 2Fn ⇒ Fn < 2n .
Таким образом, производящая функцияпоследовательности∞f (x) =∑ Fn xn(1.21)n=0сходится в открытом круге R < 21 . В нем допустимы следующие действия:f (x) = F0−x f (x) =−x2 f (x) =+F1 x−F0 x+F2 x2−F1 x2−F0 x2+F3 x3 + · · ·+Fn xn + · · ·3−F2 x − · · · −Fn+1 xn+2 − · · ·−F1 x3 − · · ·−Fn xn+3 − · · ·Сложим эти три равенства. Заметим при этом, что согласно рекуррентному определению чисел Фибоначчи коэффициенты при всех степенях, начиная со второй, обнулятся:1 − x − x2 f (x) = F0 + (F1 − F0 ) x =⇒ f (x) =1.1 − x − x2Обозначим k (x) = 1 − x − x2 — многочлен, обратный к производящей функции последовательности. Характеристическим многочленом называется функция√√ 11− 51+ 5h (x) = x2 k= x2 − x − 1 = (x − α1 ) (x − α2 ) , где α1 =, α2 =.x22Отсюда легко видеть, чтоk (x) = x2 h 1= (1 − α1 x) (1 − α2 x) .xТаким образом, производящую функцию можно разложить на простые дроби следующим образом:f (x) =11AB==+,1 − x − x2(1 − α1 x) (1 − α2 x) 1 − α1 x 1 − α2 xгде A и B определяются из системы линейных уравненийA+B= 1,−α2 A − α1 B = 0.Решением являются значения A =√1+√ 52 5√=α1√,5α2√ 5 = −√B = − 1−.
Теперь можно разложить производящую функцию в2 55степенной ряд по степеням x, используя то, что∞f (x) = A ∑n=0α1n xn + B∞∑n=011−zα2n xn= 1 + z + z2 + · · ·.∞=∑n=0(Aα1n + Bα2n ) xn∞=∑n=0α1n+1 α2n+1√ − √55!xn .(1.22)24ГЛАВА 1. КОМБИНАТОРИКАПриравнивая коэффициенты при равных степенях в (1.21) и (1.22), получаем√ !n+1√ !n+1 11+51−51.−Fn = √ α1n+1 − α2n+1 = √ 2255Числа Фибоначчи имеют понятный содержательный смысл: для n > 1 это число двоичных последовательностей длины n − 1, у которых никакие две единицы не стоят рядом.
Легко понять, что fn+2 = Fn+3 путем выделения последнегоразряда складывается из последовательностей длины n + 1, у которых никакие две единицы не стоят рядом с выделенным разрядом нулем и последовательностей длины n, у которых никакие две единицы не стоят рядом с выделеннымразрядом единицей: fn+2 = fn+1 + fn .Пусть дана последовательность {un }∞n=0 над некоторым полем. Линейных однородным рекуррентным соотношениемс постоянными коэффициентами порядка r называется равенство видаun+r − p1 un+r−1 − p2 un+r−2 − · · · − pr−1 un+1 − pr un = 0.При известных начальных условиях u0 , u1 , .
. . , ur−1 при его помощи может быть достаточно легко найден общий вид uk .Действительно, если производящая функция для этой последовательности равна∞u (x) =∑ un xn ,x ∈ C,n=0то, поступая также, как и в случае последовательности Фибоначчи, получимk (x) = 1 − p1 x − p2 x2 − · · · − pr xr .Имеем,k (x) · u (x) = C (x) ,degC (x) 6 r − 1,что также ясно из рассмотренного выше примера последовательности Фибоначчи. Поступаем далее аналогично: 11rr−1rrh (x) = x k= x − p1 x − · · · − pr , k (x) = x hxxи по основной теореме алгебры существует единственное представлениеh (x) = xr − p1 xr−1 − · · · − pr = (x − α1 )s1 (x − α2 )s2 · · · (x − αq )sq ,s1 + s2 + · · · + sq = r.Отсюда способ нахождения явного выражения для степенного ряда производящей функцииu (x) =q siβi jC (x).sq = ∑ ∑(1 − α1 x) · · · (1 − αq x)(1−αi x) ji=1 j=1s1(1.23)В качестве еще одного примера можно найти, какую последовательность определяет производящая функция1.(1 − αx)nДля этого воспользуемся разложением в ряд функции1(−1) (−n − 1) · · · (−n − m + 1) m(1 + z)−n = 1 + (−n) z + (−n) (−n − 1) · z2 + · · · +z +··· .2m!Тогда∞∞1(−n) (−n − 1) · · · (−n − m + 1)(n + m − 1) · · · (n + 1) n m m(−αx)m = ∑α x =n = ∑(1 − αx)m!m!m=0m=0∞ ∞ n+m−1 m mn+m−1 m mα x , (1.24)∑ n−1 α x = ∑mm=0m=0= Pn−1 (m), выступающийто есть это — производящая функция чисел сочетаний с повторениями.
Заметим, что n+m−1n−1в роли коэффициента при α m xm в сумме (1.24), является многочленом от m степени n − 1. Используя этот факт, окончательное выражение для производящей функции можно переписать несколько иначе, подставив разложение (1.24) в(1.23):!q siq∞βi jnu (x) = ∑ ∑= ∑ ∑ Q6si−1 (n) αi xn .j(1−αx)ii=1 j=1n=0 i=1251.2. ПРОИЗВОДЯЩИЕ ФУНКЦИИИсходя из r начальных условий можно получить общий член последовательности из линейной системы уравнений:qun = ∑ Q6si −1 (n) αin .i=1Найдем теперь производящую функцию∞∞∑ ∑ fn,k xn ykF (x, y) =n=0 k=0двухиндексной последовательности чисел сочетаний с повторениями fn,k = n−k+1, задаваемой линейным рекурkрентным соотношениемf−f−f=0,чтопродемонстрированонатаблице(1.10).
Легко получить, чтоn,kn−1,kn−2,k−11 − x − x2 y F (x, y) = 1 + xy. ТогдаF (x, y) =∞∞1 + xy= (1 + xy) ∑ x` (1 + xy)` = ∑ x` (1 + xy)`+1 =1 − x (1 + xy)`=0`=0∞`+1 ∞∞ ∞ ∞ `+1 m m`+1 m m` + 1 `+m m``∑x ∑ m x y = ∑x ∑ m x y = ∑ ∑ m x y .`=0 m=0`=0 m=0`=0 m=0Выполняя замену переменных n = ` + m, k = m, получаем∞F (x, y) =∞∑∑n=0 k=0n−k+1 n kx y.kТаким образом, получено, что единственным решениемлинейного однородного рекуррентного соотношения с постоянными коэффициентами (1.9) является fn,k = n−k+1.kОпределение 1.2.4.
Числом Каталана un называется число способов корректной расстановки скобок в произведении n сомножителейx1 · x2 · · · xn .Очевидно, что u0 = 0, u1 = u2 = u1 ·u2 = 1 и числа Каталана удовлетворяют следующему соотношению un = u1 ·un−1 +u2 · un−2 + · · · + un−1 · u1 , n > 2. Действительно, первый сомножитель в каждом слагаемом указывает число способоврасстановки скобок слева, а второй — справа. Заметим, что ничего не изменится, если это соотношение дополнитьдвумя нулевыми слагаемыми:un = u0 · un + u1 · un−1 + · · · + un · u0 , n > 2.Производящая функция последовательности чисел Каталана∞∑ un xnu (x) =n=0удовлетворяет простому соотношению: u2 (x) = −x + u (x). Действительно, возведем ее в квадрат и соберем коэффициенты при равных степенях: u2 (x) = 0+0·x+u2 ·x2 +u3 ·x3 +· · · = −x+u (x).
Заметим, что это тождество выполняется какформальное для рядов. В действительности решить это функциональное уравнение традиционными методами не удается, так как неизвестно, сходится этот формальный ряд или нет. Поэтому прибегают к следующему приему: рассмотримфункцию√1 − 1 − 4x1|x| < ,v (x) =;24удовлетворяющую этому же функциональному отношению и аналитическую в открытом круге с центром в нуле ненулевого радиуса. Осталось доказать только начальные условия: очевидно, что коэффициент разложения v (x) в ряд постепеням x∞v (x) =∑ vn · xnn=0и v0 = v (0).
Надо найти v1 . Разложим для этого в ряд функцию(1 + z)m =∞∑ an · zn ,n=0Отсюда1vn = −21212−1 ···n!12−n+1(−4)n =an =12√1 − 4x. Используем известное разложениеm (m − 1) · · · (m + 1 − n) n·z .n!1 12 · 12 · 32 · · · 2n−324n =2n!1 · 3 · · · (2n − 3) n−1 1 · 3 · · · (2n − 3) · 2 · 4 · · · (2n − 2)(2n − 2)!2==.n!n! (n − 1)!n! (n − 1)!26ГЛАВА 1. КОМБИНАТОРИКАОтсюда получается, что v1 = u1 = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
