Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Необходимые определения)
(Источники информации)
Строка 103: Строка 103:
  
 
== Источники информации ==
 
== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24
+
* С. А. Ландо {{---}} Лекции о производящих функциях, стр 24
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Производящие функции]]
 
[[Категория: Производящие функции]]

Версия 15:25, 25 марта 2018

Необходимые определения

Определение:
Производящая функция [math]F(t)[/math] называется дробно-рациональной (англ. rational), если она представима в виде отношения двух многочленов, то есть [math]F(t) = \dfrac{P(t)}{Q(t)}[/math], где [math]P(t), Q(t)[/math] — многочлены конечной степени


Отметим, что если [math]p_0 = 0[/math] и [math]q_0 = 0[/math], то оба многочлена могут быть разделены на [math]t[/math]. Разделим оба многочлена на [math]t[/math]. Если после деления [math]p_0[/math] и [math]q_0[/math] остаются равными нулю, то разделим на [math]t[/math] ещё раз. Делить будем до тех пор, пока [math]q_0[/math] и [math]p_0[/math] будут оставаться равными нулю.

Ситуация, при которой [math]q_0 = 0[/math], а [math]p_0 \neq 0[/math], невозможна по правилам деления формальных степенных рядов.

Остаётся ситуация, при которой [math]q_0 \neq 0[/math]. Тогда необходимо разделить [math]P(t), Q(t)[/math] на [math]q_0[/math], чтобы [math]q_0[/math] стало равным [math]1[/math]. В дальнейшем, без ограничения общности, полагаем [math]q_0 = 1[/math]


Определение:
Последовательность [math]a_0, a_1, \ldots, a_n, \ldots [/math] называется линейной рекуррентной последовательностью (англ. constant-recursive sequence), если её члены [math]a_0 \ldots a_{k - 1} [/math] заданы, а [math]\forall n \geqslant k [/math] выполняется [math] a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}[/math]


Условные обозначения

В дальнейшем будем придерживаться следующих условных обозначений:

Будем обозначать [math][t^n]X(t)[/math] коэффициент при [math]t^n[/math] в [math]X(t)[/math]

[math][t^n]A(t) = a_n[/math]

[math][t^n]Q(t) = q_n[/math]

[math][t^n]P(t) = p_n[/math]

[math][t^n]F(t) = f_n[/math]

Теорема о связи этих понятий

Теорема:
Последовательность [math]a_0, a_1, \ldots, a_n, \ldots [/math] является линейно рекуррентной с [math]k[/math] первыми заданными членами [math]\Leftrightarrow[/math] её производящая функция [math]A(t)[/math] является дробно-рациональной, причём представимой в виде [math]A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) \lt k[/math]
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow)[/math]. Пусть [math]A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) \lt k[/math]. Тогда [math]A(t) \cdot Q(t) = P(t)[/math]. Пусть [math]Q(t)[/math] имеет вид [math]Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k[/math].

Так как [math]deg(P) \lt k[/math], то для [math]\forall n \geqslant k [/math] выполнено [math]p_n = 0[/math]. Расписывая [math]p_n[/math] по определению произведения степенных рядов, получаем [math]\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0[/math]

Тогда [math]a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0[/math] (так как [math]deg(Q) = k[/math])

Так как [math]q_0 = 1[/math], а [math]q_i = -c_i[/math], то [math]a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0[/math]

Тогда [math]a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}[/math]

[math]\Rightarrow)[/math]

Напишем друг под другом несколько производящих функций:

[math]A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots[/math]

[math]-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots[/math]

[math]-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots[/math]

[math]\cdots[/math]

[math]-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots[/math]

Почленно складывая эти формальные степенные ряды, получаем

[math]A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_{k - 1} - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots[/math]

Так как [math]\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}[/math], то все коэффициенты при степенях, начиная с [math]k[/math]-ой включительно, обнулятся.

Тогда [math]A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_{k - 1} - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}[/math].

Обозначим [math]Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)[/math],

а [math]P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_{k - 1} - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}[/math]

Тогда [math]A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) \lt k[/math]
[math]\triangleleft[/math]

Примеры применения теоремы

  • Вычислим производящую функцию последовательности [math]a_0 = 1, a_n = k \cdot a_{n - 1}[/math]
    Так как последовательность является линейно рекуррентной, её производящая функция, согласно теореме, имеет вид [math]F(t) = \dfrac{P(t)}{Q(t)}[/math], где [math]Q(t) = 1 - k \cdot t[/math] (так как [math]c_1 = k[/math]), а [math]deg(P) \lt 1[/math].
    Будем искать производящую функцию в виде [math]F(t) = \dfrac{C}{1 - k \cdot t}, C \in \mathbb{R}[/math]
    Пусть [math]F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots [/math], тогда [math]a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots = \dfrac{C}{1 - k \cdot t}[/math], следовательно [math](a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots a_n \cdot t^n + \ldots) \cdot (1 - k \cdot t) = C[/math]
    Пользуясь правилом перемножения формальных степенных рядов, получаем
    [math] C = a_0 \cdot 1 = 1 \cdot 1 = 1[/math]
    Следовательно, [math] F(t) = \dfrac{1}{1 - k \cdot t}[/math]
    Таким образом, [math] 1 + k \cdot t + (k \cdot t)^2 + \ldots + (k \cdot t)^n + \ldots = \sum\limits_{n = 0}^{\infty}(k \cdot t)^n = \dfrac{1}{1 - k \cdot t}[/math]
    Частным случаем этой формулы являются соотношения [math]1 + t + t^2 + \ldots t^n + \cdots = \sum\limits_{n = 0}^{\infty}t^n =\dfrac{1}{1 - t}[/math] и [math]1 - t + t^2 + \ldots (-1)^n \cdot t^n + \cdots = \sum\limits_{n = 0}^{\infty}(-1)^n \cdot t^n = \dfrac{1}{1 + t}[/math]
  • Вычислим производящую функцию последовательности Фибоначчи [math]f_0 = f_1 = 1, f_n = f_{n - 1} + f_{n - 2}[/math]
    Так как последовательность является линейно рекуррентной, её производящая функция, согласно теореме, имеет вид [math]F(t) = \dfrac{P(t)}{Q(t)}[/math], где [math]Q(t) = 1 - t - t^2[/math] (так как [math]c_1 = c_2 = 1[/math]), а [math]deg(P) \lt 2[/math].
    Будем искать производящую функцию в виде [math]F(t) = \dfrac{B + At}{1 - t - t^2}, A, B \in \mathbb{R}[/math]
    Пусть [math]F(t) = f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots [/math], тогда [math]f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots = \dfrac{C}{1 - t - t^2}[/math], следовательно [math](f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots) \cdot (1 - t - t^2) = B + At[/math]
    Пользуясь правилами перемножения формальных степенных рядов, получаем [math]p_n = \sum\limits_{i = 0}^{n} f_i \cdot q_{n - i}[/math], в частности, [math]B = f_0 \cdot q_0 = 1 \cdot 1 = 1[/math], а [math]A = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 1 - 1 = 0[/math]
    Таким образом, [math]F(t) = \dfrac{1}{1 - t - t^2}[/math]

См. также

Источники информации

  • С. А. Ландо — Лекции о производящих функциях, стр 24