Элементы комбинаторного анализа

Глава 1

Элементы комбинаторного анализа

1.1. Начальные понятия теории множеств

Под множеством
понимают объединение в единое целое определенных вполне различаемых объектов. Объекты при этом называют элементами
образуемого ими множества.

Для обозначения множеств используют прописные буквы, а для обозначения элементов множеств – строчные буквы латинского алфавита.

Запись означает, что является элементом множества ; в противном случае пишут .

Множество называют конечным
, если оно содержит конечное число элементов, и бесконечным
, если оно содержит бесконечное число элементов. Множество, не содержащее элементов, называют пустым
и обозначают символом .

Число элементов конечного множества называют его мощностью
и обозначают .

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

Конечное множество можно задать путем перечисления его элементов, т.е. .

Если каждый элемент множества есть элемент множества B
, то говорят, что есть подмножество
и записывают .

Заметим, что пустое множество считают подмножеством любого множества.

Если и , то говорят, что множества и равны
, и пишут: .

Если и , то называют собственным
подмножеством .

Обычно в конкретных рассуждениях элементы всех множеств берут из некоторого одного, достаточно широкого множества (в каждом случае своего), которое называют универсальным
и обозначаютI
.

Пусть A
и B
- подмножества универсального множества I
. Введем следующие операции над множествами

:

Название операции	Обозначение операции	Определение операции	Геометрическая иллюстрация
Объединение A и B
Пересечение A и B
Разность A и B
Дополнение A
Декартово произведение A и B		, здесь - упорядоченная пара

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

Свойства операций над множествами

Пусть задано универсальное множество I
. Тогда для любых множеств выполняются следующие свойства:

коммутативные законы
:

1. ; 2. ;

ассоциативные законы
:

3.;

4. ;

дистрибутивные законы
:

5.;

6. ;

законы идемпотентности
:

7. ; 8. ;

законы де Моргана
:

9. ; 10. ;

законы нуля
:

11. ; 12. ;

законы единицы
:

13. ; 14. ;

законы поглощения
:

15. ; 16. ;

законы дополнения
:

17. ; 18. ;

закон двойного дополнения
:

19. .

Операции объединения, пересечения и декартового произведения можно обобщить на случай произвольного конечного числа участников.

Декартовым произведением
n
множеств называют множество

.

В частном случае одинаковых сомножителей декартово произведение обозначают .

Объединением
множеств называют множество, любой элемент которого является элементом хотя бы одного из данных множеств. Обозначение:
или .

Пересечением
множеств называют множество, любой элемент которого является элементом каждого из данных множеств. Обозначение:
или.

Если , то множества и называются непересекающимися
.

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

Утверждение 1.
Если между конечными множествами и существует взаимно однозначное соответствие, то .

Утверждение 2.
Если
- конечные попарно непересекающиеся множества, то множество
также конечно и
.

Утверждение 3 (принцип включения-выключения).
Если
- конечные множества, то множество
также конечно и

.

Утверждение 4.
Если
- конечные множества, то множество
также конечно и
.

1.2. Комбинаторные объекты и комбинаторные числа

В комбинаторном анализе изучаются различные объекты, порождаемые элементами из конечного множества , а также числовые характеристики этих объектов.

При подсчете числа объектов с наперед заданными свойствами используются следующие два правила.

Правило суммы. Если объект может быть выбран способами, а объект способами, то выбор «либо , либо » может быть осуществлен способами.

Правило произведения. Если объект может быть выбран способами и после каждого из таких выборов объект в свою очередь может быть выбран способами, то выбор « и » в указанном порядке может быть осуществлен способами.

Набор элементов из множества называется выборкой
объема из элементов или -выборкой.

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

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

Рассмотрим некоторые комбинаторные объекты и их комбинаторные числа.

1.
Размещения.

Размещением
элементов из по (или размещением
из n
элементов по k
) называется упорядоченная -выборка без повторений.

