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

Чтобы найти мощность объединения двух множеств нужно из суммы их мощностей вычесть мощность их пересечения. При этом каждый элемент объединения будет посчитан ровно один раз.

.

Аналогичная формула имеет место для трех множеств.

Она справедлива и в общем случае

Докажем эту формулу, называемую формулой включения и исключения. Пусть элемент x входит ровно в k подмножеств . Вклад, который дает этот элемент в правую часть, равен

,

как это следует из тождества 4 для биномиальных коэффициентов (п. 1.2.). Поэтому в правой части будет полное число элементов, что и доказывает формулу.

В практических задачах часто имеется некоторое множество U и система его подмножеств U₁,…,U_m. Требуется найти число элементов множества U, не принадлежащих ни одному из множеств U₁,…,U_m. В этом случае формула включения и исключения выглядит следующим образом

.

Рассмотрим пример. В группе, состоящей из 20 человек, 6 знают немецкий, 7 – французский и 8 – английский язык, 3 человека знают немецкий и французский, 4 – немецкий и английский, 5 – французский и английский и один человек знает все 3 языка. Сколько человек не знают ни одного иностранного языка?

Решение: 20-(6+7+8)+(3+4+5)-1=10.

Другой пример. Пусть требуется найти число целочисленных решений системы

Введем новые переменные , , . Система перепишется в виде

Пусть U – множество решений системы

U₁ – множество решений системы

U₂ – множество решений системы

U₃ – множество решений системы

согласно п. 1.1.

Чтобы найти мощность множества U₁, достаточно в соответствующей системе сделать замену . Это дает

Аналогично, ,

Далее, легко видеть, что

, ,

Поэтому в соответствии с формулой включения и исключения число решений исходной системы равно

В качестве ещё одного примера рассмотрим известную задачу о беспорядках. Требуется найти число перестановок чисел 1,2,…,n, в которых никакое число i не стоит на i – ом месте. Всего перестановок . Перестановок, в которых число i стоит на i – ом месте, Перестановок, в которых два различных числа i и j стоят на своих местах, и т.д. По формуле включения и исключения имеем

Отметим, что выражение в скобках с ростом стремится к .

Тест.

1. В группе 25 студентов. Среди них 20 сдали сессию успешно, 12 занимаются в спортивных секциях, причем 10 из них сдали сессии успешно. Сколько неуспевающих студентов не посещают спортивных секций а) 3; б) 5; в) 10.

2. Сколько натуральных чисел, не превосходящих 1000, не делятся ни на одно из чисел 3,5,7? а) 455; б) 457; в) 459.

3. Сколько натуральных чисел, не превосходящих 1000, не делятся ни на одно из чисел 6,10,15? а) 730; б) 732; в) 734.

4. Сколькими способами можно раздать 12 одинаковых монет 5 нищим так, чтобы каждый получил не менее одной, но не более 3 монет? а) 10; б) 20; в) 30.

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