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

Размещения без повторений

Имеется $$n$$ различных предметов. Сколько из них можно составить $$k$$ -расстановок? При этом две расстановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Такие расстановки называют размещениями без повторений, а их число обозначают $$A_n^k$$. При составлении $$k$$ -размещений без повторений из $$n$$ предметов нам надо сделать $$k$$ выборов. На первом шагу можно выбрать любой из имеющихся $$n$$ предметов. Если этот выбор уже сделан, то на втором шагу приходится выбирать из оставшихся $$n - 1$$ предметов. На $$k$$ - м шагу $$n-k+1$$ предметов. Поэтому по правилу произведения получаем, что число $$k$$ -размещений без повторения из $$n$$ предметов выражается следующим образом:$$A_n^k = n(n - 1)\ldots (n - k + 1).$$

Перестановки

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

Сочетания

В тех случаях, когда нас не интересует порядок элементов в комбинации, а интересует лишь ее состав, говорят о сочетаниях. Итак, $$k$$ - сочетаниями из $$n$$ элементов называют всевозможные $$k$$ - расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов. Число $$k$$ -сочетаний, которое можно составить из $$n$$ элементов, обозначают через $$C_n^k$$.

Формула для числа сочетаний получается из формулы для числа размещений. В самом деле, составим сначала все $$k$$ -сочетания из $$n$$ элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получается, что все $$k$$ -размещения из $$n$$ элементов, причем каждое только по одному разу. Но из каждого $$k$$ - сочетания можно сделать $$k$$! перестановок, а число этих сочетаний равно $$C_n^k$$. Значит справедлива формула$$k!C_n^k = A_n^k.$$ Из этой формулы находим, что$$C_n^k = \frac{{A_n^k }}{{k!}} = \frac{{n!}}{{(n - k)!k!}}.$$

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

При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского "recurrere" - "возвращаться").

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

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

Пусть $$F_n$$ - число пар кроликов в популяции по прошествии $$n$$ месяцев, и пусть эта популяция состоит из $$N_n$$ пар приплода и $$O_n$$ "старых" пар, то есть $$F_n = N_n + O_n$$. Таким образом, в очередном месяце произойдут следующие события: $$O_{n + 1} = O_n + N_n = F_n$$. Старая популяция в $$(n + 1)$$ -й момент увеличится на число родившихся в момент времени $$n$$. $$N_{n + 1} = O_n$$. Каждая старая пара в момент времени $$n$$ производит пару приплода в момент времени $$(n + 1)$$. В последующий месяц эта картина повторяется:$$O_{n+2}=O_{n+1}+N_{n+1}=F_{n+1},$$ $$N_{n+2} = O_{n + 1}$$

Объединяя эти равенства, получим следующее рекуррентное соотношение:$$F_{n+2}=O_{n+2}+N_{n+2}=F_{n+1}+O_{n+1},$$ $$F_{n+2}=F_{n+1}+F_n$$

Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенное свойство этой последовательности определяется рекуррентным соотношением. Будем предполагать $$F_0 = 0,F_1 = 1$$ (иногда $$F_0 = F_1 = 1$$ ).

Рассмотрим эту задачу немного иначе.

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

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через $$F(n)$$ количество пар кроликов по истечении $$n$$ месяцев с начала года. Ясно, что через $$n + 1$$ месяцев будут эти $$F(n)$$ пар и еще столько новорожденных пар кроликов, сколько было в конце месяца $$n - 1$$, то есть еще $$F(n - 1)$$ пар кроликов. Иными словами, имеет место рекуррентное соотношение$$F(n + 1) = F(n) + F(n - 1)$$ Так как, по условию, $$F(0) = 1$$ и $$F(1) = 2$$, то последовательно находим$$F(2)=3,F(3)=5,F(4)=8$$ и т.д.

В частности, $$F(12) = 377$$.

Числа $$F(n)$$ называются числами Фибоначчи. Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через $$C_m^k$$. Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.

Найти число $$n$$ последовательностей,состоящих из нулей и единиц, в которых никакие две единицы не идут подряд.

Чтобы установить эту связь, возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями - все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию": сама пара появилась в конце 11-го месяца, ее родители - в конце 7-го месяца, "дед" - в конце 5-го месяца и "прадед" - в конце второго месяца. Исходная пара кроликов тогда зашифровывается последовательностью 000000000000.

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

