Числа Фибоначчи.
При решении многих комбинаторных задач применяют метод сведения данной задачи к задаче касающегося меньшего числа элементов. Например, можно вывести формулу для числа перестановок:
Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.
Хорошей иллюстрацией к построению рекуррентных соотношений является задача Фибоначчи. В своей книге в 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 элементов , или, короче, - перестановками .
Сочетания
В тех случаях, когда нас не интересует порядок элементов в комбинации, а интересует лишь ее состав, говорят о сочетаниях. Итак, - сочетаниями из элементов называют всевозможные - расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов. Число -сочетаний, которое можно составить из элементов, обозначают через .
Формула для числа сочетаний получается из формулы для числа размещений. В самом деле, составим сначала все - сочетания из элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получается, что все -размещения из элементов, причем каждое только по одному разу. Но из каждого - сочетания можно сделать ! перестановок, а число этих сочетаний равно . Значит справедлива формула
Из этой формулы находим, что
Рекуррентные соотношения
При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского "recurrere" - "возвращаться").
Понятие рекуррентных соотношений проиллюстрируем классической проблемой, которая была поставлена около 1202 года Леонардо из Пизы, известным как Фибоначчи. Важность чисел Фибоначчи для анализа комбинаторных алгоритмов делает этот пример весьма подходящим.
Фибоначчи поставил задачу в форме рассказа о скорости роста популяции кроликов при следующих предположениях. Все начинается с одной пары кроликов. Каждая пара становится фертильной через месяц, после чего каждая пара рождает новую пару кроликов каждый месяц. Кролики никогда не умирают, и их воспроизводство никогда не прекращается.
Пусть - число пар кроликов в популяции по
прошествии месяцев, и пусть эта популяция состоит из пар
приплода и "старых" пар, то есть . Таким образом, в очередном месяце произойдут следующие события: . Старая популяция в -й момент увеличится на число родившихся в момент времени . 
. Каждая старая пара в момент времени производит пару приплода в момент времени .
В последующий месяц эта картина повторяется:
Объединяя эти равенства, получим следующее рекуррентное соотношение:
| (7.1) |
Выбор начальных условий для последовательности чисел Фибоначчи не важен;
существенное свойство этой последовательности определяется рекуррентным
соотношением. Будем предполагать (иногда 
).
Рассмотрим эту задачу немного иначе .
Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов ?
Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через количество пар кроликов по истечении месяцев с начала года. Ясно, что через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца , то есть еще пар кроликов. Иными словами, имеет место рекуррентное соотношение
| (7.2) |
Так как, по условию, и , то последовательно находим
В частности, 
.
Числа называются числами Фибоначчи . Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через . Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.
Найти число последовательностей,состоящих из нулей и единиц, в которых никакие две единицы не идут подряд .
Чтобы установить эту связь , возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями - все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию": сама пара появилась в конце 11-го месяца, ее родители - в конце 7-го месяца, "дед" - в конце 5-го месяца и "прадед" - в конце второго месяца. Исходная пара кроликов тогда зашифровывается последовательностью 000000000000.
Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд - только что появившаяся пара не может, по условию, принести приплод через месяц. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов всегда имеют разную "генеалогию", так как, по условию, крольчиха дает приплод, состоящий только из одной пары кроликов.
Установленная связь показывает, что число -последовательностей, обладающих указанным свойством, равно .
Докажем теперь, что
| (7.3) |
Где , если нечетно, и , если четно. Иными словами, - целая часть числа (в
дальнейшем будем обозначать целую часть числа через ; таким образом, 
).
В самом деле, - это число всех - последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно единиц и нулей, равно . Так как при этом должно выполняться
В математике весьма часто употребляют такие термины как «рекурсивные функции», «рекуррентные последовательности», «рекуррентные соотношения», «рекурсивные алгоритмы». Все эти термины имеют один корень, происходящий от латинского слова гесиггеге - возвращаться. Общим для рекурсивных функций, рекурсивных алгоритмов и рекуррентных последовательностей является то, что для вычисления очередного значения функции, получения очередной реализации алгоритма, определения очередного члена последовательности необходимо обращаться к предшествующим их значениям, вычисленным раньше. В свою очередь, вычисление предшествующих значений требует обращения к вычисленным перед этим требуемым значениям и т.д. Таким образом, для того чтобы получить значение функции, реализацию алгоритма или значение члена ряда на п-м шаге необходимо знать их значения на (п - 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, в которых две единицы не стоят рядом и которые оканчиваются на нуль, равно g n . Возьмем теперь последовательность ДЛИНОЙ /7 + 1, в которой две единицы не стоят рядом и которая оканчивается на единицу. Так как две единицы не стоят рядом, перед последней единицей последовательности стоит нуль, т.е. последовательность оканчивается на 01. Отбрасывая эти цифры, получим последовательность длиной п - 1, в которой две единицы не стоят подряд. Число таких последовательностей g n _^. Так как каждая последовательность длиной п + 1, в которой две единицы не стоят подряд оканчивается на единицу или нуль, для общего числа таких последовательностей по правилу суммы получаем g n+ ^ - g n + g n _ x . При этом для последовательностей длиной п = 1 существует две последовательности: 0 и 1, в которых две единицы не стоят рядом, вследст-
вие чего g l - 2. Для последовательностей длиной п - 2 существует три последовательности, в которых две единицы не стоят рядом: 00, 01 и 10. Поэтому = 3. Таким образом, рекуррентное соотношение g n+l = g n + g n _ { , g^ = 2, g 2 =3 эквивалентно рекуррентному соотношению / я+1 = /„ + /, =2, / 2 = 3, описывающему ряд
Фибоначчи. Следовательно, для любого /7 = 1,2, ..., используя это соотношение, можно решить сформулированную выше задачу.
Необходимо отметить, что вывод рекуррентных соотношений иногда бывает прост, а иногда требует серьезных усилий. Для одних задач рекуррентные соотношения получаются простыми, для других - сложными. Общим же неудобством рекуррентных соотношений является то, что для вычисления члена последовательности необходимо вычислить все предшествующие ее члены.