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

По правилу суммы, мощность объединения двух не пересекающихся множеств равна сумме их мощностей. В общем же случае, когда множества A и B могут пересекаться, в сумме Метод включений и исключений - student2.ru некоторые элементы из множества Метод включений и исключений - student2.ru сосчитаны дважды. Это те элементы, которые принадлежат пересечению Метод включений и исключений - student2.ru . Следовательно, мощность объединения двух конечных множеств можно найти по формуле:

Метод включений и исключений - student2.ru .

Использованный здесь прием подсчета можно применить и для определения количества элементов в объединении любого числа множеств. Его называют методом включений и исключений. Докажем формулу включений и исключений в общем случае.

Теорема 10. Для любых конечных множеств Метод включений и исключений - student2.ru имеет место равенство

Метод включений и исключений - student2.ru , (1)

где Метод включений и исключений - student2.ru .

Д о к а з а т е л ь с т в о. Рассмотрим произвольный элемент Метод включений и исключений - student2.ru и определим вклад, который он вносит в правую часть формулы (1). Допустим, что x входит точно в m из множеств Метод включений и исключений - student2.ru . Так как Метод включений и исключений - student2.ru – это сумма мощностей этих множеств, то элемент x в Метод включений и исключений - student2.ru сосчитан m раз. Далее, Метод включений и исключений - student2.ru – сумма мощностей попарных пересечений множеств Метод включений и исключений - student2.ru . Значит, x будет в этой сумме сосчитан столько раз, сколько существует пар множеств Метод включений и исключений - student2.ru таких, что Метод включений и исключений - student2.ru . Но x принадлежит точно m множествам, значит, таких пар будет Метод включений и исключений - student2.ru . Рассуждая и дальше в том же духе, приходим к выводу, что для любого Метод включений и исключений - student2.ru элемент x в сумме Метод включений и исключений - student2.ru учтен Метод включений и исключений - student2.ru раз. Значит, общий вклад элемента x в правую часть формулы (1) равен Метод включений и исключений - student2.ru . Из свойства 6° биномиальных коэффициентов следует, что эта сумма равна Метод включений и исключений - student2.ru . Значит, каждый элемент сосчитан точно один раз и правая часть (1) равна числу элементов, т.е. мощности объединения множеств Метод включений и исключений - student2.ru . 

В качестве примера применения метода включения и исключения рассмотрим задачу о беспорядках: сколько существует перестановок Метод включений и исключений - student2.ru чисел Метод включений и исключений - student2.ru таких, что Метод включений и исключений - student2.ru при любом Метод включений и исключений - student2.ru ?

Число искомых перестановок D является разностью между числом всех перестановок и числом перестановок, у которых хотя бы один символ стоит на своем месте. Обозначим множество перестановок, для которых Метод включений и исключений - student2.ru через Метод включений и исключений - student2.ru , тогда Метод включений и исключений - student2.ru . Мощность объединения множеств находим по формуле включения и исключения. Пересечение любых k множеств Метод включений и исключений - student2.ru Метод включений и исключений - student2.ru содержит все такие перестановки, у которых числа Метод включений и исключений - student2.ru стоят на своих местах. Поскольку остальные n-k чисел располагаются на оставшихся местах произвольно, число таких перестановок равно (n-k)!. Поэтому каждое слагаемое в сумме Метод включений и исключений - student2.ru равно Метод включений и исключений - student2.ru !. Число слагаемых равно числу способов выбрать k чисел из n, т.е. Метод включений и исключений - student2.ru . Следовательно, Метод включений и исключений - student2.ru .

Задачи

1.На одной из кафедр университета работают тринадцать человек, причем каждый из них знает хотя бы один иностранный язык. Десять человек знают английский, семеро - немецкий, шестеро - французский. Пятеро знают английский и немецкий, четверо - английский и французский, трое - немецкий и французский.

Сколько человек знают все три языка?

Сколько человек знают ровно два языка?

Сколько человек знают только английский язык?

2. В музыкальном ансамбле используется четыре инструмента, Для каждого инструмента в ансамбле имеется четыре человека, владеющих данным инструментом, для любых двух инструментов - три человека, играющих на них, для любых трех - два человека. Один человек владеет всеми четырьмя инструментами. Сколько человек в ансамбле?

6. Задачи для самостоятельной работы

1. Имеется Метод включений и исключений - student2.ru разных книг одного автора, Метод включений и исключений - student2.ru – второго и Метод включений и исключений - student2.ru – третьего. Каким числом способов можно выбрать

а) две книги одного автора?

б) три книги одного автора?

в) одну книгу первого автора, две – второго и три – третьего?

2.Каким числом способов можно на шахматной доске поместить черного и белого королей так, чтобы они не атаковали друг друга?

3. На одной из двух параллельных прямых зафиксировано n точек, а на другой - m точек. Сколько имеется

а) треугольников;

б) четырехугольников

с вершинами в данных точках?

4. Каким числом способов из 10 человек можно выбрать три комиссии, если в первой и во второй должно быть по 3 человека, а в третьей - 5 человек, и ни один из членов первой комиссии не должен входить во вторую и третью?

5. Траекторией назовем ломаную линию на плоскости, состоящую из отрезков, параллельных координатным осям, причем длины отрезков - целые числа, а при движении вдоль ломаной от начальной точки каждый вертикальный отрезок проходится снизу вверх, а горизонтальный - слева направо. Найдите число траекторий, начинающихся в точке (0,0), а оканчивающихся

а) в точке (m,n);

б) на прямой Метод включений и исключений - student2.ru .

