Лекция № 4.

Тема: Основные правила комбинаторики

Основные вопросы, рассматриваемые на лекции:

1. Главные задачи комбинаторики.

2. Правило суммы и правило произведения.

3. Формула включений и исключений для двух множеств.

4. Формула включений и исключений трех множеств.

Краткое содержание лекционного материала

1. Главные задачи комбинаторики. Термин «комбинаторика» был введен Лейбницем («Рассуждения о комбинаторном искусстве», 1666 год).

a) Перечислительной задача. найти число комбинаторных конфигураций с заданными свойствами.

b) Существует ли комбинаторная конфигурация с (очень сложными) заданными свойствами?

c) Алгоритмическая задача. Найти метод генерации комбинаторных конфигураций с заданными свойствами.

d) Оптимизационная задача. Найти комбинаторную конфигурацию с экстремальным значением некоторого параметра.

2. Правило суммы и правило произведения. В теории множеств доказываются следующие правила о числе элементов множеств:

(I) Правило суммы. .

(II) Правило произведения. .

Правило суммы может быть обобщено: если множества попарно не пересекаются, то

.

Правило произведения может быть обобщено:

.

Замечание. Операции объединения, пересечения и декартового произведения двух множеств могут быть обобщены на множеств , , …, .

Объединение множеств , , …, содержит те, и только те, элементы, которые принадлежат хотя бы одному из множеств A1,…,An:

.

Пересечение множеств , , …, содержит те, и только те, элементы, которые принадлежат одновременно каждому из множеств A1,…,An:

.

Декартово произведение n множеств , , содержит последовательности из n элементов, i-й элемент которой принадлежит множеству :

.

Формулировка правила суммы на языке комбинаторики:

(I) Если объект можно выбрать способами и объект можно выбрать способами, причем, ни один из выборов не совпадает ни с каким выбором , то выбор «или » можно осуществить способами.

Формулировка правила произведения на языке комбинаторики:

(II) Если объект X можно выбрать m способами и объект Y можно выбрать способами, то упорядоченную пару (X,Y) можно выбрать mn способами.

Сформулируем правила суммы и произведения в самом общем виде.

Предположим, что смысл выбора объекта Y в том, чтобы выбрать объекты X1, X2, …, Xk соответственно n1, n2, …, nk способами.

(Обобщенное) правило суммы на языке комбинаторики: если для любых i,jÎ{1,2,…,k}, i¹j, ни один из выборов i не совпадает ни с каким выбором j, то объект Y можно выбрать n1+n2+…+nk способами.

(Обобщенное) правило произведения на языке комбинаторики: если для любых iÎ{1,2,…,k} объект Xi выбирается способами, независимыми от выбора объектов X1, …, Xi-1, Xi+1, …, Xk, то объект Y можно выбрать n1n2…nk способами.

3. Формула включений и исключений для двух множеств. По правилу суммы можно найти число элементов объединения двух непересекающихся множеств. Найти число элементов объединения двух пересекающихся множеств можно по формуле, сформулированной в следующей теореме.

Теорема 1. |AÈB|=|A|+|B|-|AÇB|.

Доказательство. Так как множества AB и B, а также AB и AÇB не пересекаются, (AB)ÈB=AÈB, (AB)È(AÇB)=A, то по правилу суммы

|AÈB|=|AB|+|B|,

|A|=|AB|+|AÇB|.

Из первого равенства по частям вычтем второе, получим

|AÈB|-|A|=|B|-|AÇB|.

Задача 1. В группе 25 студентов. Из них 16 учат английский, 12 – немецкий, 5 – английский и немецкий. Сколько человек в группе освобождены от изучения английского и немецкого языков?

Решение. Пусть A и B – множества студентов, изучающих соответственно английский и немецкий. Тогда AÇB – множество студентов, изучающих оба языка, AÈB – множество человек в группе, изучающих хотя бы один из двух языков. В силу теоремы 1, |AÈB|=|A|+|B|-|AÇB|=16+12-5=23. Число студентов, освобожденных от изучения языков: 25-23=2.

4. Формула включений и исключений для трех множеств. Метод включений и исключений при подсчете числа элементов объединения трех множеств заключается в следующем: 1) подсчитываем элементы всех трех множеств без различения элементов; 2) вычитываем число элементов, повторяющихся в каких-либо двух списках; 3) прибавляем число элементов, которые повторяются в трех множествах, поскольку они два раза вычитывались.

Теорема 2. |AÈBÈC|=|A|+|B|+|C|-|AÇB|-|AÇC|-|BÇC|+|AÇBÇC|.

Доказательство. Так как AÈBÈC=(AÈB)ÈC, то, в силу теоремы 1,

|AÈBÈC|=|AÈB|+|C|-|(AÈB)ÇC|.

Используем свойство дистрибутивности пересечения относительно объединения: (AÈB)ÇC=(AÇC)È(BÇC). И ещё раз применим теорему 1:

|(AÇC)È(BÇC)|=|AÇC|+|BÇC|-|(AÇC)Ç(BÇC)|.

По свойствам пересечения, (AÇC)Ç(BÇC)=AÇBÇC.

Задача 2. Найти число натуральных чисел, не превосходящих 1000 и не делящихся на 3, 5 и 7.

Решение. Пусть A, B и C – множества чисел, не превосходящих 1000 и кратных 3, 5 и 7 соответственно. Тогда AÇB, AÇC, BÇC и AÇBÇC – множества чисел, не превосходящих 1000 и кратных 15, 21, 35 и 105 соответственно. Напомним обозначение: [a] – целая часть числа a. Вычислим:

|A|=[1000/3]=333, |B|=[1000/5]=200, |C|=[1000/5]=142,

|AÇB|=[1000/15]=66, |AÇC|=[1000/21]=47, |BÇC|=[1000/35]=28,

|AÇBÇC|=[1000/105]=9.

Далее, AÈBÈC – множество чисел, не превосходящих 1000 и кратных хотя бы одному из чисел 3, 5 и 7. По теореме 2,

|AÈBÈC|=333+200+142-66-47-28+9=543.

Значит, число натуральных чисел, не превосходящих 1000 и не делящихся ни на одно из чисел 3, 5 и 7, равно 1000-543=457.

В теоремах 1 и 2 доказаны формулы включений и исключений соответственно для двух и трех множеств.

Сформулируем формулу включений и исключений для n множеств:

|A1È…ÈAn|=|A1|+…+|An|-|A1ÇA2|-|A1ÇA3|-…-|An-1ÇAn|+

+|A1ÇA2ÇA3|+|A1ÇA2ÇA4|+…+|An-2ÇAn-1ÇAn|+…

…+(-1)n-1|A1ÇA2Ç…ÇAn-1ÇAn|.