Линейные рекуррентные соотношения с постоянными коэффициентами. Основные определения и примеры рекуррентных соотношений Часто решение одной комбинаторной задачи удается свести к решению аналогичных задач меньшей размерности с помощью некоторого соотношения называемого рекуррентным от латинского слова recurrere возвращаться. Тем самым решение сложной задачи можно получить последовательно находя решение более легких задач и далее пересчитывая по рекуррентным соотношениям находить решение трудной задачи. Рекуррентным соотношением го...
Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск
аранов Виктор Павлович. Дискретная математика. Раздел 2. Элементы комбинаторики.
Лекция 5. Метод рекуррентных соотношений
Лекции 5. МЕТОД РЕКУРРЕНТНЫХ СООТНОШЕНИЙ
План лекции:
Бине.
Часто решение одной комбинаторной задачи удается свести к решению аналогичных задач меньшей размерности с помощью некоторого соотношения, называемого реку р рентным (от латинского слова recurrere возвращаться). Тем самым решение сложной задачи можно получить, последовательно находя решение более легких задач, и далее, п е ресчитывая по рекуррентным соотношениям, находить решение трудной задачи.
Рекуррентным соотношением -го порядка между элементами последовательности чисел называется формула вида
(1)
Частным решением рекуррентного соотношения является любая последовател ь ность, обращающая соотношение (1) в тождество. Соотношение (1) им е ет бесконечно много частных решений, так как первые элементов последовательн о сти можно задать произвольно. Например, последовательность является р е шением рекуррентного соотн о шения, так как имеет место тождество.
Решение рекуррентного соотношения -го порядка называется общим , если оно з а висит от произвольных постоянных, и путем подбора этих постоянных мо ж но получить любое решение данного соотношения. Например, для соотнош е ния
(2)
общим решением будет
. (3)
Действительно, легко проверить, что последовательность (3) обращает соотношение (2) в тождество. Поэтому надо только показать, что любое решение соотношения (2) мо ж но представить в виде (3). Но любое решение этого соотношения однозначно определяе т ся значениями и. Поэтому надо доказать, что для любых чисел и найдутся т а кие значения и, что
Так как эта система имеет решение при любых значениях и, то решение (3) действительно является общим решением соотношения (2).
Пример 1 . Числа Фибоначчи. В 1202 г. знаменитым итальянским математиком Ле о нардо Пизанским, который известен больше по своему прозвищу Фибоначчи (Fib o nacci сокращенное filius Bonacci , т. е. сын Боначчи), была написана книга « Liber abacci » («Кн и га об абаке»). До нас эта книга дошла во втором своем варианте, который относится к 1228 г. Рассмотрим одну из множества приведенных в этой книге задач.
Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), пр и чем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится ч е рез год, если в начале года была одна пара кроликов?
Из условия задачи следует, что через месяц будет две пары кроликов. Через два мес я ца приплод даст только первая пара кроликов, и получится 3 пары. A еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов и т. д.
Обозначим через количество пар кроликов по истечении месяцев с начала г о да. Тогда через месяцев будут эти пар и еще столько новорожденных пар кр о ликов, сколько было в конце -го месяца, то есть еще пар. Таким образом, имеет место р е куррентное соотношение
. (4)
Так как, то последовательно находим: и т. д. Эти числа составляют последовательность
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,
которую называют рядом Фибоначчи , а его члены числами Фибоначчи . Они обладают целым рядом замечательных свойств. Числа Фибоначчи связаны со следующей комбин а торной задачей.
Найти число двоичных слов длины, в которых никакие две единицы не идут по д ряд.
Будем называть такие слова правильными и обозначим их число через. Разобьем множество этих правильных слов на два класса: слова, оканчивающиеся на ноль, и слова, оканчивающиеся на единицу. Обозначим количество слов в этих классах и соо т ветственно. По правилу сложения
(5)
Очевидно, что у слова, оканчивающегося на ноль, первые символов образуют правильное слово длины, или другими словами, имеется биекция между множеством правильных слов длины, оканчивающихся на ноль, и множеством правильных слов длины, то есть.
Если правильное слово длины оканчивается на единицу, то предыдущий символ этого слова должен быть нулем, а первые символа должны образовывать правильное слово длины. Как и в предыдущем случае, снова имеем биекцию между множеством правильных слов длины, оканчивающихся на единицу, и множеством правильных слов длины. Следовательно. . Из формулы (5) получаем рекуррентное соотн о шение
. (6)
Для использования рекуррентного соотношения необходимы для данного вычи с ления всех предыдущих значений. Например, если нам нужно знать количество правил ь ных слов из 10 символов, то его можно найти, последовательно заполняя следующую та б лицу:
Таблица 1
Первые два значения находятся непосредственно ( слова 0 и 1; слова 000, 010, 101), а остальные по формуле (6).
Пример 2. Задача о расстановке скобок в выражении с неассоциативной бина р ной операцией. Пусть “” обозначает некоторую бинарную операцию. Рассмотрим в ы ражение, в котором символ обозначает некоторую бинарную неассоци а тивную операцию. Сколько имеется различных способов расстановки скобок в этом в ы раж е нии?
Как пример неассоциативной операции можно привести векторное произведение. Другой пример обычное сложение и умножение, выполняемое на компьютере. В с и лу того, что представление каждого числа в памяти компьютера ограничено определе н ным количеством разрядов, при выполнении каждой операции возникает погрешность и су м марный результат этих погрешностей зависит от расстановки скобок. Пусть маши н ный ноль . Это означает, что. Тогда, в то время как.
Обозначим число всевозможных способов расстановки скобок через. Тогда
Назовем операцию условно произведением. Для произвольного разобьем все способы расстановки скобок на классы, включив в -ый класс способы, при которых сн а чала вычисляется произведение первых и последних операндов с какой-то расст а новок скобок, а потом вычисляется их произведение:
(7)
где.
По определению количество способов расстановки скобок для вычисления первых операндов равно, последних . По правилу произведения число расстановок ск о бок для выражения (4) равно. По правилу сложения
, (8)
Например, .
Пусть функция в соотношении (1) является лине й ной
, (9)
где некоторые числа. Такие соотношения называют линейными соотн о шениями -го порядка с постоянными коэффициентами.
Сначала исследуем подробно соотношения второго порядка, а затем перейдем к о б щему случаю. При из формулы (9) получим
, . (10)
Решение этих соотношений основано на следующих легко доказываемых утвержд е ниях.
Лемма 1. Пусть решение соотношения (10), а любое число. Тогда последовательность также является решен и ем этого соотношения.
Лемма 2. Пусть и решения соотн о шения (10). Тогда последовательность также явл я ется решением этого соотношения.
Из этих двух простых лемм можно сделать следующий важный вывод. Совоку п ность всевозможных последовательностей с операциями покоо р динатного сложения и умножения на скаляр образует векторное пространство. Совоку п ность последовательностей, являющихся решениями соотношения (10), представляет с о бой подпространство этого пространства. Объемлющее пространство всевозможных п о следовательностей бесконечномерно, но подпространство решений линейного рекуррен т ного соотношения имеет конечную размерность, равную порядку уравн е ния.
Лемма 3. Размерность пространства решений рекуррентного соотношения (10) равна двум.
Из леммы 3 следует, что для определения всех решений уравнения (12) необходимо отыскать два линейно независимых решения. Любое другое решение будет представлят ь ся линейной комбинацией этих базисных решений.
Рассмотрим рекуррентное соотношение первого порядка
, (11)
где константа.
Если, то из (11) имеем
, (12)
то есть решением рекуррентного уравнения первого порядка является геометрическая прогрессия.
Будем искать решение рекуррентного соотношения второго порядка также в виде (12). Тогда, подставляя (12) в (9), получим
. (13)
При =0 имеем нулевое решение, которое не представляет интереса. Считая, поделим последнее соотношение на:
(14)
Таким образом, геометрическая прогрессия (12) является решением рекуррентного соотношения (10), если знаменатель прогрессии является корнем квадратного уравн е ния (14). Это уравнение называется характеристическим уравнением для рекуррентного соо т ношения (9).
Построение базисных решений зависит от корней и характеристического уравнения (14).
(15)
путем соответствующего выбора констант можно получить любое решение соотношения (10). Рассмотрим произвольное решение. Выберем константы и так, чтобы при и:
(16)
Определитель линейной системы (16)
следовательно, система имеет единственное решение, а значит формула (15) общее р е шения соотношения (10).
. (17)
В случае соотношения -го порядка (9) имеют место утверждения, аналогичные тем, которые были рассмотрены для уравнений 2-го порядка.
. (18)
Многочлен
(19)
называется характеристическим многочленом рекуррентного соотношения (9).
. (20)
При заданных начальных значениях решения, константы н а ходятся из системы
Пусть характеристическое уравнение (18) имеет корни: ,…, кратности с о ответственно,…, причем. Тогда характеристический мног о член и общее решение соотношения (9) представятся в виде
Пример 3 . Формула Бине . Поставим задачу получить формулу в явном виде для ч и сел Фибоначчи. Для этого найдем решение рекуррентного соотношения (4) при условии, что. Составим характеристическое уравнение, найдем его корни и получим общее решение. Константы и опред е лим из начальных условий: . Тогда или
, (21)
где золотое сечение. Формула (21) называется формулой Бине . При этом. Из формулы Бине следует, что.
Другие похожие работы, которые могут вас заинтересовать.вшм> |
|||
| 3792. | Рациональность соотношений в активе предприятия | 113.83 KB | |
| Бухгалтерский баланс - основная форма бухгалтерской отчетности. Он характеризует имущественное и финансовое состояние организации на отчетную дату. В балансе отражаются остатки по всем счетам бухгалтерского учета на отчетную дату. Эти показатели приводятся в бухгалтерском балансе в определенной группировке. | |||
| 8407. | Константный метод | 17.82 KB | |
| Говорят, что метод объекта обладает свойством неизменности (константности), если после его выполнения состояние объекта не изменяется.Если не контролировать свойство неизменности, то его обеспечение будет целиком зависеть от квалификации программиста. Если же неизменный метод в процессе выполнения будет производить посторонние эффекты, то результат может быть самым неожиданным,отлаживать и поддерживать такой код очень тяжело. | |||
| 13457. | Метод фазовой плоскости | 892.42 KB | |
| Метод фазовой плоскости впервые был применен для исследования нелинейных систем французским ученым Анри Пуанкаре. Основное преимущество этого метода – точность и наглядность анализа движений нелинейной системы. Метод является качественным | |||
| 2243. | МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ | 113.98 KB | |
| Идея метода возможных направлений МВН заключается в том что в каждой очередной точке находится направление спуска такое что перемещение точки по этому направлению на некоторое расстояние не приводит к нарушению ограничений задачи. Направление определяемое вектором называется возможным направлением в точке если достаточно малое перемещение из в направлении не выводит точку за пределы допустимой области т. Очевидно если является внутренней точкой множества то любое направление в этой точке является возможным. Возможное... | |||
| 12947. | МЕТОД ГАРМОНИЧЕСКОЙ ЛИНЕАРИЗАЦИИ | 338.05 KB | |
| Переходя непосредственно к рассмотрению метода гармонической линеаризации будем считать что исследуемая нелинейная система приведена к виду показанному на. Нелинейный элемент может иметь любую характеристику лишь бы она была интегрируемой без разрывов второго рода. Преобразование данной переменной для примера нелинейным элементом с зоной нечувствительности показано на рис. | |||
| 2248. | Графический метод решения ЗЛП | 219.13 KB | |
| Точки лежащие внутри и на границе этой области являются допустимыми планами. А именно все точки отрезка АВ являются оптимальными планами задачи на которых достигается максимальное значение линейной формы. Метод последовательного улучшения плана Метод основан на упорядоченном переборе угловых точек множества планов задачи в сторону увеличения или уменьшения линейной формы и содержит три существенных момента. Вопервых указывается способ вычисления опорного плана. | |||
| 7113. | Метод гармонической линеаризации | 536.48 KB | |
| Метод гармонической линеаризации Поскольку этот метод является приближённым то полученные результаты будут близки к истине только при выполнении определённых допущений: Нелинейная система должна содержать только одну нелинейность; Линейная часть системы должна представлять собой фильтр низких частот ослабляющий высшие гармоники возникающие в предельном цикле; Метод применим только к автономным системам. Изучается свободное движение системы то есть движение при ненулевых начальных условиях в отсутствие внешних воздействий.... | |||
| 10649. | Индексный метод анализа | 121.13 KB | |
| Индивидуальные индексы. Общие агрегатные индексы. Средние преобразованные индексы. Индексы переменного и постоянного состава индексы структурных сдвигов. | |||
| 12914. | Метод наименьших квадратов | 308.27 KB | |
| Пусть из теоретических соображений мы знаем что. Поэтому можно сказать что наша задача состоит и в том чтобы провести прямую наилучшим образом. Будем считать что вся ошибка заключена в. Будем подбирать искомые коэффициенты из соображений чтобы случайная добавка была наименьшей. | |||
| 9514. | Метод бухгалтерського обліку | 1002.23 KB | |
| Бухгалтерські рахунки та їх побудова. Він складається з ряду елементів головні з яких: документація; інвентаризація; рахунки; подвійний запис; оцінка; калькуляція; баланс; звітність. Рахунки бухгалтерські призначені для обліку наявності активів і пасивів. Бухгалтерські рахунки та їх побудова. | |||
Аннотация: Размещения без повторений. Перестановки. Сочетания. Рекуррентные соотношения. Другой метод доказательства. Процесс последовательных разбиений. Задача: "Затруднение мажордома".
Имеется различных предметов. Сколько из них можно составить -расстановок? При этом две расстановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Такие расстановки называют размещениями без повторений , а их число обозначают . При составлении -размещений без повторений из предметов нам надо сделать выборов. На первом шагу можно выбрать любой из имеющихся предметов. Если этот выбор уже сделан, то на втором шагу приходится выбирать из оставшихся предметов. На - м шагу предметов. Поэтому по правилу произведения получаем, что число -размещений без повторения из предметов выражается следующим образом:
При составлении размещений без повторений из элементов по мы получили расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называют перестановками из n элементов , или, короче, - перестановками .
В тех случаях, когда нас не интересует порядок элементов в комбинации, а интересует лишь ее состав, говорят о сочетаниях. Итак, - сочетаниями из элементов называют всевозможные - расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов. Число -сочетаний, которое можно составить из элементов, обозначают через .
Формула для числа сочетаний получается из формулы для числа размещений. В самом деле, составим сначала все - сочетания из элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получается, что все -размещения из элементов, причем каждое только по одному разу. Но из каждого - сочетания можно сделать ! перестановок, а число этих сочетаний равно . Значит справедлива формула
Из этой формулы находим, что
При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского "recurrere" - "возвращаться").
Понятие рекуррентных соотношений проиллюстрируем классической проблемой, которая была поставлена около 1202 года Леонардо из Пизы, известным как Фибоначчи. Важность чисел Фибоначчи для анализа комбинаторных алгоритмов делает этот пример весьма подходящим.
Фибоначчи поставил задачу в форме рассказа о скорости роста популяции кроликов при следующих предположениях. Все начинается с одной пары кроликов. Каждая пара становится фертильной через месяц, после чего каждая пара рождает новую пару кроликов каждый месяц. Кролики никогда не умирают, и их воспроизводство никогда не прекращается.
Пусть - число пар кроликов в популяции по
прошествии месяцев, и пусть эта популяция состоит из пар
приплода и "старых" пар, то есть . Таким образом, в очередном месяце произойдут следующие события: . Старая популяция в -й момент увеличится на число родившихся в момент времени . 
. Каждая старая пара в момент времени производит пару приплода в момент времени .
В последующий месяц эта картина повторяется:
Объединяя эти равенства, получим следующее рекуррентное соотношение:
| (7.1) |
Выбор начальных условий для последовательности чисел Фибоначчи не важен;
существенное свойство этой последовательности определяется рекуррентным
соотношением. Будем предполагать (иногда 
).
Рассмотрим эту задачу немного иначе .
Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов ?
Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через количество пар кроликов по истечении месяцев с начала года. Ясно, что через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца , то есть еще пар кроликов. Иными словами, имеет место рекуррентное соотношение
| (7.2) |
Так как, по условию, и , то последовательно находим
В частности, 
.
Числа называются числами Фибоначчи . Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через . Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.
Найти число последовательностей,состоящих из нулей и единиц, в которых никакие две единицы не идут подряд .
Чтобы установить эту связь , возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями - все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию": сама пара появилась в конце 11-го месяца, ее родители - в конце 7-го месяца, "дед" - в конце 5-го месяца и "прадед" - в конце второго месяца. Исходная пара кроликов тогда зашифровывается последовательностью 000000000000.
Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд - только что появившаяся пара не может, по условию, принести приплод через месяц. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов всегда имеют разную "генеалогию", так как, по условию, крольчиха дает приплод, состоящий только из одной пары кроликов.
Установленная связь показывает, что число -последовательностей, обладающих указанным свойством, равно .
Докажем теперь, что
| (7.3) |
Где , если нечетно, и , если четно. Иными словами, - целая часть числа (в
дальнейшем будем обозначать целую часть числа через ; таким образом, 
).
В самом деле, - это число всех - последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно единиц и нулей, равно . Так как при этом должно выполняться
Числа Фибоначчи.
При решении многих комбинаторных задач применяют метод сведения данной задачи к задаче касающегося меньшего числа элементов. Например, можно вывести формулу для числа перестановок:
Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.
Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 1202 г. итальянский математик Фибоначчи привел следующую задачу. Пара кроликов приносит приплод раз в месяц двух крольчат (самку и самца), причём новорождённые крольчата через два месяца после рождения сами приносят приплод. Сколько кроликов появится через год, если в начале была одна пара кроликов.
Из условия задачи следует, что через месяц будет две пары кроликов, через два месяца приплод даст только первая пара кроликов, появившихся два месяца назад, поэтому всего будет 3 пары кроликов. Ещё через месяц будет уже 5 пар. И так далее.
Обозначим через количество пар кроликов по истечении месяцев с начала года. Тогда через месяц количество пар кроликов можно найти по формуле:
Эта зависимость называется рекуррентным соотношением . Слово «рекурсия» означает возврат назад (в нашем случае – возврат к предыдущим результатам).
По условию, и , тогда по соотношению имеем: , , и т.д., .
Определение 1: Числа называются числами Фибоначчи . Это – известная в математике последовательность чисел:
1, 1, 2, 3, 5, 8, 13, 21, ...
В этой последовательности каждое последующее число является суммой двух предыдущих чисел. И в рекуррентном соотношении также последующий член находится как сумма двух предыдущих членов.
Установим связь между числами Фибоначчи и комбинаторной задачей. Пусть требуется найти число - последовательностей, состоящих из нулей и единиц, в которых никакие две единицы не стоят подряд.
Возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители в конце 7-го месяца, «дед» – в конце 5-го месяца, и «прадед» в конце 2-го месяца. Первоначальная пара шифруется последовательностью . Ни в одной последовательности две единицы не могут стоять подряд – только что появившаяся пара не может принести приплод через месяц. Очевидно, различным последовательностям отвечают различные пары и обратно.
Таким образом, число последовательностей с указанными свойствами, равно .
Теорема 1: Число находится как сумма биномиальных коэффициентов:. Если – нечетно, то . Если – четно, то . Иначе: – целая часть числа .
Доказательство: В самом деле, - число всех последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число таких последовательностей, содержащих ровно единиц и нулей, равно , при этом , тогда изменяется от 0 до . Применяя правило суммы, получаем данную сумму.
Это равенство можно доказать иначе. Обозначим:
Из равенства , следует, что . Кроме этого, ясно, что и . Так как обе последовательности и удовлетворяют рекуррентному соотношению , то , и .
Определение 2: Рекуррентное соотношение имеет порядок , если оно позволяет вычислять через предыдущих членов последовательности: .
Например, – рекуррентное соотношение второго порядка, а рекуррентное соотношение 3-го порядка. Соотношение Фибоначчи является соотношением второго порядка.
Определение 3:Решением рекуррентного соотношения является последовательность, удовлетворяющая этому соотношению.
Если задано рекуррентное соотношение ‑ го порядка, то ему удовлетворяют бесконечно много последовательностей, т.к. первые элементов можно задать произвольно. Но если первые элементов заданы, то остальные члены определяются однозначно.
Например, соотношению Фибоначчи кроме рассмотренной выше последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., могут удовлетворять также и другие последовательности. К примеру, последовательность 2, 2, 4, 8, 12,... строится по тому же принципу. Но если задать начальные члены (их в последовательности Фибоначчи - 2), то решение определяется однозначно. Начальных членов берут столько, каков порядок соотношения.
По известным рекуррентным соотношениям и начальным членам можно выписывать члены последовательности один за другим и таким путем мы можем получить любой её член. Но во многих случаях, нам не нужны все предыдущие члены, а необходим один определенный член. В этом случае удобнее иметь формулу ‑ го члена последовательности.
Мы будем говорить, что некоторая последовательность является решением данного рекуррентного соотношения, если при подстановке этой последовательности соотношение тождественно выполняется.
Например, последовательность является одним из решений соотношения: . Это легко проверить обычной подстановкой.
Определение 4: Решение рекуррентного соотношения ‑ го порядка называется общим , если оно зависит от произвольных постоянных , меняя которые, можно получить любое решение данного соотношения.
Например, для соотношения общим решение будет .
В самом деле, легко проверяется, что оно будет решением нашего соотношения. Покажем, что любое решение можно получить в таком виде. Пусть и – произвольны.
Тогда найдутся такие и , что
Очевидно, для любых , система уравнений имеет единственное решение.
Определение 5: Рекуррентное соотношение называется линейным , если оно записывается в виде:
где - числовые коэффициенты.
Для решения произвольных рекуррентных соотношений общих правил, вообще говоря, нет. Однако для решения линейных рекуррентных соотношений есть общие правила решения.
Рассмотрим сначала соотношение 2-го порядка .
Решение этого соотношения основано на следующих утверждениях.
Теорема 2: Если и - являются решением данного рекуррентного соотношения 2-го порядка, то для любых чисел и последовательность также является решением этого соотношения.
Теорема 3: Если число является корнем квадратного уравнения , то последовательность является решением рекуррентного соотношения .
Из теорем 2, 3 вытекает следующее правило решения линейных рекуррентных соотношений 2-го порядка.
Пусть дано рекуррентное соотношение .
1) Составим квадратное уравнение , которое называется характеристическим для данного соотношения. Найдём все корни этого уравнения (даже кратные и комплексные).
2) Составим общее решение рекуррентного соотношения. Его структура зависит от вида корней (одинаковые они или различные).
а) Если это соотношение имеет два различных корня и , то общее решение соотношения имеет вид .
Действительно, из теорем 2, 3 следует, что - решение и система уравнений
Имеет единое решение, т.к. при условии .
Например, для чисел Фибоначчи, имеем . Характеристическое уравнение имеет вид: . Решая последнее уравнение, получим корни:, .
Если все корни характеристического уравнения различны, то общее решение имеет вид: .
Если же, например, , то этому корню соответствуют решения:
данного рекуррентного соотношения. В общем решении этому корню соответствует часть .
Например , решая рекуррентное соотношение:
составляем характеристическое уравнение вида: .
Его корни , . Поэтому общее решение есть.
Данный метод состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, называемого рекуррентным. Говорят, что последовательность элементов u0 , u1 , … un , … над полем комплексных чисел C удовлетворяет рекуррентному соотношению порядка k, если
где a1 , … , ak - коэффициенты из C. Соотношения такого типа естественным образом возникают при решении комбинаторных задач.
Пример. Пусть имеется последовательность позиций, занумерованных числами 1, 2, … , n, … и в начальный момент предмет находится в 1-ой позиции. За один ход предмет продвигается вперед на 1 и 2 позиции. Найти число способов попадания в n-ю позицию.
♦ Пусть un - интересующее нас число. Ясно, что u2 = 1, u3 = 2 . Далее, разобьем все способы попадания в позицию с номером n на два класса: те, при которых на последнем шаге предмет передвигается на 1 шаг и те, при которых он передвигается на 2 шага. Ясно, что в первом случае имеем un-1 вариантов, во втором un-2 вариантов. Следовательно, имеем
Многочлен P(x) называется характеристическим для линейного рекуррентного соотношения (2). Заметим, что всякая рекуррентная последовательность k-го порядка однозначно определяется заданием k ее первых членов.
Пусть λ - корень характеристического многочлена P(x).
Теорема 1. Последовательность u0 , u1 , … un , … , где un = cλ n , c - произвольная константа из C, удовлетворяет линейному рекуррентному соотношению (2).
♦ Подставляя данные значения un , n = 0, 1, … в (2), имеем
cλ n - a1 cλ n-1 - a2 cλ n-2 - … - ak cλ n-k = cλ n-k (λ k - a1 λ k-1 - … - ak ) ≡ 0. ♦
Теорема 2. Пусть последовательности un , vn , n = 0, 1, … удовлетворяют линейному рекуррентному соотношению (2). Тогда этим свойством обладает последователь-
ность rn , n = 0, 1, … , где rn = α un + β vn , n , α, β - произвольные константы из C.
♦ Доказательство очевидно. ♦
Теорема 3. Пусть λ 1 , … , λ k - простые (т.е. не являющиеся кратными) корни характеристического многочлена P(x) для последовательности (2).
Тогда общее решение данного рекуррентного соотношения имеет вид
где c1 , … , ck - подходящие константы из C.
♦ Согласно предыдущему замечаем, что последовательностьun , n = 0, 1, … есть решение соотношения (2). Чтобы доказать, что любое решение имеет вид (5) достаточно показать, что для произвольной последовательности vn , n = 0, 1, … , удовлетворяющей
(2), существуют константы c1 , … , ck , такие, что un = vn , n . Для этого достаточно, чтобы выполнялось v0 = u0 , v1 = u1 , … , vk-1 = uk-1 . Рассмотрим данные условия
относительно c1 , c2 , … , ck . Определитель этой системы есть определитель Вандермонда и согласно (7, стр. 118).
= ∏ (λi − λj ) ≠ 0 |
||||||
λ k− 1 |
λ k− 1 |
L λ k − 1 |
||||
согласно предположению о корнях λ 1 , … , λ k . Отсюда и следует утверждение. ♦ В качестве примера рассмотрим рекуррентное соотношение (3). Имеем характеристический многочлен
P(x) = x2 - x -1
Его корни равны λ 1 = 1 + 2 5 , λ 2 = 1 − 2 5 , Общее решение имеет вид
u n = c 1 1+ 2 5 n + c 2 1− 2 5 n
Система уравнений для констант c1 , c2 : c1 1 + 2 5 + c2 1 − 2 5 = 1
1− 5 |
||||||||||
Откуда получаем c1 |
C2 = - |
|||||||||
Пусть теперь λ - корень кратности r характеристического многочлена P(x). Аналогично предыдущему доказывается
Теорема 4. Последовательности c1 λ n , c2 nλ n ,K , cr n r − 1 λ n , n = 0, 1, … для про-
извольных констант c1 , … , cr из C удовлетворяют соотношению (2).
Теорема 5. Пусть характеристический многочлен P(x) имеет корни λ 1 , … , λ s кратностей r1 , … , rs (r1 + … + rs = k) . Тогда общее решение рекуррентного соотношения
Укажем еще одно полезное свойство линейных рекуррентных соотношений. Теорема 6. Пусть имеем соотношение
un = a1 un-1 + … + ak un-k
с начальными условиями u1 , … , uk . Тогда справедливо соотношение при всех n ≥ k
a 1 a 2 |
A k n − k uk |
||||||||||
u k− 1 |
u n− 1 |
||||||||||
u n− k+ 1 |
|||||||||||
♦ Доказательство индукцией по n. При n = k равенство (8) справедливо. Пусть оно верно при n. При n + 1 имеем
a 1 a 2 |
A k n + 1 − k uk |
|||||||||||||||||||
u k− 1 |
||||||||||||||||||||
0 . . 1 0 |
||||||||||||||||||||
a 1 a 2 |
a k a 1 a 2 |
a k n − k uk |
||||||||||||||||||
u k− 1 |
||||||||||||||||||||
a 1 a 2 |
u n+ 1 |
|||||||||||||||||||
u n− 1 |
||||||||||||||||||||
1 0 un − k + 1 |
u n− k+ 2 |
|||||||||||||||||||
В большинстве случаев, однако, при изучении перечислительных задач возникают нелинейные рекуррентные соотношения, для разрешения которых используются специфические приемы. Некоторые из них будут рассмотрены в дальнейшем. Приведем важный пример нелинейного рекуррентного соотношения.
Теорема 7. Пусть C(n, k) - число подстановок n-элементного множества, имеющих точно k циклов. Тогда справедливо
C(n - 1, k - 1) + (n - 1)C(n - 1, k) |
||
1, C(0, 1) = 0 |
♦ Разобьем множество подстановок множества X = {1, 2, … n,} имеющих точно k циклов, на два класса - подстановки, в которых элемент n содержится в единичном цикле, и подстановки, в которых элемент n находится в цикле длины l, l > 1. В первом случае число подстановок совпадает с числом подстановок множества X′ = {1, 2, …, n - 1}, имеющих k - 1 циклов, т.е. C(n - 1, k - 1). Во втором случае, удаляя элемент n, полу-
чаем подстановку множества X′ = {1, 2, …, n - 1} с k циклами, число которых равно C(n - 1, k). Выясним теперь, каким числом способов в подстановку степени n - 1 с k циклами можно добавить элемент n. Если имеется цикл длины i, то это можно сделать i способами. Общее число способов равно i1 + … + ik , где i1 , … , ik - длины циклов подстановки. Однако i1 + … + ik = n - 1. Значит число подстановок второго класса равно
(n - 1)C(n - 1, k). Отсюда и получаем (9). ♦
Полученные числа C(n, k) связаны с известными числами Стирлинга первого рода sn,k , которые определяются так:
sn,k = (- 1)n+k C(n, k)
Приведем таблицу нескольких первых значений чисел sn,k .
s n,1 |
s n,2 |
s n,3 |
s n,4 |
s n,5 |
||
Табл. Числа Стирлинга первого рода
