КАТЕГОРИИ: Архитектура-(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) Правило произведения. . Правило суммы может быть обобщено: если множества попарно не пересекаются, то . Правило произведения может быть обобщено: . Замечание. Операции объединения, пересечения и декартового произведения двух множеств могут быть обобщены на множеств , , …, . Объединение множеств , , …, содержит те, и только те, элементы, которые принадлежат хотя бы одному из множеств A 1,…, An: . Пересечение множеств , , …, содержит те, и только те, элементы, которые принадлежат одновременно каждому из множеств A 1,…, An: . Декартово произведение n множеств , , содержит последовательности из n элементов, i -й элемент которой принадлежит множеству : . Формулировка правила суммы на языке комбинаторики: (I) Если объект можно выбрать способами и объект можно выбрать способами, причем, ни один из выборов не совпадает ни с каким выбором , то выбор «или » можно осуществить способами. Формулировка правила произведения на языке комбинаторики: (II) Если объект X можно выбрать m способами и объект Y можно выбрать способами, то упорядоченную пару (X, Y) можно выбрать mn способами. Сформулируем правила суммы и произведения в самом общем виде. Предположим, что смысл выбора объекта Y в том, чтобы выбрать объекты X 1, X 2, …, Xk соответственно n 1, n 2, …, nk способами. (Обобщенное) правило суммы на языке комбинаторики: если для любых i, j Î{1,2,…, k }, i ¹ j, ни один из выборов i не совпадает ни с каким выбором j, то объект Y можно выбрать n 1+ n 2+…+ nk способами. (Обобщенное) правило произведения на языке комбинаторики: если для любых i Î{1,2,…, k } объект Xi выбирается способами, независимыми от выбора объектов X 1, …, Xi -1, Xi +1, …, Xk, то объект Y можно выбрать n 1 n 2… nk способами. 3. Формула включений и исключений для двух множеств. По правилу суммы можно найти число элементов объединения двух непересекающихся множеств. Найти число элементов объединения двух пересекающихся множеств можно по формуле, сформулированной в следующей теореме. Теорема 1. | A È B |=| A |+| B |-| A Ç B |. Доказательство. Так как множества A B и B, а также A B и A Ç B не пересекаются, (A B)È B = A È B, (A B)È(A Ç B)= A, то по правилу суммы | A È B |=| A B |+| B |, | A |=| A B |+| 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 множеств: | A 1È…È An |=| A 1|+…+| An |-| A 1Ç A 2|-| A 1Ç A 3|-…-| An -1Ç An |+ +| A 1Ç A 2Ç A 3|+| A 1Ç A 2Ç A 4|+…+| An -2Ç An -1Ç An |+… …+(-1) n -1| A 1Ç A 2Ç…Ç An -1Ç An |.
Дата добавления: 2014-01-03; Просмотров: 356; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |