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

⇐ Предыдущая 30 31 32 33 343536 37 38 39 Следующая ⇒

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

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

1 2 r

ni i... i

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

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

p, …,

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

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

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

n 0 = n –

∑ ni +

∑ ni i +…

1 2

i i 1  i 2

…+(–1)r ∑ ni i

i +…+(–1) nn 12… n. (18)

1 2 K r

i 1  i 2 K ir

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

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

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

∑ ni;

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

1 2

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

K ir

такое,

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

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

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

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

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

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

s s s s

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

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

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

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

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

Значит, D 4 = 9.

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

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