Пример 1
. Пусть и . Выпишем все размещения из этого множества по два:

, , , , , .

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

при .

При не су

ществует размещений из по , следовательно, при ; при полагаем .

Упражнение 1.
Показать, что для чисел выполняются тождества

,

.

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

Перестановками
элементов множества (или перестановками из
n
элементов) называются упорядоченная -выборка без повторений.

Пример 2
. Пусть . Выпишем все перестановки этого множества:

, , , , , .

Очевидно, что перестановки из элементов – частный случай размещений из элементов по , когда . Поэтому их число равно

3.
Сочетания.

Сочетанием
элементов из по (или сочетанием
из n
элементов по k
) называется неупорядоченная -выборка без повторений.

Пример 3
. Пусть и . Выпишем все сочетания из этого множества по два:

, , .

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

, .

Из последней формулы следует

и .

При полагают . При полагают , поскольку при не существует сочетаний из элементов по .

Наряду с обозначением часто используется обозначение .

Числа называются также биномиальными коэффициентами
, посколькуони фигурируют в функциональном тождестве, называемом формулой бинома Ньютона:

. (1)

Формулу (1) несложно доказать, используя метод математической индукции. Советуем провести доказательства в качестве упражнения.

Полагая в (1) , получим тождество

; (2)

При получим

. (3)

При четном n
из соотношений (2) и (3) следуют тождества

, .

При нечетном n
из соотношений (2) и (3) следуют тождества

, .

Упражнение 2.
Показать, что для чисел выполняется тождество .

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

1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
.	.	.	.	.	.

В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число находится в () ряду на () месте.

Упражнение 3.
Показать, что последовательность , где обладает свойством:

, если n
четно

и

если n
нечетно.

4.
Размещения с повторениями.

Размещением с повторениями
элементов из по (или размещением с повторением
из n
элементов по k
) упорядоченная -выборка с повторениями.

Пример 4
. Пусть и . Выпишем все размещения с повторениями из этого множества по два:

, , , ,, , , , .

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

.

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

Пример 5
. 3-х мерный куб размера 2 состоит из следующих элементов: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).

5.
Сочетания с повторениями.

Сочетанием с повторениями
элементов из по (или сочетанием с повторением
из n
элементов по k
) неупорядоченная -выборка с повторениями.

Пример 5
. Пусть и . Выпишем все сочетания с повторениями из этого множества по два:

, , , , , .

Можно показать, что число сочетаний с повторениямииз n
элементов по k
равно .

6.
Булеан множества .

Множество всех подмножеств называется булеаном
множества
и обозначается как .

Пример 6
. Пусть . Тогда множество есть булеан множества .

Мощность булеана множества
равна .
Докажем это. Пусть . Возьмем произвольное множество и сопоставим ему взаимнооднозначным образом двоичный набор :

Отсюда получаем, что мощность булеана совпадает с мощностью множества, образованного всеми двоичными наборами, т.е. с мощностью единичного -мерного куба
. Таким образом, .

7. Покрытие множества .

Семейство подмножеств множества называют покрытием
, если .

8. Разбиение множества .

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

Пример 7
. Пусть . Тогда семейство подмножеств является как разбиением, так и покрытием. В то время как семейство является покрытием, но не является разбиением.

Явные формулы для числа покрытий и разбиений множества получаются довольно трудоемко. За неимением времени в нашем курсе эти задачи не рассматриваются.

1.3. Производящие функции

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

Пусть имеется последовательность чисел и последовательность функций . Этим последовательностям сопоставим формальный ряд (для конечных последовательностей этот ряд превращается в многочлен). В ряде случаев, например, при определенных ограничениях, данный ряд может оказаться сходящимся и задавать некоторую функцию : . Эта функция называется производящей
для последовательности относительно последовательности функций .

В качестве обычно используют и .

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

.

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

.

Сравнивая коэффициенты при в левой и правой частях последнего тождества, получаем

.