С62 =	6!		=15.
		2!(6 − 2)!

После того, как выбор произведен, из пары букв <x, y> составляют слова. Количество таких слов вычисляем по формуле для перестановок: P2 = 2! = 2.

Мы совершаем два события последовательно: выбираем буквы и составляем слова, следовательно, по правилу произведения полу-

чаем решение: N1 = С62 P2 =15 2 = 30.

В случае выбора одинаковых букв, слов столько, сколько раз-

личных букв, т.е. n: N2 = n = 6.

Таким образом, общее количество слов

N = N1+N2 = 30+6 = 36.

5.4. Разбиения

Разбиение множества X из n элементов на k блоков – это формирование множества Q = {B1, …, Bk}, в котором B1 B2 ...

Bk = X , Bi ∩ Bj = , Bi ≠ для 1 ≤ i < j ≤ k. Обозначим множе-

ство всех разбиений множества X на k блоков через Πk(X), а через Π(X) – множество все разбиений.

Существует алгоритм построения разбиений, описанный в рекуррентной форме.

Можно показать, что разбиение Q множества {1, …, n} однозначно определяет разбиение Qn−1 множества {1, …, n−1}, которое получается из Q после удаления элемента n (или пустого блока) из соответствующего блока. Также если имеется разбиение W={B1, …, Bk} множества {1, …, n−1}, то можно отыскать все разбиения Q множества {1, …, n}, для которых Qn−1 = W, т.е. такие разбиения:

B1 {n},..., Bk ,

…

B1 ,..., Bk {n},

B1 ,..., Bk ,{n}.

Обозначим такую последовательность через E. Тогда алгоритм разбиений выглядит следующим образом: если у нас есть список

132

Ln−1 всех разбиений множества {1, …, n−1}, то список Ln разбиений множества {1, …, n} будем создавать, заменяя каждое разбиение Q

всписке Ln−1 на соответствующую ему последовательность E.

5.5.Формула включений и исключений

Рассмотрим классическую задачу о количестве элементов, получаемых при объединении множеств (рис. 5.1).

Рис. 5.1

Основная формула, по которой находят количество элементов в объединении двух множеств, вычисляется по диаграмме Эйлера– Венна, так как часть элементов принадлежат одновременно А и В и не могут учитываются дважды:

| A B |=| A | + | B | −| A ∩ B | .

Для трех множеств А, В и С формула пересчета выглядит следующим образом:

| A B C |=| A| +| B | +| C | −| A ∩ B | −| A ∩C | −

−| B ∩C | +| A ∩ B ∩C | .

Теорема 5.4 (формула включений и исключений). Если X1, X2, …, Xn некоторые множества и их мощность равна |X1|, |X2,|,…,|Xn|, тогда

| X1 X2 ... Xn |=| X1 | +| X2 | +...+ | Xn | − −{| X1 ∩ X2 | + | X1 ∩ X3 | +...+ | Xn−1 ∩ Xn |} + +{| X1 ∩ X2 ∩ X3 | +...+| Xn−2 ∩ Xn−1 ∩ Xn |} + +(−1)n−1 | X1 ∩ X2 ∩... ∩ Xn | .

Обобщая, получаем формулу включения и исключения для N объектов со свойствами, которыми эти объекты могут обладать или не обладать. Пусть имеется N объектов, которые могут обладать n

133

свойствами a1, a2,..., an. Обозначим через N (ai, aj,..., ak) число предметов, обладающих свойствами ai, aj,..., ak и, быть может, какимилибо другими свойствами. Тогда число N предметов, не обладающих ни одним из свойств, a1, a2,..., an, даётся формулой

N= N – N (a1) – N (a2) –... – N (an) + N (a1, a2) + N (a1, a3) +...

...+ N (an-1, an) – N (a1, a2, a3) –... – N (an-2, an-1, an) +...

...+(–1) n N (a1,..., an).

Задача 5.12. В аудитории находится несколько программистов. Шестеро знают VISIAL BASIC, шестеро – PHP, семеро умеют программировать на JAVA. Четверо знают VISIAL BASIC и PHP, трое

VISIAL BASIC и JAVA, двое – PHP и JAVA. Один из них умеет программировать на всех языках. Сколько человек в аудитории? Сколько из них знают только VISIAL BASIC?

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

Зададим PVB – свойство знать VISIAL BASIC, PP – свойство знать PHP, PJ – свойство знать JAVA.

Тогда количество программистов в аудитории n

n = n(PVB ) + n(PP ) + n(PJ ) + n(PVB & PP ) − n(PVB & PJ ) −

−n(PP & PJ ) + n(PVB & PP & PJ ) = 6 + 6 + 7 − 4 −3 − 2 +1 =11.

При этом по формуле включений и исключений получается, что людей, знающих только VISIAL BASIC, нет:

n(PVB , PP , PJ ) = n(PVB ) − n(PVB & PP ) − n(PVB & PJ ) +

+n(PVB & PP & PJ ) = 6 − 4 −3 +1 = 0.

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

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

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

134

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

Пусть Fn – число пар кроликов в стае по прошествии n месяцев, и пусть эта стая состоит из Nn пар приплода и On «старых» пар, т.е.

Fn = N n + On .

Таким образом, в очередном месяце произойдут следующие события: On+1 = Nn + On = Fn . Старая стая в (n+1)-й момент увеличит-

ся на число родившихся кроликов в момент времени n. В последующий месяц эта картина повторяется:

On+2 = On+1 + Nn+1 = Fn+1, Nn+2 = On+1.

Объединяя эти равенства, получим следующее рекуррентное соотношение:

Fn+2 = On+2 + Nn+2 = Fn+1 + On+1 , Fn+2 = Fn+1 + Fn .

Будем предполагать F0 = 0, F1 =1(иногдаF0 = F1 =1 ).

Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенное свойство этой последовательности определяется рекуррентным соотношением.

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

F (n +1) = F (n) + F(n −1) ,

где F(n) – называются числа Фибоначчи.

Другим примером являются числа Каталана. Они появляются в контексте следующей задачи: нужно найти число различных последовательных действий, чтобы вычислить сумму S0, …, Sn, складывая любые два рядом стоящих числа и результат помещая на их место. Тогда если обозначить искомое число через Сn, то производящая функция будет выглядеть, как

Cn = C0Cn - 1 + C1Cn - 2 + C2Cn - 3 +...+ Cn - 2C1 + Cn - 1C0.

Для чисел Каталана известно и нерекуррентное соотношение:

135