Метод включения-исключения

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

Теорема. =

Доказательство.

1. Рассмотрим элемент обладающий ровно свойствами. Такой элемент войдет в только при и в сумме будетсчитаться единственный раз. Поэтому элементы, обладающиеровно свойствами, будут входить в сумму по одному разу.

2. Рассмотрим элемент обладающий ровно свойствами, .Тогда в они будут входить при а в они войдут раз. Тогда общее число вхождений такого элемента есть

Таким образом, из 1 и 2 следует требуемое свойство.

Пример 1. Подсчитать число перестановок, оставляющих на месте ровно элементов.

Решение. Вводим множество всех перестановок элементов . Вводим n свойств : -тый элемент при перестановке остается на месте. Тогда число перестановок, оставляющих на месте ровно эле­ментов, есть:

где N( ) — число перестановок, оставляющих на ме­сте -ый, -ой,…, -ый элементы, и это число есть очевидно, (n-k)!, а число слагаемых в сумме есть . Поэтому искомое число есть

Здесь

И при больших получим ассимтотическую формулу

Пример 2. Найти число чисел взаимно простых с данным . Обозначим это число через (так называемая функция Эйлера).

Решение. Введем множество натуральных чисел 1, 2,..., т и введем свойства , где означает, что число делится на про­стое число . Тогда числа взаимно простые с т есть числа, которые не обладают ни одним из свойств , т.е. обла­дают 0 свойствами, и поэтому искомое число есть

где есть число чисел, делящихсяна , и поэтому это числа, представленные в виде

где множитель h изменяется 1,2, Поэтому =

и тогда = =

Пример 3. Найти число способов раскладки m различных шаров по n различным урнам, при которых ровно урн пусты.

Решение. Введем множество различных раскладок m различных ша­ров по n различным урнам, т.е. упорядоченных наборов m эле­ментов из множества {1,2,..., n} n-элементов с возможными повторениями. Введем свойства раскладок . — i-ая урна пуста. Тогда искомое число есть — ровноурн пусты.

— число раскладок, при которых ая, ая, ая урны пусты и это число, как нетрудно видеть, есть .Поэтому

Упражнения.

1. Имеется колода карт четырех мастей по n карт каждой масти. Берут карт. Найти число комбинаций, в которых имеются все масти.

2. Бросают различных игральных кубиков.Найти число комбина­ций, когда имеются все цифры.

3. Найти число квадратных двоичных матриц размера n n, в каждой строке которых содержится хотя бы один ноль.

4. Найти число двоичных матриц размера n в строках, кото­рых содержатся все двоичные слова длины m.

5. Составляют n-значные числа из цифр 1,2,3,4. Найти число чисел, в

которых имеются все цифры.