Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод включений и исключений ⇐ ПредыдущаяСтр 4 из 4
Поставим задачу подсчитать количество элементов в объединении конечных множеств , которые могут иметь непустые пересечения между собой, т. е. это объединение в общем случае не является разбиением. Для двух множеств имеем формулу (1). Обозначим и применим эту формулу для трех множеств, используя дистрибутивность операций объединения и пересечения множеств: (6) В результате по индукции получаем формулу включений и исключений: (7) Название этой формулы подчеркивает использование последовательных включений и исключений элементов подмножеств. Часто формулу (7) записывают в другом виде. Рассмотрим некоторое -множество элементов и -множество свойств , которыми элементы могут обладать или не обладать. Пусть подмножество состоит из элементов, обладающих свойством , . Тогда подмножество объединяет элементы из , которые обладают хотя бы одним из свойств множества . Дополнение составляют элементы, которые не обладают ни одним из свойств , . Пересечения вида объединяют элементы, обладающие одновременно свойствами . Если обозначить число таких элементов через , то для числа элементов множества имеем формулу обращения (8) Использование формулы (8) в комбинаторике называют методом включений и исключений. Пример 5. Рассмотрим слова длины в алфавите {0, 1, 2}. Сколько имеется слов, в которых встречаются все три цифры? Обозначим через множество всех слов, в которых не встречается цифра , . Тогда . Кроме того, . Наконец, . В множество входят слова, в которых отсутствует хотя бы одна цифра. По формуле(7) . По формуле обращения число слов, в которых присутствуют все три цифры, равно .
|