Установленная связь показывает, что число $$n$$ -последовательностей, обладающих указанным свойством, равно $$F(n)$$.

Докажем теперь, что$$F(n)=C_{n+1}^0+C_n^1+C_{n-1}^2+\ldots+C_{n-p+1}^p,$$ где $$p = \frac{{n + 1}} {2}$$, если $$n$$ нечетно, и $$p = \frac{n} {2}$$, если $$n$$ четно. Иными словами, $$p$$ - целая часть числа $$\frac{{n + 1}} {2}$$ (в дальнейшем будем обозначать целую часть числа $$\alpha$$ через $$E(\alpha )$$ ; таким образом, $$p = E(\frac{{n + 1}} {2})$$ ).

В самом деле, $$F(n)$$ - это число всех $$n$$ - последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно $$k$$ единиц и $$n - k$$ нулей, равно $$C_{n - k + 1}^k$$. Так как при этом должно выполняться неравенство $$k \leqslant n - k + 1$$, то $$k$$ изменяется от 0 до $$E(\frac{{n + 1}}{2})$$. Применяя правило суммы, приходим к соотношению (7.3).

Равенство (7.3) можно доказать и иначе. Положим $$G(n)=C_{n+1}^0+C_n^1+C_{n-1}^2+\ldots+C_{n-p+1}^p,\vspace{-1mm}$$ где $$p = \frac{{n + 1}}{2}$$. Из равенства $$C_n^k=C_{n-1}^k+C_{n-1}^{k-1}$$ легко следует, что$$G(n)=G(n-1)+G(n-2).$$ Кроме того, ясно, что $$G(1)=2=F(1)$$ и $$G(2)=3=F(2)$$. Так как обе последовательности $$F(n)$$ и $$G(n)$$ удовлетворяют рекуррентному соотношению $$X(n)=X(n-1)+X(n-2)$$, то имеем$$G(3)=G(2)+G(1)=F(2)+F(1)=F(3),$$ и, вообще, $$G(n) = F(n)$$.

Другой метод доказательства

В предыдущем разделе непосредственно установлена связь между задачей Фибоначчи и комбинаторной задачей. Эту связь можно установить и иначе, непосредственно доказав, что число $$T(n)$$ решений комбинаторной задачи удовлетворяет тому же рекуррентному соотношению$$T(n + 1) = T(n) + T(n - 1),$$ что и числа Фибоначчи. В самом деле, возьмем любую $$(n+1)$$ -последовательность нулей и единиц, удовлетворяющую условию, что никакие две единицы не идут подряд. Она может оканчиваться или на 0, или на 1. Если она оканчивается на 0, то, отбросив его, получим $$n$$ -последовательность, удовлетворяющую нашему условию. Если взять любую $$n$$ - последовательность нулей и единиц, в которой подряд не идут две единицы, и приписать к ней нуль, то получим $$(n + 1)$$ -последовательность с тем же свойством. Таким образом доказано, что число последовательностей, оканчивающихся на нуль, равно $$T(n)$$.

Пусть теперь последовательность оканчивается на 1. Так как двух единиц подряд быть не может, то перед этой единицей стоит нуль. Иными словами, последовательность оканчивается на 01. Остающаяся же после отбрасывания 0 и 1 $$(n - 1)$$ -последовательность может быть любой, лишь бы в ней не шли подряд две единицы. Поэтому число последовательностей, оканчивающихся единицей, равно $$T(n - 1)$$. Но каждая последовательность оканчивается или на 0, или на 1. В силу правила суммы получаем, что $$T(n + 1) = T(n) + T(n - 1)$$.

Таким образом, получено то же самое рекуррентное соотношение. Отсюда еще не вытекает, что числа $$T(n)$$ и $$F(n)$$ совпадают.

Процесс последовательных разбиений

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

Применим описанный прием для решения следующей задачи.

Пусть дано некоторое множество из $$n$$ предметов, стоящих в определенном порядке. Разобьем это множество на две непустые части так, чтобы одна из этих частей лежала левее второй (то есть, скажем, одна часть состоит из элементов от первого до $$m$$ - го, а вторая - из элементов от $$(m + 1)$$ -го до $$n$$ -го). После этого каждую из частей таким же образом разобьем на две непустые части (если одна из частей состоит уже из одного предмета, она не подвергается дальнейшим разбиениям). Этот процесс продолжается до тех пор, пока не получим части, состоящие из одного предмета каждая. Сколько существует таких процессов разбиения (два процесса считаются различными, если хотя бы на одном шагу они приводят к разным результатам)?

