X-PDF

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

Поделиться статьей

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

Пусть А 1 и А 2 – 2 конечных множества. Тогда если А 1Ç А 2=Æ, то . Пусть теперь А 1Ç А 2¹Æ, тогда в каждый элемент из А 1Ç А 2 будет учтен дважды. Поэтому . Последнюю формулу можно обобщить на случай произвольного числа множеств:

. (2)

Равенство (2) называется формулой включений и исключений. В частности, для трех множеств эта формула имеет вид:

.

Доказывается формула (1) методом математической индукции.

Пример 6.

Сколько существует натуральных чисел, меньших 1000, которые не делятся ни на 3, ни на 5, ни на 7?

Всего чисел, меньших тысячи, 999. Из них 999_3=333 делятся на 3,

999:5=199 (ост. 4) делятся на 5,

999:7=142 (ост. 5) делятся на 7,

999:(3х5)=66 (ост. 9) делятся на 3 и на 5,

999:(3х7)=47 (ост. 12) делятся на 3 и на 7,

Представленная информация была полезной?
ДА
61.15%
НЕТ
38.85%
Проголосовало: 1449

999:(5х7)=28 (ост. 10) делятся на 5 и на 7,

999:(3х5х7)=9 (ост. 45) делятся на 3, на 5 и на 7.

В итоге искомых чисел 999-(333+199+142-66-47-28+9)=457.

Следствие. Пусть А – конечное множество, А 1, …, Аn – его подмножества. Тогда

. (3)

Доказательство. Поскольку , а Æ, то . Следовательно, . Применив для правой части последнего равенства формулу включений и исключений, получим искомый результат.

Пример 7.

Дано множество А ={0, 1, …, 10} и 3 его подмножества:
А 1={ a | a – четное}, А 2={ a | a &gt .6}, А 3={ a | 2&lt . a &lt .8}. Сколько элементов множества А не принадлежат ни одному из этих подмножеств?

тогда по формуле (3) . Очевидно, что таким элементом является 1.


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
61.15%
НЕТ
38.85%
Проголосовало: 1449

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ЯТТС-Рекомендации по написанию отчета по учебной и производственной практики-Гостинечное дело

Поделиться статьей

Поделиться статьейПоделиться статьей Автор статьи Анастасия Задать вопрос Эксперт Представленная информация была полезной? ДА 61.15% НЕТ 38.85% Проголосовало: 1449


Поделиться статьей

ЮУрГУ-вопросы

Поделиться статьей

Поделиться статьейПоделиться статьей Автор статьи Анастасия Задать вопрос Эксперт Представленная информация была полезной? ДА 61.15% НЕТ 38.85% Проголосовало: 1449


Поделиться статьей

ЮУГУ-Отчет_ПП-Машины непрерывного транспорта

Поделиться статьей

Поделиться статьейПоделиться статьей Автор статьи Анастасия Задать вопрос Эксперт Представленная информация была полезной? ДА 61.15% НЕТ 38.85% Проголосовало: 1449


Поделиться статьей

ЮУГУ- Курсовой проект по электронике

Поделиться статьей

Поделиться статьейПоделиться статьей Автор статьи Анастасия Задать вопрос Эксперт Представленная информация была полезной? ДА 61.15% НЕТ 38.85% Проголосовало: 1449


Поделиться статьей

ЮУГУ-ВКР-Обеспечение требований охраны труда на рабочем месте слесаря-ремонтника 5 разряда

Поделиться статьей

Поделиться статьейПоделиться статьей Автор статьи Анастасия Задать вопрос Эксперт Представленная информация была полезной? ДА 61.15% НЕТ 38.85% Проголосовало: 1449


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет