Более того, с помощью метода математической индукции можно доказать следующую формулу:

n

(x+ y)n=C0n xn y0+ C1n xn−1 y1+ …+ C kn xn−k yk+ …+ C nn x0 yn=∑Ckn an−k bk .

k =0

Эта формула носит название бином Ньютона или биномиальное разложение натуральной степени бинома. Здесь словом бином назван двучлен x+ y . Отсюда название для Cnk биномиальный коэффициент.

Биномиальный коэффициент обладает двумя интересными свойствами:

Cnk=Cnn−k −правилосимметрии ,

Cnk=Ckn−1+ Ckn−−11−правило Паскаля.

Эти два свойства (правила) позволяют построить так называемый треугольник Паскаля: 1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

…

Что также даёт нам рекурсивное правило для вычисления биномиальных коэффициентов.

Вспомним теперь о до конца нерешённой нами проблеме: чему равно 2X ? Как мы уже выяснили при рассмотрении сочетаний (без повторений):

n

2X =C 0n+ C1n+ C2n+ …+ C nn=∑C kn .

k =0

Если мы сравним эту формулу с биномом Ньютона, то увидим, что если положить x=1 и y=1 , то получим:

n

(1+ 1)n=C 0n+ C1n+ …+ C kn+ …+ C nn=∑Cnk ,

k=0

что даёт нам ответ на наш вопрос:

2X =2 X .

Обобщение бинома Ньютона является полиномиальная формула:

(x1+ x2+ …+ xk )n= ∑ Pn (r1, r2, …,rk )xr11 xr22 …xrkk ,r1+ r2+ …+ r k=n .

r1, r2, … ,rk

Разбиения

Разбиением множества X, X =n , на k подмножеств называется семейство множеств таких,

что X 1 X 2… X k=X , X i ∩X j= ,1 i< j k , X i≠, 1 i k . Разбиение множества X на k обозначают Π k ( X ) , а множество всех разбиений – Π (X ) Например, выпишем все

разбиения множества X ={1, 2,3} :

на одно: {{1, 2,3}} ; на два: {{1}, {2, 3}} , {{2}, {1, 3}} , {{3}, {1, 2}} ; на три: {{1}, {2}, {3}} .

S kn−1 . Тогда добавляя по очереди к каждому из элементов разбиения, коих k, элемент xn , получим, что их общее количество равно k Skn−1 .

Есть и другая формула для вычисления количества разбиений:

n−1

S kn= ∑ C in−1 S ki −1 , k 2 . i=k−1

Эту формулу мы доказывать не будем. (См. [Окулов: ДМ].)

Рассмотрим теперь всевозможные разбиения множества X, X =n . Очевидно, что

n

Π ( X ) =∑ S kn .

k=0

Количество всех разбиений Π ( X ) называют также числами Белла и обозначают Bn . Для них справедлива следующая рекуррентная формула:

n

Bn+ 1=∑C kn Bk . k =0

Генерация всех перестановок

Перестановки часто встречаются в задачах, решаемых полным перебором. Поэтому уметь реализовывать алгоритм генерации всех перестановок – важно. (Хотя, например, в C++, в его стандартной библиотеке, есть готовый алгоритм под названием next_permutation().)

В принципе, придумать алгоритм, генерирующий все перестановки, не сложно. Посмотрим

–сначала упорядочиваем элементы перестановки в соответствии с заведённом на исходном множестве порядком; таким образом получаем первую перестановку;

Выпишем все его подмножества, соблюдая некоторую последовательность: {a} , {b} , {c} ,

{a ,b} , {a ,c } , {b , c} , {a ,b ,c} . Несложно уловить идею этого алгоритма:

–сначала генерируем одно элементные подмножества;

–затем дополняем полученные подмножества последующими элементами исходного множества;

–повторяем этот процесс до тех пор, пока не сможем больше ничего добавлять (при этом получим исходное множество).

Применим этот алгоритм к нашему примеру ещё раз:

{}→{a}, {b}, {c}

{a}→{a ,b}, {a ,c} {b}→{b , a}, {b , c} {c}→{c ,a}, {c ,b} {a ,b}→{a ,b ,c} {a , c}→{a ,c ,b} {b ,c}→{b ,c ,a }

Из примера хорошо видно, что у этого алгоритма большой недостаток: он генерирует одинаковые множества. Таким образом нужен более хитроумный алгоритм. Один из них заключается в том, что каждому подмножеству Y множества X ={x1, x2, …, xn} ставится в соответствие кортеж (b1, b2, ... ,bn) , где

bi={1,0, xxii YY .

Тогда для нашего примера получим следующее соответствие:

→(0,0,0)

{a }→(0,0,1) {b}→(0,1,0) {c}→(1,0,0) {a ,b}→(0,1,1) {a ,c}→(1,0,1) {b ,c}→(1,1,0) {a ,b ,c}→(1,1,1)

Из примера хорошо видно, что мы установили связь между всеми подмножествами конечного множества мощности n и n-разрядными двоичными числами. Таким образом генерирование всех подмножеств множества мощности n можно свести к генерированию всех n-разрядных двоичных чисел. Последняя задача может быть легко решена следующим образом. Возьмём в качестве первого двоичного числа число 02 . Тогда следующее за ним

числа получаются прибавлением единицы (инкрементированием): 12 , 102 , 112 , 1002 , …,

11...12 .

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