При решении теоретико-множественных задач большое зна­чение имеет определение мощности конечных множеств.

Очевидно, что

,

когда А и В пересекаются.

Кроме того,

,

когда А включается в В;

,

когда А и В пере­секаются.

Нетрудно заметить, что

.

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

Пусть в базе данных имеется n записей об объектах недвижи­мости (например, квартирах) в виде запроса (что требуется) и предложения (что имеется) Требуется найти такие пары записей, в которых предложение первой записи совпадает с запросом вто­рой и, наоборот, предложение второй записи совпадает с запро­сом первой («подбор вариантов обмена»).

Допустим, на проверку варианта обмена тратится одна мил­лисекунда. Можно показать, что при сравнении каждой записи с каждой требуется  сравнений.

Например, n = 8:

(1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8),

(2,3), (2,4), (2,5), (2,6), (2,7), (2,8),

(3,4), (3,5), (3,6), (3,7), (3,8),

(4,5), (4,6), (4,7), (4,8),

(5,6), (5,7), (5,8),

(6,7), (6,8),

(7,8).

Всего 28 вариантов:

8 ∙ 7/2 = 28 = 7 + 6 + 5 + 4 + 3 + 2 + 1.

Здесь отношение сравнения симметрично и сам с собой вариант не сравнивается.

Если n = 100, то при указанном быстродействии на сравнения уйдет 4,95 с. Но если n = 100000 (в задачах реальной размернос­ти), то необходимо 1999950 с, т.е. без малого 1 389 ч. Столько ждать клиент вряд ли будет. И это только сравнение прямых вариантов, а существуют вариан­ты, в которых число участников сделки больше двух.

Поэтому комбинаторные вычисления требуют предваритель­ного анализа и ориентировочной количественной оценки исход­ных данных. Иначе можно подумать, что компьютер просто «за­вис» и не выдает ответа. Здесь речь идет о сложности вычислений по времени решения. В ряде задач комбинаторной слож­ности необходимо время, сравнимое с геологическими эпохами. Но есть еще и пространственная сложность – по объему памяти. Ведь промежуточные результаты часто надо где-то хра­нить. В ряде задач требуется объем памяти, превышающий коли­чество атомов во Вселенной.

Основным инструментом такого анализа сложности вычисле­ний и является комбинаторика.

Основная задача комбинаторики – пересчет и перечисление элементов в конечных мно­жествах.

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

Рассмотрим основополагающие правила комбинаторики – правила суммы и произведения.

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

.

Таково комбинаторное правило суммы. Для k = 2 это правило формулируется следующим образом. Если объект х может быть выбран n способами из множества X, а объект у из непересекающегося с ним множества Y – другими m способами, то выбор «х или у» может быть осуществлен n + m способами.

Правило произведения для k = 2 формулируется следующим образом. Если объект х может быть выбран n способами и после каждого из таких выборов объект у, в свою очередь, может быть выбран m способами, то выбор упорядоченной пары – вектора (х,у) может быть осуществлен n·m способами. Например:

.

Тогда упорядоченные пары (х, у) описываются декартовым произведением:

.

Выбор упорядоченной последовательности из k объектов век­тора  может быть осуществлен  способами, где  – число способов выбора i-гo объекта , i меняется от 1 до k (записывается:).

В частности, если все  равны, что может быть, например, в случае, когда элементы принадлежат одному и тому же множест­ву, т.е. рассматривается декартово произведение , то число спо­собов равно n^k.

Набор элементов  из множества  (век­тор) называется выборкой (комбинацией) объема k из n элемен­тов или, иными словами, --выборкой.

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

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

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