Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Общая постановка задачи
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Комбинаторика для начинающих
737 оценки
Из урока
Формула включений и исключений
Как отпраздновать новый год, нарисовать картину Ван Гога, посетить все города России и составить правильный отчёт в школе - в 6-й неделе курса. Формально, мы познакомимся с формулой включений и исключений - очень полезным комбинаторным инструментом. В частности, мы выведем новое тождество и получим формулу для нахождения числа беспорядков.
Познакомьтесь с преподавателями
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Значит, давайте так, общая постановка задачи.
Общая постановка задачи.
Ну вот в той форме, в которой я ее здесь рассказывал,
она ставится следующим образом.
Имеется в нашем распоряжении N, N объектов.
Ну, например, 30 человек в аудитории.
То есть N вот в том примере, который мы только что рассмотрели, это 30.
Вот имеется просто какой-то набор абстрактный из N объектов.
Так.
И есть перечень свойств, которые мы проверяем относительно этих объектов.
То есть смотрим, обладает ли данный объект тем или иным свойством из данного перечня.
Это вот знание языков в нашем примере.
Давайте свойство обозначим α1, ..., αn.
Значит, n в том примере равнялось 3, потому что у нас было 3 языка.
α1 — это, соответственно, А.
α2 — это, соответственно, F.
α3 — это N.
Вот.
Давайте введем следующее обозначение: N(α1)
— это количество объектов
среди наших a1,
..., aN — ну, то есть,
вспоминайте количество людей в аудитории — которые заведомо обладают свойством α1.
Вспоминайте, знают английский язык.
Которые точно обладают свойством α1.
Обладают свойством α1.
Еще раз и еще раз подчеркиваю — я ни в коем случае в этом месте не требую,
чтобы они обладали только свойством α1.
Единственно мое требование — чтобы они этим свойством заведомо обладали.
Но может быть они при этом обладают и какими-то другими из перечисленных
свойств.
Вот в точности как это было в примере про английский язык.
Английский знают, но среди них есть и те, кто знают также и французский, и немецкий,
и китайский, и чего хотите.
Вот.
Давайте аналогично определим N(α2),
..., N(αn).
То есть вот это вот количество объектов среди наших N,
которые точно обладают свойством α2 и, возможно, еще какими-то.
И вот это вот — это количество объектов,
которые точно обладают свойством αn и опять же, возможно, еще какими-то.
Ну вот в примере это были условные «немцы» — товарищи,
которые знали немецкий язык и, возможно, английский и французский тоже.
Так, ну, аналогично можно определить величины
типа N(α1, α2).
N(α1, α3), …,
N(αn − 1, αn).
Ну что здесь имеется в виду?
Имеется в виду, что теперь мы берем два свойства произвольных из нашего множества,
в котором всего n элементов.
И для каждой такой вот пары свойств...
Но пары, естественно, неупорядоченные — то есть количество обозначений,
которые вводятся в этом месте, это просто C из n по 2.
C из n по 2.
Множество всех возможных пар свойств.
И вот для каждой такой пары свойств...
Ну, вспоминайте, английский/французский, английский/немецкий, немецкий/французский.
Вот как раз C из 3 по 2 — это 3.
Для каждой такой пары свойств мы смотрим на количество объектов,
которые одновременно обладают и вот этим свойством,
и вот этим свойством, но, возможно, опять же, еще какими-то.
То есть английский и французский знают,
но при этом им не возбраняется знать и немецкий тоже.
Вот. Ну и так далее.
Дальше можно точно так же ввести N(α1, α2, α3), ...,
N(αn − 2, αn − 1, αn).
Таких будет C из n по 3 штук.
И так далее.
Вплоть до величины N(α1, ..., αn).
Это вот та величина, которую в примере мы
с вами называли «количеством полиглотов» в нашей аудитории.
То есть количеством людей, которые всеми возможными языками владели.
Ну вот у нас их было 3, а в общем случае тут какие-то n свойств.
И объекты, которые обладают всеми-всеми перечисленными свойствами — это такие
суперобъекты очень хорошие — их мы обозначаем количество N(α1, ..., αn).
И задача, которую мы хотим решать в
общем случае — это задача отыскания следующей величины.
Тоже N, но в скобочках давайте напишем вот так: (α1', ..., αn').
Подразумевая под вот этим штришком,
который я здесь нарисовал, отрицание свойства.
То есть α1' — это свойство,
состоящее в том, что объект не обладает свойством α1.
α1' — это значит, что свойством α1 объект не обладает, не знает английского языка.
αn' — что объект не обладает свойством αn, не знает немецкого языка.
То есть вот это количество абсолютных неучей, товарищей, объектов,
которые не обладают ни одним из интересующих нас свойств.
Не могут ни бутылку водки выпить на дереве, ни английский не знают,
ни французский, ничего вообще.
Вот. И чтобы вычислить эту величину,
нужно применить формулу,
которая полностью аналогична только что обсужденной в примере.
Давайте это назовем «теоремой».
Эта буковка Т — это просто от слова «теорема».
И теорема, собственно, именуется формулой включения-исключения,
которую я сейчас напишу.
Значит, если мы желаем посчитать общее количество объектов, которые не обладают
ни одним из интересующих нас свойств, то мы должны сначала посчитать их все.
Их у нас N, сравнивайте с 30.
Потом из этого N исключить всех тех товарищей,
которые обладают одним из перечисленных свойств.
То есть сначала исключить тех, кто обладает свойством α1 и, возможно,
еще какими-то.
Потом исключить тех, кто обладает свойством α2 и так далее.
В конце исключить тех, конечно, кто обладает свойством αn.
Но при этом когда мы исключали, мы исключали лишний раз.
Значит, понятно, мы исключили тех, кто знает, обладает, вернее,
свойством α1 и тех, кто обладает свойством α2 и вот здесь, и вот здесь.
Давайте компенсировать, то есть включать.
Включаем N(α1, α2), ...,
N(αn − 1, αn).
Сравнивайте с формулой для английского и немецкого.
Дальше исключаем всевозможные потройные пересечения,
то есть все возможные тройки свойств смотрим,
которые здесь лишний раз были включены.
Будет N(α1, α2, α3) +...
+ N(αn − 2,
αn − 1, αn) −...
То есть дальше мы исключаем, наоборот,
четверки, исключаем пятерки, исключаем шестерки и так далее.
Ну, естественно, в предположении, что n как минимум 6,
потому что откуда возьмется 6, если n — это, скажем, 3.
Если n — это 3, то мы вот здесь вот остановимся на этом шаге.
И, соответственно, главное понять, какой будет последний знак.
Вот в нашем примере про английский, немецкий и французский,
последний знак был именно минус.
На последнем шаге мы исключали полиглотов.
Но представьте себе, что у нас было бы четыре языка.
Не английский, немецкий и французский, а, скажем, английский,
немецкий, французский, китайский.
И в этом случае мы исключили бы товарищей,
которые пересекаются по трем языкам, знают одновременно три языка,
но в конце включили бы тех, кто знает все четыре.
Смотрите, значит, если у нас три свойства, то последний знак — это минус.
Мы исключаем.
Но если у нас свойств четыре, то последний знак — плюс.
Если свойств пять — то последний знак снова минус и так далее.
Ну понятно, то есть, если свойств нечетное количество, то последний знак — минус,
а если свойств четное количество, то последний знак — плюс.
Соответственно, надо написать вот так: прибавить (−1) в n-й степени...
Видите, если n — нечетное, то как раз получится минус, а если n — четное,
то как раз получится плюс.
И вот это умножается на количество так называемых условных полиглотов — тех,
кто обладает сразу всеми возможными знаниями.
Среди тех, которые нас интересуют, конечно.
Вот это называется «формулой включений-исключений», такое выражение.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
