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

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

Пусть А ₁ и А ₂ – 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,

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.

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

. (3)

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

Пример 7.

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

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

Дата добавления: 2014-01-05