- •Глава I. Азы комбинаторики
- •§ 1. Основные принципы комбинаторики
- •§ 2. Размещения и перестановки без повторений
- •§ 3. Размещения и перестановки с повторениями
- •§ 4. Подмножества конечных множеств и сочетания
- •§ 5. Сочетания с повторениями
- •§ 6. Принцип включения-исключения
- •§ 7. Примеры решения простейших комбинаторных задач
- •§ 8. Примеры других комбинаторных объектов и сводка некоторых результатов
- •Биномиальные коэффициенты
- •Числа Стирлинга
- •Глава II. Рекуррентные соотношения
- •§ 1. Определение и примеры рекуррентных соотношений
- •Основы метода конечных разностей
- •§ 2. Метод производящих функций для нахождения общего решения линейного однородного рекуррентного соотношения второго порядка
- •Алгоритм нахождения общего решения
- •§ 3. Решение линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 4. Метод производящих функций для решения общего линейного однородного рекуррентного соотношения с постоянными коэффициентами
- •Алгоритм нахождения общего решения
- •§ 5. Частные решения линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 6. Некоторые примеры применения производящих функций
Алгоритм нахождения общего решения
Составить характеристическое уравнение k – a1k–1 – … – ak–1 – ak = 0.
Найти все его различные корни 1 , … , s и их кратности r1 , … , rs .
Записать общее решение u(n, c1 , … , ck) = .
Если нужно найти частное решение u(n) с заданными начальными условиями u(0)=u0 , … , u(k–1)=uk–1 , то составляем систему линейных уравнений:
,
из которой однозначно находятся все k констант сij (0 i s, 0 j < ri). Можно доказать (как ?!), что эта система всегда однозначно разрешима.
Примеры: 1. Найти общее решение линейного рекуррентного соотношения f(n + 3) = 3f(n + 2) – 3f(n + 1) + f(n).
Составляем характеристическое уравнение: 3–32+3–1 = ( – 1)3 = 0. Оно имеет единственный корень = 1 кратности r = 3. Значит, общее решение этого соотношения третьего порядка выглядит так: u(n, c0 , c1 , c2) = (c0 + c1n + c2n2)1n = c0 + c1n + c2n2 .
Если требуется соблюсти начальные условия u(0) = 0, u(1) = 1, u(2) = 3, то получается система
,
из которой находим c0 = 0, c1 = = c2 , т.е. un = .
Найти общее решение линейного рекуррентного соотношения
f(n+3) = –f(n+2) – 2f(n+1) + 16·f(n).
С
_ 3
+ 2
+ 2· – 16 |
– 2 3
– 2·2
2
+ 3·
+ 8 _
3·2
+ 2·
– 16
3·2
– 6·
_
8·
– 16
8·
0
оставляем характеристическое уравнение: () = 3 + 2 + 2 – 16 = 0. Угадываем корень 1 = 2 и понижаем степень уравнения, деля характеристический многочлен на – 2. Таким образом, 3 + 2 + 2 – 16 = ( – 2)·(2 + 3· + 8), и решая уравнение 2 + 3· + 8 = 0, находим остальные корни уравнения 2 , 3 = .Все корни различны, т.е. имеют кратности r1 = r2 = r3 = 1. Поэтому общее решение таково: un = 2n·a + ·b + ·c (a, b, c C).
3. Найти общее решение линейного рекуррентного соотношения
f(n+4) = –2·f(n+2) – f(n).
Характеристическое уравнение () = 4 + 2·2 + 1 = 0 раскладывается на множители 4 + 2·2 + 1 = (2 + 1)2, так что имеет два корня 1 = i, 2 = –i кратностей r1 = 2 = r2 . Общее решение записывается так:
un = in·(a·n + b) + (–i)n·(c·n + d).
§ 5. Частные решения линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
Теорема (о частном решении линейного неоднородного рекуррентного соотношения). Для любого линейного рекуррентного соотношения с постоянными коэффициентами
f(n + k) = a1f(n + k – 1) + …+ akf(n) + Tm(n)n,
где Tm(x) – многочлен степени m, С, существует решение вида nrSm(n)n , где Sm(x) – некоторый многочлен степени m, а r – кратность корня в характеристическом уравнении xk – a1xk–1 – … – ak–1x – ak = 0 . В частности, если не является корнем характеристического уравнения, то нужно считать r = 0.
Доказательство. Подставим nr(smnm+…+s1n+s0)n в рекуррентное соотношение:
(здесь всегда можно считать m > r, используя, если необходимо, нулевые коэффициенты многочленов).
В случае, когда не является корнем характеристического многочлена, т.е. r = 0, система упрощается:
Видно, что система имеет верхнетреугольный вид с диагональными элементами () 0, а потому имеет единственное решение.
Если же – это r-кратный корень характеристического многочлена (x), то в силу леммы о соотношениях для r-кратного корня многочлена последняя группа уравнений системы тривиальна: все коэффициенты в ней нулевые. Действительно, эти коэффициенты имеют вид , где u = m+j–r (j = 1, … , r).
При этом
по упомянутой выше лемме.
Более того, система снова верхнетреугольная. В самом деле, если j > u, то коэффициент при su в j-м уравнении первой группы (j r) равен
по лемме о соотношениях для r-кратного корня многочлена, т.к. u+r–j < r при j > u. При j = u коэффициент при su равен
и отличен от нуля по той же лемме.
Если же j > r, то коэффициенты могут быть ненулевыми только для значений u из диапазона j–r u m. При этом
по лемме о соотношениях для r-кратного корня многочлена, т.к. u+r–j < r при j > u. При j = u > r коэффициент при su равен и отличен от нуля по той же лемме.
Таким образом, в любом случае полученная система уравнений крамерова и имеет единственное решение.
Теорема доказана.
Эта теорема упрощает нахождение частных решений для линейных рекуррентных соотношений с постоянными коэффициентами, имеющими свободные члены специального рассмотренного в теореме вида.
Пример. 1. Найти формулу общего члена решения рекуррентного соотношения f(n + 3) = f(n) + 1.
Здесь (x) = x3 – 1 имеет три простых корня 1 = 1, , а свободный член соотношения представим в виде 1 = 1nT0(x), где T0(x) = 1. Таким образом, общее решение однородного соотношения записывается в виде c11n + c22n + c33n, а частное решение неоднородного соотношения – в виде cn1n = cn. Подставляя это выражение в исходное соотношение, получаем соотношение с(n+3) = cn + 1, откуда находим c = .
Таким образом, общее решение рассматриваемого неоднородного соотношения имеет вид c11n + c22n + c33n + .
2. Найти формулу общего члена решения рекуррентного соотношения
f(n + 1) = f(n) + n2 – 1.
Здесь () = – 1 имеет единственный корень = 1, так что общее решение однородного соотношения (n, c) = c.
Частное решение неоднородного соотношения будем искать в виде n·(s2n2+s1n+s0)1n, т.к. свободный член рассматриваемого соотношения имеет вид 1nT2(n), где T2(x) = x2 – 1. Подставляя это выражение в исходное соотношение, получим
s2(n + 1)3+s1(n + 1)2+s0(n + 1) = s2n3 + s1n2 + s0n + n2 – 1,
т.е. 3s2n2+(3s2 + 2s1)n + s2 + s1+s0 = n2 – 1, откуда , а значит, s2 = , s1 = – , s0 = – . Таким образом, общее решение рассматриваемого неоднородного соотношения имеет вид
w(n) = с + ( n3 – n2 – n).