Обозначим число способов разбиения для множества из $$n + 1$$ предметов через $$B_n$$. На первом шагу это множество может быть разбито $$n$$ способами (первая часть может содержать один предмет, два предмета,…, $$n$$ предметов). В соответствии с этим множество всех процессов разбиений распадается на $$n$$ классов - в $$s$$ - класс входят процессы, при которых первая часть состоит из $$s$$ предметов.

Подсчитаем число процессов в $$s$$ -м классе. В первой части содержится $$s$$ элементов. Поэтому ее можно разбивать далее $$B_{s - 1}$$ различными процессами. Вторая же часть содержит $$n - s + 1$$ элементов, и ее можно разбивать далее $$B_{n - s}$$ процессами. По правилу произведения получаем, что $$s$$ - класс состоит из $$B_{s - 1} B_{n - s}$$ различных процессов. По правилу суммы отсюда вытекает, что$$B_n=B_0 B_{n - 1} + B_1 B_{n - 2} + \ldots + B_{n - 1} B_0.$$ Таким образом получено рекуррентное соотношение для $$B_n$$. Двоичный поиск, поиск делением пополам. Поиском по числам Фибоначчи называется поиск, основанный на том, что область поиска делится в точках, являющихся числами Фибоначчи.

Задача: "Затруднение мажордома"

Бывают комбинаторные задачи, в которых приходится составлять не одно рекуррентное соотношение, а систему соотношений, связывающую несколько последовательностей. Эти соотношения выражают $$(n + 1)$$ -у члены последовательностей через предыдущие члены не только данной, но и остальных последовательностей.

Задача: "Затруднение мажордома". Однажды мажордом короля Артура обнаружил, что к обеду за круглым столом приглашено 6 пар враждующих рыцарей. Сколькими способами можно рассадить их так, чтобы никакие два врага не сидели рядом?

Если мы найдем какой-то способ рассадки рыцарей, то, пересаживая их по кругу, получим еще 11 способов. Мы не будем сейчас считать различными способы, получающиеся друг из друга такой циклической пересадкой.

Введем следующие обозначения. Пусть число рыцарей равно $$2n$$. Через $$A_n^{}$$ обозначим число способов рассадки, при которых никакие два врага не сидят рядом. Через $$B_n$$ обозначим число способов, при которых рядом сидит ровно одна пара врагов, и через $$C_n$$ - число способов, при которых есть ровно две пары враждующих соседей.

Выведем сначала формулу, выражающую $$A_{n + 1}$$ через $$A_n,B_n,C_n$$. Пусть $$n + 1$$ пар рыцарей посажены так, что никакие два врага не сидят рядом. Мы будем считать, что все враждующие пары рыцарей занумерованы. Попросим встать из-за стола пару рыцарей с номером $$n + 1$$. Тогда возможны три случая: среди оставшихся за столом нет одной пары соседей- врагов, есть одна такая пара и есть две такие пары (ушедшие рыцари могли разделять эти пары). Мы считаем, что $$n > 1$$. При $$n = 1$$ последующие рассуждения теряют силу.

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

Проще всего посадить их, если за столом рядом сидят две пары врагов. В этом случае один из вновь пришедших садится между рыцарями первой пары, а другой – между рыцарями второй пары. Это можно сделать двумя способами. Но так как число способов рассадки $$2n$$ рыцарей, при которых две пары соседей оказались врагами, равно $$C_n$$, то всего получилось $$2C_n$$ способов.

Пусть теперь рядом сидит только одна пара врагов. Один из вернувшихся должен сесть между ними. Тогда за столом окажутся $$2n + 1$$ рыцарей, между которыми есть $$2n + 1$$ мест. Из них два места - рядом с только что севшим гостем – запретны для второго рыцаря, и ему остается $$2n - 1$$ мест. Так как первым может войти любой из двух вышедших рыцарей, то получается $$2(2m-1)$$ способов рассадки. Но число случаев, когда $$2n$$ рыцарей сели так, чтобы ровно одна пара врагов оказалась соседями, ровно $$B_n$$. Поэтому мы получаем $$2(2n - 1)B_n$$ способов посадить гостей требуемым образом.

