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

Глава 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   Пусть задано универсальное множество  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. Показать, что для чисел выполняется тождество .

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