Комбинаторные вычисления на конечных множествах
Введение в комбинаторику
Предметом теории комбинаторных алгоритмов, часто называемой комбинаторными вычислениями, являются вычисления на дискретных математических структурах. В этой теории большое внимание уделяется алгоритмическому подходу к решению задач дискретной математики, оптимизации перебора вариантов, сокращению числа рассматриваемых решений.
Область комбинаторных алгоритмов включает в себя задачи, которые требуют подсчёта (оценивания) числа элементов в конечном множестве или перечисления этих элементов в специальном порядке (приложение Б). При этом широко применяется процедура выбора элементов с возвращением и её варианты.
Существуют два вида задач подсчёта. В простом случае задаётся конкретное множество и требуется определить точно число элементов в нём. В общем случае имеется семейство множеств, заданное некоторым параметром, и определяется мощность множества как функция параметра. При этом часто бывает достаточной оценка порядка функции, а иногда требуется только оценка скорости её роста. Например, если мощность подлежащего рассмотрению множества растёт по некоторому параметру экспоненциально, то этого может оказаться достаточно для того, чтобы отказаться от предложенного подхода к изучению проблемы, не занимаясь различными деталями. К этому, более общему, типу проблем применяются процедуры асимптотических разложений, рекуррентных соотношений и производящих функций.
Асимптотика
Асимптота — особая линия (чаще всего прямая), являющаяся предельной для рассматриваемой кривой.
Асимптотика — это искусство оценивания и сравнения скоростей роста функций. Говорят, что при х ®¥ функция 
"ведёт себя, как х ", или "возрастает с такой же скоростью, как х ", и при х ®0 "ведёт себя, как 1/ x ". Говорят, что "log x при x ®0 и любом e>0 ведёт себя, как x e, и что 
при n ®¥ растёт не быстрее, чем n log n ". Такие неточные, но интуитивно ясные утверждения полезны при сравнении функций так же, как и соотношения <, £ и = при сравнивании чисел.
Определим три основных асимптотических соотношения.
Определение 1. Функция f (x) эквивалентна g (x) при х ® x0, если и только если 
=1.
В этом случае говорят, что функция f (x) асимптотически равна функции g (x) или что f (x) растёт с такой же скоростью, как и g (x).
Определение 2. f (x)=o(g (x)) при x ® x0, если и только если 
=0.
Говорят, что при x ® x0 f (x) растёт медленнее, чем g (x), или что f (x) "есть о-малое" от g (x).
Определение 3. f (x)=О(g (x)) при x ® x0, если и только если существует константа С такая, что sup =С.
В этом случае говорят, что f (x) растёт не быстрее, чем g (x), или что при x ® x0 f (x) "есть О-большое" от g (x).
Cоотношение f (x)= g (x)+ o (h (x)) при x ®¥ означает, что f (x)-g (x) =o (h (x)). Аналогично f (x)= g (x)+ О (h (x)) означает, что f (x) -g (x) =О (h (x)).
Выражения О(·) и о(·) могут использоваться также и в неравенствах. Например, неравенство x + o (x)£2 x при x ®0 означает, что для любой функции f (x) такой, что f (x) =o (x), при x ®¥ имеет место соотношение x+f (x)£2 x для всех достаточно больших значений х.
Приведём некоторые полезные асимптотические равенства.
Полином асимптотически равен своему старшему члену:
при x ®¥; (4.1)
при x ®¥; (4.2)
при x ®¥ и ak ¹0. (4.3)
Суммы степеней целых чисел удовлетворяют соотношению:
при n ®¥. (4.4)
Отсюда, в частности, имеем при n ®¥
и 
. (4.5)
В более общем случае при n ®¥ и для любого целого k ³0
; (4.6)
. (4.7)
Рекуррентные соотношения
Понятие рекуррентных соотношений проиллюстрируем на классической проблеме, поставленной и изученной Фибоначчи около 1200 г.
Фибоначчи поставил свою проблему в форме рассказа о скорости роста популяции кроликов при следующих предположениях. Все начинается с одной пары кроликов. Каждая пара кроликов становится фертильной (fertile – плодовитый) через месяц, после чего каждая пара рождает новую пару кроликов каждый месяц. Кролики никогда не умирают, и их воспроизводство никогда не прекращается. Пусть Fn - число пар кроликов в популяции по прошествии n месяцев и пусть эта популяция состоит из Nn пар приплода и On “старых” пар, т.е. Fn = Nn + On. Таким образом, в очередном месяце произойдут следующие события:
- старая популяция в (n +1)-й момент увеличится на число родившихся в момент времени n, т.е. On+1 = On + Nn = Fn;
- каждая старая в момент времени n пара производит в момент времени (n +1) пару приплода, т.е. Nn+1 = Cn.
В последующий месяц эта картина повторяется:
On+2 = On+1 + Nn+1 = Fn+1,
Nn+2 = On+1;
объединив эти равенства, получим рекуррентное соотношение Фибонначи:
On+2 + Nn+2 = Fn+1 + On+1,
или
Fn+2 = Fn+1 + Fn. (4.8)
Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенные свойства этой последовательности определяются рекуррентным соотношением (4.8). Обычно полагают F0 =0, F1 =1 (иногда полагают F0 = F1 =1).
Рекуррентное соотношение (4.8) является частным случаем однородных линейных рекуррентных соотношений с постоянными коэффициентами:
xn = a1xn-1 + a2xn-2 +…akxn-k, (4.9)
где коэффициенты ai не зависят от n и x1, x2, …, xk считаются заданными.
Существует общий метод решения (т.е. отыскания xn как функции n) линейных рекуррентных соотношений с постоянными коэффициентами. Этот метод рассмотрим на примере соотношения (4.8). Найдём решение в виде
Fn = crn (4.10)
с постоянными с и r. Подставляя это выражение в (4.8), получим
crn+ 2 = crn+ 1 + crn,
или
crn (rn-r -1)=0. (4.11)
Это означает, что Fn = crn является решением, если либо с =0, либо r = 0 (и отсюда Fn=0 для всех n), а также (и это более интересный случай) если r 2 - r -1=0, причём константа с произвольна. Тогда из (4.11) следует
r = 
или r = 
. (4.12)
Число »1,618 известно как ²золотое² сечение, поскольку с древних времен считается, что треугольник (прямоугольник) со сторонами 1 и имеет наиболее приятные для глаза пропорции.
Сумма двух решений однородного линейного рекуррентного соотношения, очевидно, также является решением, и можно на самом деле показать, что общее решение последовательности Фибоначчи имеет вид
Fn = 
, (4.13)
где константы с и с’ определяются начальными условиями. Положив F0=0 и F1=1, получим следующую систему линейных уравнений:
, (4.14)
решение которой даёт
c = - c' = 
. (4.15)