Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Лекция № 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 можно выбрать n1n2nk способами.



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

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

Доказательство. Так как множества AB и B, а также AB и AÇB не пересекаются, (ABB=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ÈBC, то, в силу теоремы 1,

|AÈBÈC|=|AÈB|+|C|-|(AÈBC|.

Используем свойство дистрибутивности пересечения относительно объединения: (AÈBC=(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|.





Дата добавления: 2014-01-03; Просмотров: 159; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.005 сек.