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

Пусть X – некоторое n-множество, а p1, p2, …, pk – свойства, которыми могут обладать элементы множества X. Каждый элемент множества X может обладать одним или несколькими свойствами из числа перечисленных или не обладать ни одним из них. Обозначим через ni число элементов со свойством pi,

i = 1, 2,…, k. Вообще, пусть

1 2 r

ni i ...i

– число элементов со

свойствами p ,

p , …,

p . Тогда число элементов n , не

обладающих ни одним из перечисленных свойств, задается

следующей формулой:

n0 = n –

∑ni +

∑ni i +…

1 2

i i1 i2

…+(–1)r ∑ni i

i +…+(–1)nn12…n. (18)

1 2 K r

i1 i2 Kir

Элемент a, не обладающий ни одним свойством,

учитывается один раз в слагаемом n и ни одно другое слагаемое вклад не вносит. Элемент a, обладающий ровно одним

свойством j, учитывается по одному разу в слагаемых n и

∑ni ;

его вклад в правую часть (18) составляет 1 – 1=0. Рассмотрим теперь элемент a, обладающий s ≥ 1 свойствами j1,…, js.

1 2

Элемент a дает вклад 1 в каждое слагаемое ∑ni i i1 i2 Kir

Kir

такое,

что {i1,…, ir} ⊂ {j1,…, js}. Для каждого фиксированного r ≤ s

число таких слагаемых равно числу r-подмножеств s-множества

{j1,…, js}, т. е. числу сочетаний

С r . Следовательно, вклад

элемента a в правую часть (18) равен

1 – С1+ С2 +…+(–1)r Сr +…+(–1)s Сs =(1 – 1)s = 0.

s s s s

Таким образом, правая часть (18) учитывает каждый элемент, не обладающий ни одним из указанных свойств ровно один раз, а каждый элемент, обладающий хотя бы одним свойством, – ноль раз. Но это и означает, что правая и левая части (18) равны.

В качестве применения метода включения и исключения рассмотрим известную задачу о беспорядках.

Перестановка a1a2…an чисел 1, 2, …, n называется беспорядком, если ai ≠ i для всех i = 1, 2, …, n. Таким образом, беспорядок – это перестановка, в которой ни один элемент не занимает «своего» места. Обозначим число беспорядков через Dn.

Пример.Перечислим беспорядки из четырех элементов:

2143; 2341; 2413; 3142; 3412; 3421; 4123; 4312; 4321.

Значит, D4 = 9.

На множестве всех перестановок из элементов 1, 2, …, n определим набор свойств pi, i = 1, 2, …, n. Перестановка a1a2…an обладает свойством pi, если ai = i. Тогда число беспорядков – это число перестановок, не обладающих ни одним из указанных свойств. Число перестановок, оставляющих

на месте ровно r фиксированных символов (например, 1, 2,…, r)