- •Глава I. Азы комбинаторики
- •§ 1. Основные принципы комбинаторики
- •§ 2. Размещения и перестановки без повторений
- •§ 3. Размещения и перестановки с повторениями
- •§ 4. Подмножества конечных множеств и сочетания
- •§ 5. Сочетания с повторениями
- •§ 6. Принцип включения-исключения
- •§ 7. Примеры решения простейших комбинаторных задач
- •§ 8. Примеры других комбинаторных объектов и сводка некоторых результатов
- •Биномиальные коэффициенты
- •Числа Стирлинга
- •Глава II. Рекуррентные соотношения
- •§ 1. Определение и примеры рекуррентных соотношений
- •Основы метода конечных разностей
- •§ 2. Метод производящих функций для нахождения общего решения линейного однородного рекуррентного соотношения второго порядка
- •Алгоритм нахождения общего решения
- •§ 3. Решение линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 4. Метод производящих функций для решения общего линейного однородного рекуррентного соотношения с постоянными коэффициентами
- •Алгоритм нахождения общего решения
- •§ 5. Частные решения линейных неоднородных рекуррентных соотношений с постоянными коэффициентами и специальной правой частью
- •§ 6. Некоторые примеры применения производящих функций
§ 4. Подмножества конечных множеств и сочетания
Если A = {a0 , … , an–1 } – конечное множество из n элементов, то символом В(А) будем обозначать булеан множества A, т.е. множество всех подмножеств множества А. Для того, чтобы поближе познакомиться с булеаном, рассмотрим следующую задачу: как перечислить все элементы булеана В(А) конечного n-элементного множества А = {a0 , … , an–1} ? Для бесконечных множеств булеан, очевидно, тоже бесконечен и поэтому менее обозрим, нежели в конечном случае.
Каждому подмножеству X A сопоставим n-значное двоичное число (X) = n–12n–1+…+020 = ( )2 с цифрами i {0, 1} (0 i n–1), однозначно определяющее это подмножество. Вместо двоичного числа в этих рассуждениях можно рассматривать и просто набор (X) = (n–1 ; … ; 0) длины n из нулей и единиц. Итак, положим (0 i n–1). Кстати, именно такой способ интерпретации множеств реализуется в некоторых языках программирования.
Примеры. 1. Если A = {a0 , a1 , a2} и X = {a0 , a2}, то (X) = 1012 = 5, а если X = {a1 }, то (X) = 0102 = 2. Вообще, можно составить полный список подмножеств множества А:
Количество элементов |
Подмножество X |
(X) |
0 |
|
0002 = 0 |
1 |
{a2 } |
1002 = 4 |
{a1 } |
0102 = 2 |
|
{a0 } |
0012 = 1 |
|
2 |
{a1 , a2 } |
1102 = 6 |
{a0 , a2 } |
1012 = 5 |
|
{a0 , a1 } |
0112 = 3 |
|
3 |
{a0 , a1 , a2 } |
1112 = 7 |
Видно, что значения (X) пробегают всё множество {0, 1, 2, 3, 4, 5, 6, 7}, и В(А) состоит из восьми элементов.
2. Перечислить все подмножества четырёхэлементного множества A = {a0 , a1 , a2 , a3 }.
Будем перечислять подмножества, выписывая соответствующие им наборы из нулей и единиц:
№ |
набор |
подмножество |
0 |
(0, 0, 0, 0) |
|
1 |
(0, 0, 0, 1) |
{a0 } |
2 |
(0, 0, 1, 0) |
{a1 } |
3 |
(0, 0, 1, 1) |
{a1 , a0 } |
4 |
(0, 1, 0, 0) |
{a2 } |
5 |
(0, 1, 0, 1) |
{a0 , a2 } |
6 |
(0, 1, 1, 0) |
{a1 , a2 } |
7 |
(0, 1, 1, 1) |
{a0 , a1 , a2 } |
8 |
(1, 0, 0, 0) |
{a3 } |
9 |
(1, 0, 0, 1) |
{a0 , a3 } |
10 |
(1, 0, 1, 0) |
{a1 , a3 } |
11 |
(1, 0, 1, 1) |
{a0 , a1 , a3 } |
12 |
(1, 1, 0, 0) |
{a2 , a3 } |
13 |
(1, 1, 0, 1) |
{a0 , a2 , a3 } |
14 |
(1, 1, 1, 0) |
{a1 , a2 , a3 } |
15 |
(1, 1, 1, 1) |
{a0 , a1 , a2 , a3 } |
В общем случае наименьшее значение (X), очевидно, равно 0…02 = 0 для множества X = , а наибольшее значение равно 1…12 = 12n–1+…+120 = = 2n–1+…+ 2+1 = = 2n – 1 при X = {a0 , … , an–1 } = A. Таким образом построена функция : В(A) {0, 1, … , 2n – 1}. Докажем, что она биективна.
Инъективность: X1 , X2 В(А) (X1) = (X2) X1 = X2 . Действительно, если = (X1) = (X2) = , то 0 = 0 , … , n–1 = n–1 . Поэтому для любого элемента ai A верно ai X1 i = 1 i = 1 ai X2 и значит, множества X1 и X2 состоят из одних элементов, т.е. равны.
Сюръективность: n {0, 1, … , 2n–1} X В(А) (X) = n. Действительно, по любому двоичному числу n = образуем множество X по правилу ai X i = 1 (0 i n–1). Ясно, что (X) = = n.
Теорема (о нумерации подмножеств конечного множества). (1) Существует биективное соответствие f : В(A) {0, … , 2n – 1} между всеми подмножествами конечного множества A = {a1 , … , an} из n элементов и интервалом целых чисел 0 .. 2n – 1.
(2) Существует биективное соответствие f : Вm(A) Bm {0, … , 2n–1} между всеми m-элементными подмножествами конечного множества A = {a1 , … , an} из n элементов и всеми целыми числами диапазона 0 .. 2n – 1, имеющими в своей двоичной записи ровно m единиц (и n–m нулей).
Следствие (о количестве наборов из нулей и единиц длины n). Количество всевозможных наборов из нулей и единиц длины n равно 2n .
Доказательство следствия очевидно, т.к. количество всевозможных наборов из нулей и единиц длины n равно количеству чисел от 0 до 2n – 1, т.е. 2n.
Следствие доказано.
Следствие (о количестве подмножеств n-элементного множества). Любое n-элементное множество содержит 2n подмножеств.
Доказательство. Построенное выше взаимно однозначное отображение : В({a0 , … , an–1}) {0, 1, … , 2n – 1} показывает, что количество элементов в В({a0 , … , an–1}) равно количеству элементов в {0, 1, … , 2n – 1}, т.е. 2n .
Если A = {a1 , … , an } – конечное множество из n элементов, то сочетанием (или выборкой) из n объектов a1 , … , an по k штук (сочетанием из n по k) называется произвольное k-элементное подмножество A. Количество всех сочетаний из n по k обозначается .
Теорема (о перечислении сочетаний). Существует взаимно однозначное соответствие между всеми сочетаниями из n элементов конечного множества A = {a1 , … , an} по m и всеми целыми числами диапазона 0 .. 2n – 1, имеющими в своей двоичной записи ровно m единиц (и n–m нулей).
Следствие (о количестве всех сочетаний из n элементов). Общее количество всех сочетаний из n элементов по всем m (0 m n) равно 2n .
Имея алгоритм перечисления всех подмножеств множества A, легко понять, как получить алгоритм перечисления сочетаний. Нужно среди всех наборов из нулей и единиц длины n отобрать наборы ровно с k единицами и построить по ним соответствующие k-элементные множества.
Пример: Выписать все сочетания из четырёх элементов по два для множества A = {1, 2, 3, 4}.
Среди всех наборов из нулей и единиц, перечисленных выше, отбираем только те, которые содержат 2 единицы и 4 нуля:
№ |
набор |
сочетание |
1 |
(0, 0, 1, 1) |
{1, 2} |
2 |
(0, 1, 0, 1) |
{1, 3} |
3 |
(0, 1, 1, 0) |
{2 , 3} |
4 |
(1, 0, 0, 1) |
{1, 4} |
5 |
(1, 0, 1, 0) |
{2, 4} |
6 |
(1, 1, 0, 0) |
{3, 4} |
Вычислим теперь количество сочетаний из n по k. Ясно, что результат не зависит от конкретной природы элементов множества A. Поэтому будем считать, что множество A состоит из n независимых переменных. Для произвольных a1 , … , ak A рассмотрим произведение (1+a1x)(1+a2x)…(1+anx). Если раскрыть скобки, то в полученной сумме мономов (без приведения подобных) моном степени s получается при перемножении произвольно выбранных s элементов , где i1 < i2 < … < is . Таким образом, коэффициент при таком мономе соответствует выбору сочетания { }, причём это соответствие взаимно однозначно, т.к. множество { } однозначно определяется элементами и не зависит от порядка их перечисления. После приведения подобных при xs будет стоять коэффициент, равный сумме всех произведений вида , а количество таких слагаемых в точности равно количеству сочетаний из n по s.
(1+a1x)(1+a2x)…(1+anx) =
= 1 + (a1+…+ak)x+(a1a2+a1a3+…+ak–1ak)x2 + …
… +(a1…an–1+…+a2…an)xn–1 + a1…anxn .
Если теперь подставить a1 = a2 = … = an = 1, то, с одной стороны, при xk получится количество сочетаний из n по k, а с другой, – мы придём к формуле бинома Ньютона:
(1 + x)n = 1+nx+ x2 + … + xk + … +nxn–1+xn .
Следовательно, – биномиальный коэффициент, который равен количеству сочетаний из n элементов по k.
Из формулы бинома Ньютона немедленно получаются следующие полезные равенства:
Кроме того, – известные свойства биномиальных коэффициентов.
Отметим ещё раз связь между размещениями, сочетаниями и перестановками. Сочетание из n по k отличается от размещения без повторений тем, что для сочетания не важен порядок элементов. Поэтому, произвольным образом переставляя элементы размещения, будем получать одно и то же сочетание. Количество перестановок рассматриваемого сочетания равно k ! , так что одному сочетанию соответствует k ! размещений. Поэтому .