ЛЕКЦИЯ № 11
В комбинаторных задачах искомым решением часто является числовая последовательность u1, u2, …, un, … Например, если мы ищем число подмножеств m-элементного множества, то . В данном разделе рассмотрим ситуацию, при которой свойства членов искомой последовательности определяются некоторым рекуррентным соотношением, которому удовлетворяют числа un:
un + k + b1 un + k – 1 + b2 un + k – 2 +…+ bk un = 0, (3.6)
где b1, b2, …, bk – некоторые коэффициенты. Выражение (3.6) называется еще разностным линейным уравнением k-го порядка с постоянными коэффициентами.
Одной из наиболее известных последовательностей, задаваемых линейным рекуррентным соотношением, является последовательность Фибоначчи {Fn}, определяемая следующими условиями: F0 = 0; F1 = 1; Fn+2 = Fn+1 + Fn. Отсюда получаем F2 = 1; F3 = 2; F4 = 3; F5 = 5; F6 = 8 и т.д.
Воспользовавшись уравнением (2.8) всегда можно вычислить значения un для любых n, если знать первые k членов последовательности. Однако, часто необходимо знать явную формулу для вычисления un.
Теорема 3.4. Пусть l1, l2,…, ls – корни соответствующих кратностей m1, m2,…, ms характеристического уравнения для выражения (3.6):
|
|
lk + b1 lk–1 + b2 lk–2 +…+ bk = 0 (3.7)
Тогда общее решение уравнения (3.6) определяется по формуле:
un = (C11 + C12 ×n + C13×n2 + … + )+
(C21 + C22 ×n + C23×n2 + … + )+ … (3.8)
(Cs,1 + Cs,2 ×n + Cs,3×n2 + … + ),
где C11,…, – константы (их число равно k), определяемые начальными условиями.
Пример 3.3. Решим уравнение Фибоначчи Fn+2 – Fn+1 – Fn = 0. Его характеристическое уравнение имеет вид: l2 – l – 1 = 0. Корни равны – некратные. Обозначим Ф1 = l1 » 1.618; Ф2 = l2 » – 0.618. Общее решение равно:
.
Из начальных условий F0 = 0; F1 = 1 получаем систему уравнений для вычисления С1 и С2 = 1:
.
Отсюда С1 = – С2 = .
Использование рекуррентных соотношений дает эффективный метод решения многих комбинаторных задач.
Пример 3.4. Найти число бинарных n-последовательностей, в которых никакие две единицы не стоят рядом.
Решение. Обозначим:
zn – число искомых последовательностей;
хn – число последовательностей, заканчивающихся 0;
уn – число последовательностей, заканчивающихся 1.
Назовем для краткости последовательность, заканчивающуюся 0 – х-последовательностью, а заканчивающихся 1 – у-последовательностью.
Очевидны следующие их свойства.
1) х-последовательность длиной n можно получить, приписав 0 в конец либо у-последовательности либо х-последовательности длиной n – 1.
2) у-последовательность длиной n можно получить, приписав 1 только в конец х-последовательности длиной n – 1.
Отсюда имеем следующую систему уравнений:
.
Уравнение (a) отражает свойство 1), уравнение (b) – свойство 2), а уравнение (а) соответствует очевидному равенству.
|
|
Из уравнения (b) при замене n на n – 1 имеем: уn–1 = хn–2.
Подставим это равенство в (a), получим: хn = хn–1 + хn–2, т.е. числа хn образуют последовательность Фибоначчи. Вычтем (b) из (a), получим:
хn – уn = уn–1 Þ хn = уn + уn–1 Þ уn+1 = уn + уn–1
– тоже последовательность Фибоначчи. В соответствие с формулой общего решения и уравнением (c) получим:
.
Для нахождения констант запишем начальные условия. z1 = 2, т.к. существует 2 последовательности длиной 1: 0 и 1. z2 = 3, т.к. существует 3 последовательности длиной 2: (0 0), (0 1), (1 0). Отсюда ; . Следовательно
.
Например, z9 = 89, z19 = 10946.