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

 

 

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

.

Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.

Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 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 следует, что - решение и система уравнений

- имеет единое решение, т.к. при условии .

Например, для чисел Фибоначчи, имеем . Характеристическое уравнение имеет вид: . Решая последнее уравнение, получим корни:

,

поэтому общее решение соотношения Фибоначчи имеет вид:

.

Для начальных условий , и , т.е. для последовательности получаем для констант и систему:

и ,

поэтому

.

Это выражение для всех натуральных принимает целые значения.

б) Рассмотрим теперь случай, когда корни характеристического уравнения совпадают, т.е. , тогда , , т.е. характеристическое уравнение имеет вид .

В этом случае и рекуррентное соотношение имеет вид:

.

Покажем, что наряду с , выражение - также является решением нашего соотношения. Действительно:

.

И общее решение в этом случае будет равно:

.

Нетрудно видеть, что и здесь можно подобрать так, что будут удовлетворены любые начальные условия.

Замечание: Линейные рекуррентные соотношения с постоянными коэффициентами порядка больше двух, решаются аналогично.

Пусть соотношение имеет вид . Составляем характеристическое уравнение: .

Если все корни характеристического уравнения различны, то общее решение имеет вид: .

Если же, например, , то этому корню соответствуют решения:

данного рекуррентного соотношения. В общем решении этому корню соответствует часть .

Например, решая рекуррентное соотношение:

,

составляем характеристическое уравнение вида: .

Его корни , . Поэтому общее решение есть:

.

 

Производящие функции.

 

 

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

Здесь необходимо знать: понятие ряда, сумма ряда, степенной ряд, сходимость степенных рядов, свойства сходящихся рядов, операции над ними. Эти понятия изложены в любом учебнике по математическому анализу, и мы их опускаем.

Определение 1: Пусть дана числовая последовательность: . Образуем степенной ряд с этими коэффициентами: . Если этот ряд сходится в некоторой области к функции , то эту функцию называют производящей для последовательности чисел .

Примеры: 1) Для степенного ряда , члены которого можно рассматривать как геометрическую прогрессию, знаменатель . Значит, степенной ряд при условии сходится к своей сумме . Таким образом, получаем:

, если .

Значит, функция является производящей для последовательности чисел (коэффициенты степенного ряда).

2) Аналогично можно получить:

.

Значит, функция является производящей для последовательности чисел .

3) Из формулы бинома Ньютона следует:

,

т.е. функция является производящей для чисел вида , где .

С помощью последней производящей функции можно доказать некоторые свойства чисел , т. е. для биномиальных коэффициентов. Например:

;

;

(здесь обе суммы конечны и обрываются, когда значения и станут больше ).

Кроме того:

,

,

.

В последнем равенстве, если , то считают, что . Поэтому меняется от до наименьшего из чисел , .

Последнее равенство можно доказать следующим образом:

,

.

Отсюда следует: .

Применяя в левой части формулу биному Ньютона и раскрывая скобки в правой части, приравниваем коэффициенты при одинаковых степенях , получаем требуемую формулу.

В частном случае, когда , получаем равенство:

, .

Проиллюстрируем на примерах применение производящих функций к решению некоторых комбинаторных задач.

1) Рассмотрим разбиение числа на слагаемые, каждое из которых равно одному из чисел . При этом слагаемые не повторяются и их порядок не играет роли.

Для решения задачи рассмотрим выражение . Раскрывая скобки, получим слагаемые вида , где – некоторые из чисел . Поэтому встретится в сумме столько раз, сколькими способами можно разбить на слагаемые требуемым образом.

Например, если надо узнать, сколькими способами можно заплатить 78 копеек, беря не более одной монеты каждого достоинства, то надо составить выражение:

,

раскрыть скобки и найти коэффициент при слагаемом .

2) Если требуется разложить число на слагаемые , каждое из которых может встречаться в разложении один или несколько раз, тогда количество слагаемых в скобках увеличивается.

Например: 1) Сколькими способами можно заплатить 29 коп., используя монеты по 2 и 5 коп?

Т.е. надо найти число способов разбить число 29 на слагаемые, равные 2 и 5, причем порядок слагаемых роли не играет, и каждое слагаемое может повторяться несколько раз. Для этого составим выражение:

.

Ясно, что при раскрытии скобок выражение войдет в разложение с коэффициентом, равным числу решений уравнения . В частности, коэффициент при дает ответ на вопрос задачи.

Вместо раскрытия скобок можно поступить иначе: составить производящую функцию. Эта функция представляет собой произведение двух дробей:

.

Разделив «уголком» числитель на знаменатель, находим коэффициент при выражении .

2) Поступающий в ВУЗ должен сдать 4 экзамена, причем для поступления достаточно набрать 17 балов. Сколькими способами абитуриент может сдать экзамены, чтобы поступить в ВУЗ?

Требуется узнать, сколькими способами можно представить число 17 в виде суммы 4-х слагаемых, принимающих значения 3, 4, 5, причем здесь порядок слагаемых имеет значение.

Для решения этой задачи можно взять производящую функцию . При раскрытии скобок каждое слагаемое встретится столько раз, сколькими способами можно разбить на сумму 4-х слагаемых, принимающих значения 3, 4 и 5. При этом встречаются члены, получаемые друг из друга перестановкой слагаемых.

В выражении можно раскрыть скобки по полиномиальной теореме, а можно следующим образом:

.

Поэтому .

.

Перемножая почленно эти выражения, найдем, что коэффициент при равен 16. Значит, разложение можно сделать 16 способами.

Между производящими функциями и рекуррентными соотношениями существует тесная связь.

Пусть - производящая функция для последовательности чисел . Это означает, что является суммой степенного ряда: .

Пусть – многочлены, причем и , значит, дробь – правильная (в противном случае можно выделить целую часть). Раскладывая дробь в ряд, получим:

.

Раскрывая скобки справа и приравнивая коэффициенты при одинаковых степенях , получаем:

При считаем, что . А дальше все соотношения имеют вид: , где , т.к. не имеет членов степени , , …

Таким образом, коэффициенты ряда , ,… удовлетворяют рассмотренному рекуррентному соотношению. Коэффициенты этого соотношения зависят только от знаменателя дроби. Числитель нужен только для нахождения первых членов рекуррентной последовательности.

Обратно, если задано рекуррентное соотношение и заданы члены , то, вычисляя значения , получим производящую функцию для последовательности чисел .

Полученную алгебраическую дробь можно разлагать на элементарные дроби и производить алгебраические преобразования.