Наконец, пусть никакие два врага не сидели рядом. В этом случае первый рыцарь садится между любыми двумя гостями - это он может сделать $$2n$$ способами. После этого для его врага останется $$2n - 1$$ мест - он может занять любое место, кроме двух мест, соседних с только что севшим рыцарем. Таким образом, если $$2n$$ рыцарей уже сидели нужным образом, то вернувшихся гостей можно посадить $$2n(2n - 1)A_n$$ способами. Как уже отмечалось, разработанными случаями исчерпываются все возможности. Поэтому имеет место рекуррентное соотношение$$A_{n + 1} = 2n(2n - 1)A_n + 2(2n - 1)B_n + 2C.$$

Этого соотношения пока недостаточно, чтобы найти $$A_n$$ для всех значений $$n$$. Надо еще узнать, как выражаются $$B_{n + 1},C_{n + 1}$$ через $$A_n, B_n, C_n$$.

Предположим, что среди $$2n + 2,n > 1$$ рыцарей оказалась ровно одна пара врагов-соседей. Мы знаем, что это может произойти в $$B_{n + 1}$$ случаях. Во избежание ссоры попросим их удалиться из-за стола. Тогда останется $$2n$$ рыцарей, причем возможно одно из двух: либо среди оставшихся нет врагов-соседей, либо есть ровно одна пара таких врагов - до ухода покинувших зал они сидели по обе стороны от них и теперь оказались рядом. Во втором случае ушедших можно посадить обратно только на старое место - иначе появится вторая пара враждующих соседей. Но так как $$2n$$ рыцарей можно посадить $$B_n$$ способами так, чтобы была только одна пара враждующих соседей, то мы получаем $$2B_n$$ вариантов (возвратившихся рыцарей можно поменять местами). В первом же случае можно посадить ушедших между любыми двумя рыцарями, то есть $$2n$$ способами, а так как их еще можно поменять местами, то получится $$4n$$ способов. Комбинируя их со всеми способами посадки $$n$$ пар рыцарей, при которых нет соседей врагов, получаем $$4nA_n$$ способов. Наконец, номер ушедшей и вернувшейся пары рыцарей мог быть любым от 1 до $$n + 1$$. Отсюда вытекает, что рекуррентное соотношение для $$B_{n + 1}$$ имеет вид$$B_{n + 1} = 4n(n + 1)A_n + 2(n + 1)B_n.$$

Наконец, разберем случай, когда среди $$2n + 2$$ рыцарей было две пары врагов-соседей. Номера этих пар можно выбрать $$C_{n + }^2 = \frac{{n(n + 1)}}{2}$$ способами. Заменим каждую пару одним новым рыцарем, причем будем считать новых двух рыцарей врагами. Тогда за столом будут сидеть $$2n$$ рыцарей, причем среди них либо не будет ни одной пары врагов-соседей (если новые рыцари не сидят рядом), либо только одна такая пара.

Первый вариант может быть в $$A_n$$ случаях. Вернуться к исходной компании мы можем 4 способами благодаря возможности изменить порядок рыцарей в каждой паре. Поэтому первый вариант приводит к $$4C_{n+1}^2A_n=2n(n+1)A_n$$ способами.

Второй же вариант может быть в $$\frac{1}{n}B_n$$ случаях. Имеется $$B_n$$ случаев, когда какая-нибудь пара врагов сидит рядом. Если указать, какая именно пара должна сидеть рядом, получим в $$n$$ раз меньше случаев.

Здесь тоже можно вернуться к исходной компании 4 способами, и мы получаем всего $$2(m+1)B_n$$ способов. Отсюда вытекает, что при $$n \geqslant 1$$$$C_{n + 1} = 2n(n + 1)A_n + 2(n + 1)B_n.$$ Мы получили систему рекуррентных соотношений$$A_{n + 1} = 2n(2n - 1)A_n + 2(2n - 1)B_n + 2C$$ $$B_{n + 1} = 4n(n + 1)A_n + 2(n + 1)B_n.$$ $$C_{n + 1} = 2n(n + 1)A_n + 2(n + 1)B_n.$$ Они справедливы при $$n \geqslant 2$$. Но простой подсчет показывает, что $$A_2 = 2,B_2 = 0,C_2 = 4$$. Поэтому из соотношений 7.10-7.12 вытекает, что $$A_3 = 32,B_3 = 48,C_3 = 24$$. Продолжая далее, находим, что гостей можно посадить за стол требуемым образом $$A_6=12771840$$ способами.