элементных подмножеств, т.е. Cnr . Определим количество подмножеств

первого типа, которые содержат выделенный элемент. Поскольку элемент уже выбран, то надо выбрать r-1 объект из n-1 элемента множества, т.е. всего

способов Cnr−−11 . Рассмотрим подмножества, которые не содержат выделенный

элемент. По-прежнему требуется выбрать r объектов, но теперь из n – 1 объектов, учитывая, что один элемент не может быть выбран. Таким образом,

существуют Cnr−1 способов сделать такой выбор. Складывая количество способов выбора в обоих случаях, получаем Cnr =Cnr−−11 + Cnr−1 .

Заметим, что доказать эту теорему можно также методом математической индукции.

□

Теорема Вандермонда. Пусть m,n,r – положительные целые числа такие, что r ≤ min(m,n). Тогда

r

Cmr +n = ∑Cmk Cnr−k k =0

Доказательство. Cmr +n – это число способов выбрать r предметов из m+n

предметов. Предметы можно выбирать в два приема: сначала выбрать k предметов из первых m предметов, а затем выбрать недостающие r-k

предметов из оставшихся n предметов. Всего для этого существует Cmk Cnr−k способов. Отсюда общее число способов выбрать r предметов составляет

6.4 Принцип включений – исключений.

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

A1 U A2 U A3 = A1 + A2 + A3 − A1 I A2 − A1 I A3 − A2 I A3 + A1 I A2 I A3

Переходя к n (n>2) множествам A1,A2,…,An с использованием индуктивных соображений можно получить формулу

21

которая в словесной формулировке выглядит так:

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

Для доказательства формулы (2) необходимо показать, что в правой части каждый элемент множества A1 U A2 U... U An подсчитан и учтен ровно

один раз. Предположим, что элемент а принадлежит в точности р

множества, содержащие элемент а. Существуют Cp2 способов выбрать такие

учтен C3p раз. В сумме элементов всех возможных пересечений r множеств, где r ≤ p , элемент a учтен Cpr раз. Следовательно, в правой части формулы

(2) элемент а учтен p −Cp2 + C3p −... + (−1)i+1 Cip +... + (−1)p+1 раз. Но

1 −C1p + Cp2 −C3p −... + (−1)i Cip +... + (−1)p Cpp = (1 −1)p = 0

Поэтому

1 =C1p −Cp2 + C3p −... + (−1)i+1 Cip +... + (−1)p+1

и получаем, что элемент a учтен в точности один раз.

□

На основании этой теоремы докажем утверждение, известное как

Теорема о включении – исключении. Пусть А1,А2,А3,...,Аn — набор

конечных множеств. Количество элементов множества A1 I A2 I... I An определяется формулой

22

Доказательство. Из теории множеств известно, что

A1 I A2 I ... I An = A1 U A2 U ... U An = U \ (A1 U A2 U ... U A )

Это легко видеть, например, из диаграммы Эйлера

так что имеем соотношение

формуле (2), получаем требуемый результат.

□

Название этой теоремы подчеркивает использование последовательных включений и исключений элементов подмножеств. Формулы (2) или (3) называются формулами включения – исключения, а метод решения комбинаторных задач с их использованием называется методом включения – исключения. Этот метод обобщает правило суммы, которое было рассмотрено нами вначале темы «комбинаторика»

Пример. Рассмотрим слова длины n в алфавите {0,1,2}. Сколько имеется слов, в которых встречаются все три цифры?

Обозначим Ai множество всех слов длины n, в которых не встречается

Следовательно, число слов, в которых присутствуют все три цифры, равно

3n −3 (2n −1).

□

Иногда удобно формулу из теоремы включений и исключений трактовать в другом виде. Пусть подмножество Хi определяется наличием некоторого

23

одним из свойств Рi,i=1,2,…,m, имеем формулу

Пример. Сколько натуральных чисел из первых 100 не делятся одновременно на 2, 3 и 5? Обозначим число натуральных чисел из первых

Теперь, применяя формулу включений и исключений, получим

□

Пример. В группе 23 студента. Из них 18 знают английский язык, 9 — немецкий и 6 — оба языка. Сколько студентов в группе не знают ни одного языка? Сколько студентов знают только один язык?

Решение. Пусть S— множество всех студентов, |S| = 23. Назначим свойства элементам s S : Р1 — знание английского языка, Р2 — знание немецкого языка. N(0) — количество студентов, не знающих языков (не обладают свойствами), N(1) — количество студентов, знающих только один язык.

Тогда N (0)= 23 − N (P1 )− N (P2 )+ N (P1 P2 )= 23 −18 −9 + 6 = 2

N (1)= (N (P1 )− N (P1 P2 ))+ (N (P2 )− N (P1 P2 ))=18 − 6 + 9 − 6 =15

□

Пример (задача о беспорядках). Перестановка a1a2…an чисел 1,2,…,n называется беспорядком, если ai ≠ i для всех i = 1, 2, …, n. Таким образом,

беспорядок – это перестановка, в которой ни один элемент не занимает «своего» места. Задача о беспорядках состоит в том, чтобы подсчитать число Dn перестановок – беспорядков. Например, D2=1 – два числа {1,2} образуют только один беспорядок (2,1). D3=2, поскольку беспорядками из трех чисел

24