Формула включений-исключений
Из правила сложения с применением других теоретико-множественных операций может быть выведена формула включений-исключений (или принцип (правило) включений-исключений). Это правило позволяет рассчитать количество элементов в объединении конечных множеств, которые в общем случае могут пересекаться друг с другом. При двух множествах 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 процесс нахождения количества элементов объединения A1 È A2 È … È As заключается в начальном суммировании чисел всех элементов, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Данный процесс дал название формулы.
Пример 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.
Дата добавления: 2015-10-05; просмотров: 944;