- •Глава I. Азы комбинаторики
- •§ 1. Основные принципы комбинаторики
- •§ 2. Размещения и перестановки без повторений
- •§ 3. Размещения и перестановки с повторениями
- •§ 4. Подмножества конечных множеств и сочетания
- •§ 5. Сочетания с повторениями
- •§ 6. Принцип включения-исключения
- •§ 7. Примеры решения простейших комбинаторных задач
- •§ 8. Примеры других комбинаторных объектов и сводка некоторых результатов
- •Биномиальные коэффициенты
- •Числа Стирлинга
- •Глава II. Рекуррентные соотношения
- •§ 1. Определение и примеры рекуррентных соотношений
- •Основы метода конечных разностей
- •§ 2. Метод производящих функций для нахождения общего решения линейного однородного рекуррентного соотношения второго порядка
- •Алгоритм нахождения общего решения
- •§ 3. Решение линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 4. Метод производящих функций для решения общего линейного однородного рекуррентного соотношения с постоянными коэффициентами
- •Алгоритм нахождения общего решения
- •§ 5. Частные решения линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 6. Некоторые примеры применения производящих функций
Алгоритм нахождения общего решения
По заданному соотношению f(n+2) = a1f(n+1) + a2f(n) составляем характеристическое уравнение () = 2 – a1 – a2 ;
Находим корни 1 и 2 этого уравнения ;
Если 1 2 , то u(n) = c11n + c22n ;
Если 1 = = 2 , то u(n) = (c1 + с2n)n .
Пример. Для последовательности Фибоначчи рекуррентное соотношение имеет вид f(n+2) = f(n+1) + f(n) (n N0) . Характеристическое уравнение
() = 2 – – 1 = ( – 1)( – 2)
имеет два различных корня 1 = , 2 = . Поэтому общее решение записывается в виде un = c1 +c2 .
Для последовательности с условиями f(0) = 0, f(1) = 1 получим
c1 +c2 = 0, c1 +c2 = 1,
т.е. . Таким образом,
un = .
Эта последовательность u0 = 0, u1 = 1, u2 = 1, u3 = 2, u4 = 3, u5 = 5, … отличается от последовательности чисел Фибоначчи сдвигом: f0 = 1, f1 = 2, f2 = 3, f4 = 5, … Таким образом, из формулы для un получаем
fn = .
Это – формула Бине для чисел Фибоначчи.
§ 3. Решение линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
Рассмотрим теперь неоднородное линейное рекуррентное соотношение второго порядка с постоянными коэффициентами
f(n+2) = a1f(n+1) + a2f(n) + nTm(n),
где – заданное комплексное число, Tm(x) = tmxm + … + t1x + t0 – известный многочлен степени m. Правую часть вида nTm(n), участвующую в этом соотношении, будем называть специальной.
Теорема (о частном решении линейного неоднородного рекуррентного соотношения второго порядка с постоянными коэффициентами и специальной правой частью). Для любого неоднородного линейного рекуррентного соотношения с постоянными коэффициентами вида
f(n+2) = a1f(n+1) + a2f(n) + nTm(n),
где C , Tm(x) = tmxm + … + t1x + t0 – многочлен степени m, существует частное решение вида v(n) = nnrSm(n), где r – кратность корня в характеристическом уравнении (x) = x2 – a1x – a2 (т.е. r = 0, если – не корень, r = 1, если – один из двух различных корней, r = 2, если – единственный двукратный корень характеристического уравнения), Sm(x) – некоторый многочлен степени не выше m: Sm(x) = smxm + … + s1x + s0 .
Доказательство. Положим v(n) = nnr(smnm + … + s1n + s0) и подберём числа sm , … , s0 так, чтобы получилось решение данного рекуррентного соотношения.
v(n + 2) – a1v(n + 1) – a2v(n) = n(tmnm + … + t1n + t0)
n+2(sm(n+2)m+r+sm–1(n+2)m+r–1+…+s1(n+2)1+r+s0(n+2)r) –
– a1n+1( sm(n+1)m+r+sm–1(n+1)m+r–1+…+s1(n+1)1+r+s0(n+1)r) +
+ a2n( smnm+r+sm–1nm+r–1+…+s1n1+r+s0nr) =
= n(tmnm + … + t1n + t0) {: n 0}
2(sm(n+2)m+r+sm–1(n+2)m+r–1+…+s1(n+2)1+r+s0(n+2)r) –
– a1( sm(n+1)m+r+sm–1(n+1)m+r–1+…+s1(n+1)1+r+s0(n+1)r) +
+ a2( smnm+r+sm–1nm+r–1+…+s1n1+r+s0nr) =
= tmnm + … + t1n + t0
sm[2(n+2)m+r – a1(n+1)m+r – a2nm+r] + …
… + si[2(n+2)i+r – a1(n+1)i+r – a2ni+r] + …
… + s0[2(n+2)r – a1(n+1)r – a2nr] =
= tmnm + … + t1n + t0 .
Рассмотрим три возможные случая, обозначенные в теореме:
1. – не корень характеристического уравнения. Тогда r = 0, и последнее соотношение приобретает следующий вид:
sm[2(n+2)m – a1(n+1)m – a2nm] + …
… + si[2(n+2)i – a1(n+1)i – a2ni] + …
… + s0[2(n+2)0 – a1(n+1)0 – a2n0] =
= tmnm + … + t1n + t0 {бином Ньютона}
sm[2(nm+ nm–12+…+ n2m–1+2m) – a1(nm+ nm–1+…+ n+1)–a2nm]+ …
… + si[2(ni+ ni–12+…+ n2i–1+2i) – a1(ni+ ni–1+…+ n+1) – a2ni] + …
… + s0[2 – a1 – a2] = tmnm + … + t1n + t0
sm[(2–a1–a2)nm +(2 2 – a1 )nm–1 +...+(22m – a1)]+ …
… + si[(2–a1–a2)ni +(2 2 – a1 )ni–1 +...+(22i – a1)]+ …
…+ s0[2 – a1 – a2] = tmnm + … + t1n + t0 .
Для определения чисел s0 , s1 , … , sm приравняем коэффициенты при одинаковых степенях n, получив систему уравнений:
из которой последовательно и однозначно находятся все числа sm , sm–1 , … , s0 .
2. = 1 2 – простой корень характеристического уравнения. Тогда r = 1, и исследуемое соотношение приобретает следующий вид:
sm[2(n+2)m+1 – a1(n+1)m+1 – a2nm+1] + …
… + si[2(n+2)i+1 – a1(n+1)i+1 – a2ni+1] + …
… + s0[2(n+2)1 – a1(n+1)1 – a2n1] =
= tmnm + … + t1n + t0 {бином Ньютона}
sm[2(nm+1+ +2m+1) – a1(nm+1+ +1) – a2nm+1] + …
… + si[2(ni+1+ +2i+1) – a1(ni+1+ +1) – a2ni+1] +…
… + s0[2(n+2) – a1(n+1) – a2n] =
= tmnm + … + t1n + t0
sm[(2 – a1 – a2)nm+1+ + (22m+1 – a1)] + …
…+si[(2 – a1– a2)ni+1+ + (22i+1 – a1)] + …
… + s0[(2 – a1 – a2)n + 22 – a1] = tmnm + … + t1n + t0 .
Учитывая, что 2 – a1 – a2 = 0 и приравнивая коэффициенты при одинаковых степенях n в левой и правой частях, получим
.
Здесь 22 – a1 0 поскольку 0 (иначе a2 = 0) и 2 – a1 0 (иначе было бы 1 = 2). Поэтому из этой системы последовательно и однозначно находятся все числа sm , sm–1 , … , s0 .
3. 1 = = 2 . Тогда r = 2, a1 = 2 , a2 = 2 . Исследуемое соотношение в этом случае приобретает следующий вид:
sm[2(n+2)m+2 – a1(n+1)m+2 – a2nm+2] + …
… + si[2(n+2)i+2 – a1(n+1)i+2 – a2ni+2] + …
… + s0[2(n+2)2 – a1(n+1)2 – a2n2] =
= tmnm + … + t1n + t0 t0 {бином Ньютона}
sm[2(nm+2+ +2m+2) – a1(nm+2+ +1) – a2nm+2] + …
… + si[2(ni+2+ +2i+1) – a1(ni+2+ +1) – a2ni+2] +…
… + s0[2(n2 +4n + 4) – a1(n2 + 2n + 1) – a2n2] =
= tmnm + … + t1n + t0
sm[(2 – a1 – a2)nm+2+ + (22m+2 – a1)] + …
…+si[(2 – a1– a2)ni+2+ + (22i+2 – a1)] + …
… + s0[(2 – a1 – a2)n2 + (24 – a12)n + 24 – a1] = tmnm + … + t1n + t0 .
Учитывая, что 2 – a1 – a2 = 0, a1 = 2 и приравнивая коэффициенты при одинаковых степенях n в левой и правой частях, получим
.
Здесь 222 – a1 0 поскольку 0 (иначе a2 = 0) и 22 – a1 0 поскольку a1 = 2. Поэтому из этой системы последовательно и однозначно находятся все числа sm , sm–1 , … , s0 .
Теорема доказана.