6. Сколько диагоналей у выпуклого n-угольника? Найдите число точек пересечения этих диагоналей (не считая вершин), если известно, что в каждой из этих точек пересекаются только две диагонали?

7. Имеется колода из 4n карт четырех мастей, по n карт каждой масти, занумерованных числами 1,2,...,n. Каким числом способов можно выбрать пять карт так, чтобы среди них оказались :

а) пять карт одной масти с последовательными номерами;

б) четыре карты с одинаковыми номерами;

в) три карты с одним номером и две с другим;

г) пять карт одной масти;

д) пять карт с последовательными номерами;

е) три карты с одинаковыми номерами;

ж) две карты с одинаковыми, остальные с разными номерами.

8. Сколько имеется шестизначных десятичных чисел, у которых

а) есть одинаковые цифры?

б) цифры идут в возрастающем порядке?

в) ровно три цифры четные?

г) не менее двух четных цифр?

д) все цифры различны, причем первая - не 9, а последняя - не 0?

е) сумма цифр четна ?

9. Сколько существует отображений множества A в множество B, если ÷A÷=n, ÷B÷=m? Сколько среди них инъективных? Биективных?

10 Дано множество U из n элементов и в нем подмножество A из k элементов. Определите число подмножеств Метод включений и исключений - student2.ru , удовлетворяющих условию

а) Метод включений и исключений - student2.ru ; г) Метод включений и исключений - student2.ru ; ж) Метод включений и исключений - student2.ru ;

б) Метод включений и исключений - student2.ru ; д) Метод включений и исключений - student2.ru ; з) Метод включений и исключений - student2.ru ;

в) Метод включений и исключений - student2.ru ; е) Метод включений и исключений - student2.ru ; и) Метод включений и исключений - student2.ru .

11. В множестве U из n элементов, найдите число пар подмножеств (A,B) удовлетворяющих условиям:

а) Метод включений и исключений - student2.ru ; г) Метод включений и исключений - student2.ru , Метод включений и исключений - student2.ru ;

б) Метод включений и исключений - student2.ru ; д) Метод включений и исключений - student2.ru ;

в) Метод включений и исключений - student2.ru ; е) Метод включений и исключений - student2.ru , Метод включений и исключений - student2.ru , Метод включений и исключений - student2.ru .

12. Определите число матриц с m строками и n столбцами, составленных из элементов 0 и 1, у которых строки попарно различны.

13. Каким числом способов можно разложить p черных и q белых шаров по k различным ящикам?

14. Каким числом способов можно разместить n различных предметов по k различным ящикам? Сколько таких размещений, при которых в каждый ящик укладывается не более одного предмета?

15. Каким числом способов можно распределить n одинаковых монет между k лицами? Сколько таких способов, при которых каждый получает не менее одной монеты?

16. Каким числом способов можно kn различных предметов разложить по n одинаковым (неразличимым) ящикам так, чтобы в каждом ящике оказалось ровно k предметов?

17 Каким числом способов 7 человек могут разместиться в трех автомобилях, если в первом из них имеется 2 свободных места, во втором - 3, а в третьем - 4?

18. В следующих заданиях рассматриваются слова в алфавите Метод включений и исключений - student2.ru . Через Метод включений и исключений - student2.ru обозначается число вхождений буквы Метод включений и исключений - student2.ru в слово. Требуется подсчитать число слов длины n, удовлетворяющих данным условиям.

Вариант q n Условие  
1) n1 ?6
2) n1 =2n2
3) n1 + n2 < n3 + n4
4) n1 = n2 + n3 + n4
5) n1 = 2, n2<n3
6) n1 + n2 = 3, n3 ? 2
7) n1 = n2
8) n1 = n2 + n3, n2 - четное
9) n1 + n2 < n3
10) n1 + n2 = n3
11) n1 < n2
12) n1 + n2 ? 6
13) 2 < n1 < 6
14) n1 ? n2 ? n3
15) n1 ?2, n2 + n3 = 4
16) n1 = 4, n2 ?3
17) n1 ? n2 + n3 + n4
18) n1 + n2 = 3, n3 ?2
19) n1 > n2 > 2
20) n1 = n2
21) n1 + n2 = n3 + n4
22) n1 = 2, n2 ?3
23) n1 ?2, n2 + n3 + n4 = 3
24) n1 + n2 ?4, n3 = 1
25) n1 = n2 = n3

19. В группе N студентов, из них Метод включений и исключений - student2.ru человек владеют языком программирования СИ, Метод включений и исключений - student2.ru - Паскалем, Метод включений и исключений - student2.ru - Бейсиком, Метод включений и исключений - student2.ru студентов программируют на СИи Паскале, Метод включений и исключений - student2.ru - на СИ и Бейсике, Метод включений и исключений - student2.ru - на Паскале и Бейсике, Метод включений и исключений - student2.ru человек знают все три языка и Метод включений и исключений - student2.ru не знают ни одного из них. По данным значениям найти недостающую информацию (заполнить пустую клетку):

Вариант N Метод включений и исключений - student2.ru Метод включений и исключений - student2.ru Метод включений и исключений - student2.ru Метод включений и исключений - student2.ru Метод включений и исключений - student2.ru Метод включений и исключений - student2.ru Метод включений и исключений - student2.ru Метод включений и исключений - student2.ru  
1)  
2)  
3)  
4)  
5)  
6)  
7)  
8)  
9)  
10)  
11)  
12)  
13)  
14)  
15)  
16)  
17)  
18)  
19)  
20)  
21)  
22)  
23)  
24)  
25)  

Наши рекомендации