5.2. Основные правила подсчета чисел комбинаторных множеств

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

5.2.1. Правило сложения

Допустим, всю совокупность подсчитываемых комбинаторных множеств C(А) можно разделить на n частей С₁(А), С₂(А), ..., С_n(А), содержащих, соответственно, N(С₁(А)), N(С₂(А)), …, N(С_n(А)) множеств, таким образом, что данные части не пересекаются друг с другом и в сумме дают все множество C(А).

Тогда общее число N(C(А)) всех подсчитываемых множеств равно сумме данных значений N(С₁(А)), N(С₂(А)),…, N(С_n(А)):

N(С(А)) = N(С₁(А)) + N(С₂(А)) + … + N(С_n(А)).

Данную формулу называют правилом сложения.

Рис. 5.1. Расчетная схема правила сложения

5.2.2. Формула включений-исключений

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

N(AB) = N(A) + N(B) – N(AB), где N(A), N(B), N(AB), N(AB) – числа элементов в исходных множествах А и В, их объединении AB и пересечении AB.

Рис. 5.2. Объединение двух множеств A и B

Поскольку вывод данной формулы требует применения дополнительных теоретико-множественных операций разбиения множества на разность и пересечение, то правило включений-исключений нельзя вывести из правила сложения средствами самой теории (комбинаторики). Для сведения правила включений-исключений к параллельной схеме расчета в формуле необходимо использовать разности множеств (рис. 5.2):

N(AB) = N(A\B) + N(B\A) + N(AB), где A\B – результат вычитания множества B из множества A, B\A – результат вычитания множества A из множества B.

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

Рис.5.3. Расчетная схема правила включений-исключений для двух множеств

В случае количества множеств s > 2 процесс нахождения количества элементов объединения A₁  A₂  …  A_s заключается в начальном суммировании чисел всех элементов, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Данный процесс дал название формулы.

Пример 1. На выставке представлено 23 картины, в которых использованы только красный и синий цвета. Из них 8 выполнены только в красном цвете, на 11 одновременно использован и красный и синий цвет. Сколько выставлено картин, в которых использован синий цвет?

Решение. Обозначим множество картин, в которых использован красный цвет (только красный и вместе с синим), через A, а множество картин, в которых есть синий цвет, через В. В условии задано общее число картин: N(A  B) = 23, число картин в разности N(A\B) = 8 и число картин в пересечении N(A  B) = 11. Подставляя данные значения в формулу для N(A  B), выраженную через разности множеств, получим вначале число картин, в которых использован только синий цвет:

N(B\A) = N(A  B) – N(A\B) – N(A  B) = 23 – 8 – 11 = 4.

Искомое общее число картин, в которых использован синий цвет, равно:

N(B) = N(B\A) + N(A  B) = 4 + 11 = 15.

Ответ: 15.