Рекуррентные соотношения

В математике весьма часто употребляют такие термины как «рекурсивные функции», «рекуррентные последовательности», «рекуррентные соотношения», «рекурсивные алгоритмы». Все эти термины имеют один корень, происходящий от латинского слова гесиггеге — возвращаться. Общим для рекурсивных функций, рекурсивных алгоритмов и рекуррентных последовательностей является то, что для вычисления очередного значения функции, получения очередной реализации алгоритма, определения очередного члена последовательности необходимо обращаться к предшествующим их значениям, вычисленным раньше. В свою очередь, вычисление предшествующих значений требует обращения к вычисленным перед этим требуемым значениям и т.д. Таким образом, для того чтобы получить значение функции, реализацию алгоритма или значение члена ряда на п-м шаге необходимо знать их значения на (п - 1)-м шаге, а следовательно, на первом шаге. Правило, которое определяет способ вычисления очередного значения функции или очередного члена последовательности, с учетом того, что эти значения известны для первого шага, называется рекуррентным соотношением. Разработка рекуррентных соотношений — это один из методов решения различных задач. В комбинаторике этот метод применяется весьма широко.

Простейшим примером рекуррентного соотношения являются формулы для вычисления числа перестановок «-элементного множества. Эти формулы имеют вид Рх = 1, Рп = Рп_хп и могут быть получены следующим образом.

Пусть имеется п элементов /,, /2, ..., , /„, множества I. Лю

бую перестановку этих элементов можно получить так: взять некоторую перестановку элементов /,, /2, ..., и всеми возможными способами между указанными элементами, включая начало и конец, поставить элемент /и. Ясно, что таких способов будет п. Вследствие ЭТОГО ИЗ перестановки /, , /2, ..., /д_, будет получено п перестановок. Это означает, что перестановок из п элементов в п раз больше, чем перестановок из п -1 элементов множества I. Тем самым установлено рекуррентное соотношение Рп = Рп_хп. Пользуясь этим соотношением, последовательно получаем Рп -пРп_х =п(п-)Рп_2 - п{п - ){п -2)...2РХ. Но Рх - 1, поскольку из одного элемента можно сделать лишь одну перестановку. Поэтому Рп = п(п -1)(« — 2)___2-1 = п. На основании изложенного

правомерна и такая запись: Рп = (п -1)!«, 1! = 1.

Теперь приведем пример рекуррентной числовой последовательности, часто называемой числами Фибоначчи, по имени итальянского математика XIII века, установившего ее как результат решения следующей задачи. Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца). Новорожденные крольчата через два месяца после рождения тоже приносят приплод. Сколько кроликов появится через год, если в его начале была одна пара кроликов?

Из условия задачи следует, что через месяц будет две пары кроликов (приплод принесет первая пара кроликов). Через два месяца — три пары, а через три месяца — пять пар, так как даст приплод еще та пара, которая появилась после первого месяца.

Обозначим через /„ количество пар кроликов по истечении п месяцев с начала года. Тогда в начале года /0 = 1, через месяц /, = 2, через два месяца /2 = /0 + /, = 3, через три месяца /3 = = /2 + /1 =5. Поэтому в общем случае для вычисления числа кроликов в конце любого месяца получаем рекуррентное соотношение /„ = + /я_2. Это соотношение дает возможность

вычислить количество пар кроликов в конце года по выражению /12 = /п + ПРИ условии, что /0 = 1, /, = 2. Оно равно 377. Числа, которые получаются в результате применения приведенного рекуррентного соотношения, т.е. последовательность 1, 2, 3, 5, 8, 13, ... называются числами Фибоначчи. Примечательно, что при помощи рекуррентного соотношения, описывающего этой числовой ряд, решаются многие задачи комбинаторики. Вот одна из них.

Найти число последовательностей из нулей и единиц длиной п таких, в которых две единицы не стоят рядом. Убедимся в том, что эта задача решается при помощи рекуррентного соотношения

/я = /«-1 +/я- 2-

Возьмем любую последовательность из п +1 нулей и единиц такую, что в ней не идут две единицы подряд. Она может оканчиваться на нуль или единицу. Если последовательность оканчивается на нуль, его можно отбросить и получить последовательность длиной п, в которой две единицы не стоят рядом. Наоборот, если взять эту последовательность и приписать ей в конце нуль, то получим такую последовательность длиной п +1, в которой две единицы не стоят рядом.

Пусть число последовательностей длиной п +1, в которых две единицы не стоят рядом и которые оканчиваются на нуль, равно gn. Возьмем теперь последовательность ДЛИНОЙ /7 + 1, в которой две единицы не стоят рядом и которая оканчивается на единицу. Так как две единицы не стоят рядом, перед последней единицей последовательности стоит нуль, т.е. последовательность оканчивается на 01. Отбрасывая эти цифры, получим последовательность длиной п - 1, в которой две единицы не стоят подряд. Число таких последовательностей gn_^. Так как каждая последовательность длиной п + 1, в которой две единицы не стоят подряд оканчивается на единицу или нуль, для общего числа таких последовательностей по правилу суммы получаем gn+^ - gn + gn_x. При этом для последовательностей длиной п = 1 существует две последовательности: 0 и 1, в которых две единицы не стоят рядом, вследст-

вие чего gl - 2. Для последовательностей длиной п - 2 существует три последовательности, в которых две единицы не стоят рядом: 00, 01 и 10. Поэтому = 3. Таким образом, рекуррентное соотношение gn+l = gn + gn_{, g^ = 2, g2 =3 эквивалентно рекуррентному соотношению /я+1 = /„ + /, =2, /2 = 3, описывающему ряд

Фибоначчи. Следовательно, для любого /7 = 1,2, ..., используя это соотношение, можно решить сформулированную выше задачу.

Необходимо отметить, что вывод рекуррентных соотношений иногда бывает прост, а иногда требует серьезных усилий. Для одних задач рекуррентные соотношения получаются простыми, для других — сложными. Общим же неудобством рекуррентных соотношений является то, что для вычисления члена последовательности необходимо вычислить все предшествующие ее члены.

 
< Пред   СОДЕРЖАНИЕ     След >