Глава 1. Комбинаторные схемы

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

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

Пусть имеются два множества Рассмотрим все пары элементов при условии, что первый элемент берется из множества а второй — из множества В. Полученное таким образом множество называется прямым произведением множеств А и В. Напомним некоторые операции над множествами, которыми время от времени будем пользоваться.

прямое произведение множеств.

объединение множеств.

пересечение множеств.

разность множеств.

пустое множество.

универсальное множество.

дополнение множества.