Принцип включения и исключения

КОМБИНАТОРИКИ

Формулы и алгоритмы, рассмотренные в теме 1, дают способы вычисления комбинаторных чисел для некоторых распространенных конфигураций. Однако, практические задачи далеко не всегда непосредственно сводятся к ним. В этом случае чрезвычайно важно знание методов сведения одних конфигураций к другим, либо общих методов, не столь зависящих от конкретных комбинаторных структур. Рассмотрим наиболее популярные из таких методов.

 

1.1. Вывод формулы. Пусть имеем N объектов и некоторый набор свойств а₁, …, а_n, которыми могут обладать эти объекты. Обозначим N(i) – число объектов, обладающих свойством а_i, и вообще N(i₁, …, i_k) – число объектов, обладающих одновременно всеми свойствами . Пусть N(0) – число объектов, не обладающих ни одним из свойств а_i. Справедлива формула включения и исключения:

N(0) = N – + + …

+ (– 1)^k+ … + (–1)ⁿ N(1, 2, … , n). (3.1)

Символ 1 £ i₁ < i₂ <…< i_k £ n под знаком суммы означает, что суммирование ведется по всем комбинациям i₁, i₂,…, i_k так, чтобы выполнялось указанное соотношений. Доказательство проведем с помощью индукции по n – число свойств.

1⁰. n = 1. N(0) = N – N(1). Всего существует одно свойство. От общего числа объектов отнимем количество объектов, обладающих этим свойством – узнаем, сколько объектов этим свойством не обладают.

2⁰. Пусть для n – 1 свойств справедлива формула

N(0) = N – + + …

+ (– 1)^k+ … + (–1)ⁿ N(1, 2, … , n – 1). (3.2)

Пусть теперь имеем множество, все элементы которого обладают свойством а_n, и, возможно, обладают свойствами а₁, …, а_n–1. Очевидно, для этого множества формула (3.2) также верна и имеет вид:

N(0, n) = N(n) –+ … +

+(–1)^n–2+ (–1)^n–1N(1, 2, … , n – 1, n). (3.3)

В (3.3) везде в скобках дописано n, т.к. все элементы множества свойством а_n обладают. Вычтем (3.3) из (3.2):

N(0) – N(0, n) = N – + + … – (–1)^n–1 N(1, 2, … , n – 1, n).

Отсюда

N(0) – N(0, n) = N –++… + (–1)ⁿ N(1, 2,…,n).

Справа мы получили требуемую формулу. А что слева? N(0) – число элементов, не обладающих свойствами а₁, …, а_n–1, но, возможно, обладающих свойством а_n. N(0, n) – число элементов, не обладающих свойствами а₁, …, а_n–1, но обязательно обладающих свойством а_n. Следовательно, N(0) – N(0, n) – число элементов, не обладающих ни одним из свойств а₁, …, а_n, т.е. требуемая величина. Формула доказана.

Пример 3.1. Староста класса подал следующие сведения о классе. Всего в классе 45 учеников, из них 25 мальчиков. 30 человек учится без троек, из них – 16 мальчиков; 28 человек занимаются спортом, из них – 18 мальчиков и 17 хорошистов и отличников; 15 мальчиков учатся без троек и одновременно занимаются спортом. Классный руководитель внимательно посмотрел список и сказал, что в сведениях есть ошибка. Как он это узнал?

Решение. Обозначим a₁ – свойство принадлежности к мужскому полу; a₂ – хорошая успеваемость; a₃ – занятие спортом. Тогда N = 45, N(1) = 25, N(2) = 30, N(3) = 28, N(1, 2) = 16, N(1, 3) = 18, N(2, 3) = 17, N(1, 2, 3) = 15. Итого N(0) = 45 – 25 – 28 + 16 + 18 + 17 – 15 = – 2 – ошибка.

1.2. Модификации формулы включения и исключения

2.а. Формулу (2.1) можно обобщить для определения числа элементов, обладающих в точности k свойствами (0 £ k £ n):

N(k) = + …+ (– 1)^s–k+ …

+ (–1)^n–k ×N(1, 2, … , n). (3.4)

Пример 3.2. В отделе НИИ каждый сотрудник владеет хотя бы одним иностранным языком. Известно, что английским языком владеют 6 человек, немецким – 6, французским – 7, английским и немецким – 4, немецким и французским – 3, английским и французским – 2, все три языка знает 1 человек. Определить, сколько всего человек в отделе, сколько человек владеют только английским, только немецким, только французским, и сколько человек знает только 1 иностранный язык.

Решение. Согласно условиям задачи N(0) = 0, т.к. в отделе нет сотрудников, не владеющих иностранными языками. Следовательно, по формуле (3.1) получаем:

N = – + N(1, 2, 3) (3.5)

N = 6 + 6 + 7 – 4 – 3 – 2 + 1 = 11 человек всего в отделе.

Для вычисления остальных показателей также воспользуемся формулой (3.5). Найдем, например N(только А) – число человек, не владеющих никаким другим языком, кроме английского. Для этого формулу (3.5) надо применить только к множеству людей, владеющих английским языком. В этом случае n = 2. Тогда N = N(A), N(1) и N(2) – число людей, владеющих помимо английского еще немецким и французским, соответственно, N(1, 2) – число людей, владеющих помимо английского еще одновременно немецким и французским. Отсюда

N(только A) = N(A) – N(А и Н) – N(А и Ф) + N(А и Н и Ф) =

6 – 4 – 2 + 1 = 1.

Аналогично

N(только Н) = N(Н) – N(А и Н) – N(Н и Ф) + N(А и Н и Ф) =

6 – 4 – 3 + 1 = 0.

N(только Ф) = N(Ф) – N(Ф и А) – N(Ф и Н) + N(А и Н и Ф) =

7 –2 – 3 + 1 = 3.

Вычислим теперь N(1) – число людей, владеющих только 1 языком. Воспользуемся формулой (3.4) при k = 1.

N(1) = N(А) + N(Н) + N(Ф) + (–1)^2–1×× [N(А и Н) + N(Н и Ф) + N(А и Ф)] + (–1)^3–1×× N(А и Н и Ф) = 6 + 6 + 7 – 2×(4 + 3 + 2) + 3×1 = 4.

Такой же результат получим, если сложим N(только A) + N(только Н) + N(только Ф).

2.б. Формулу (3.1) можно также интерпретировать, как подсчет мощностей пересечений различных множеств, т.е. дать теоретико-множественное представление принципа включения и исключения. Пусть имеем некоторое конечное множество А и его подмножества А_j, j = 1,…, n. Тогда теоретико-множественный аналог формулы (3.1) будет иметь вид:

= |A| – + + …

+ (– 1)^k+ …+ (–1)ⁿ .