Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Доказательство индукционного перехода (*)
Loading...
Del curso dictado por Moscow Institute of Physics and Technology
Комбинаторика для начинающих
883 calificaciones
De la lección
Формула включений и исключений
Как отпраздновать новый год, нарисовать картину Ван Гога, посетить все города России и составить правильный отчёт в школе - в 6-й неделе курса. Формально, мы познакомимся с формулой включений и исключений - очень полезным комбинаторным инструментом. В частности, мы выведем новое тождество и получим формулу для нахождения числа беспорядков.
Conoce a los instructores
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Ну то есть, что, то же самое?
При n = k + 1 надо писать так: для любого N,
для любых свойств a₁ … не свойств, извините,
объектов, конечно… a₁, ..., aN и для любых свойств уже,
α₁, ..., αk + 1, для любых свойств в
количестве k + 1 теперь штука, справедлива формула включений-исключений.
Справедлива формула, давайте напишем и больше ничего писать здесь не будем.
Вот так вот нужно доказать.
Ну что ж?
Если нам нужно доказать что-то для любых N, для любых, для любых,
давайте зафиксируем произвольное N, произвольные объекты a₁, ..., aN,
произвольные свойства α₁, ..., αk + 1, и будем и с ними работать.
Зафиксировали, будем работать.
Ну давайте, вот у нас есть объекты а₁, ..., аN,
есть свойства α₁, ..., αk + 1.
Нас вообще-то интересует количество объектов,
которые не обладают ни одним из вот этих вот свойств в количестве k + 1 штука.
И для вот этого количества объектов нам нужно установить формулу
включений-исключений.
Так.
Но нам нужно применить то предположение,
которое мы уже считаем справедливым, мы уже знаем,
что для k-свойств и для меньшего числа свойств, формула верна.
Давайте попробуем сделать двумя способами вот это вот применение,
прибегнуть к нашему знанию, что вот для меньшего числа свойств всё в порядке.
Давайте сделаем два варианта этого применения.
Во-первых, давайте рассмотрим
только свойства α₁,
..., αk.
Вот просто возьмем и забудем, временно, конечно, то есть мы обязательно
потом вспомним про них, но временно забудем про свойство αk + 1.
Сейчас будем рассматривать только свойства α₁, ..., αk.
Ну, если ограничиться их рассмотрением, то, конечно, их уже k-штук,
мы можем прибегнуть к предположению индукции, вспомнить, что для них всё
верно и написать ту формулу, которую мы считаем, мы знаем, что она верна.
Вот эта формула: N (α₁,′ ..., αk′),
ну, это количество объектов среди вот этих наших N,
которые не обладают ни одним из k₁-свойств.
Про последнее, мы, временно, повторяю, забыли.
Вот, это выражается формулой, понятно какой: N − N (α₁) −...
− N (αk) + N (α₁
α₂) +...
+ N (αk − 1, αk) −...
+ (−1) в k-той степени N (α₁,
..., αk).
Вот так, да?
Ну это очевидно, это просто формула, которая заявлена в формулировке теоремы.
Наше предположение состояло в том,
что для любого набора, состоящего из k маленькое свойств, она справедлива.
Вот мы взяли какие-то k маленькое свойств, вот она справедлива.
Я просто это записал, ничего умного больше нету.
Давайте теперь вспомним всё-таки,
что у нас есть еще в распоряжении некое дополнительное свойство с номером k + 1,
и про него поговорим в рамках следующего пункта 2,
в котором мы тоже как-то прибегнем к нашему предварительному знанию.
Значит, давайте вот как сделаем – рассмотрим в
множестве объектов а₁,
..., aN, вот в этом множестве рассмотрим только те объекты…
только те объекты,
которые обладают свойством αk + 1.
Которые обладают
свойством αk + 1.
Ну, теоретически, это может быть даже пустое множество объектов, потому что
мало ли, вдруг мы такое свойство задали, которым ни один наш объект не обладает.
Вот, захотели, чтоб человек выпил бутылку водки на дереве,
в аудитории из ста человек ни одного такого героя не нашлось.
Всякое бывает.
Вот, ну неважно, выделим, тем не менее, из этого множества все те объекты,
в том числе может быть и никакие, которые обладают свойством αk + 1.
Давайте...
их, понятное дело, N (αk + 1) штук.
Ну, просто таково обозначение наше стандартное,
сколько всего есть объектов, которые, как минимум,
обладают вот этим свойством αk + 1, их, по определению, N (αk + 1).
Ну, давайте введем, временно, более короткое обозначение,
обозначим вот это вот буквой M.
Ну, давайте обозначим просто буквой M вот эту величину,
это количество тех объектов из наших, которые обладают свойством αk + 1.
Вот ну, при желании, их можно даже как-нибудь обозначить, но,
я думаю, что это необязательно.
Вот ну, какие-то M объектов.
Так.
Замечательно.
Смотрите, вот давайте я всё-таки подойду сюда и покажу еще раз наше предположение.
Здесь очень важно, в этом предположении,
что оно верно для любого количества объектов,
для любого количества объектов и совершенно для любого множества объектов.
Нам не важно, какое множество брать, и какова будет его мощность,
сколько объектов в этом множестве.
Вот это очень важно.
И свойства, в принципе, тоже могут быть какими угодно.
Вот давайте применим это предположение теперь не для N, как в пункте 1, а для M.
То есть, давайте применим предположение индукции,
предположение индукции
вот к этим M объектам.
Вот к этим M объектам.
Раз для любого верно, значит, например, и вот для такого количества тоже,
и для тех объектов, которые среди вот этих вот обладают указанным свойством,
которых, как мы знаем, M штук.
Вот для них тоже верно, к ним сейчас формулу включений-исключений и применим.
Осталось только сказать с какими свойствами.
А свойства возьмем те же самые, то есть мы применим предположение
индукции к этим M объектам и свойствам,
опять же, α₁, ..., αk,
то есть снова количество свойств – это k.
Но, вот в этом месте мы добавили еще где-то неявно присутствие свойства αk + 1.
А здесь мы работаем снова с k-свойствами, с ними мы умеем работать,
наше предположение для них уже выполнено,
мы его уже успели доказать на предыдущих шагах вот этой рекурсии, индукции.
Ну, что значит «применим»?
А вот так напишем: M (α₁′, ..., αk′).
Я надеюсь, такое обозначение никого не смущает,
что значит M от каких-то там свойств?
Что значит M от каких-то свойств?
Ну, это опять количество тех объектов среди вот этих вот наших,
которых теперь M штука, а не N, как раньше,
которые не обладают ни одним из свойств α₁, ..., αk.
Просто вот количество таких объектов, вот так вот удобно обозначить.
Естественно, формула включений-исключений говорит, что надо взять количество этих
объектов, вычесть из них количество тех,
которые обладают α₁ и так далее, количество тех, которые обладают αk,
компенсировать это путем включения (α₁ α₂) ...,
M (αk − 1, αk) −...
+ (−1) в k-той степени, просто в точности такая же формула, с заменой N на M.
Я специально ввел это обозначение, чтоб просто легче воспринималось.
Вот. Ну, а здесь будет, соответственно,
M (α₁, ..., αk).
Ну, это просто в точности то, что мы предполагаем выполненным,
и мы имеем право это предполагать, потому, что у нас была база индукции.
Вот тот самый первый пункт, с которого мы начали доказательство теоремы.
А теперь давайте попробуем всё-таки вот эту замечательную формулу,
которая у нас получилась, переписать в изначальных терминах,
то есть в обозначениях, в которых не будет M, а будет только N.
Как бы её переписать в таких терминах?
Ну, очень просто, например, вот это M – это в точности N (αk + 1).
Давайте подумаем, а что такое M (α₁)?
По сути?
Ну, это количество объектов среди вот этих вот, которые обладают свойством α₁,
но сами эти объекты, внимание, это ведь объекты,
которые по определению обладают свойством αk + 1, выбранные вот из
этого множества и по определению обладают, как минимум, свойством αk + 1.
Если мы из них, в свою очередь, выбираем тех товарищей, которые обладают свойством
α1 — ведь мы в итоге получаем ровно те объекты из исходного множества,
которые обладают и свойством αk + 1, и свойством α1.
Мы отсюда извлекли сначала все объекты, которые заведомо обладают свойством αk +
1, а потом из них, в свою очередь, выбрали те, которые обладают еще и свойством α1.
Понятно, что в результате мы получили просто те объекты отсюда,
которые одновременно обладают как αk + 1, так и α1.
То есть, если вот это вот равняется N( αk + 1 ),
то вот это число — это N( α1, αk + 1).
Можно вот так написать.
Просто количество всех объектов из исходного множества,
которые одновременно обладают как вот этим, так и вот этим.
Совершенно так же здесь получаем N( αk,
αk + 1 ), здесь получаем N( α1,
α2, αk + 1), здесь получаем
N(αk − 1, αk, αk + 1 ).
Ну и так далее.
Вот здесь вот получаем M...
Нет, N, извините, конечно N.
Мы все приводим к виду N.
N(α1, ..., αk, αk + 1 ).
Вот такая вот замечательная формула.
Да, а что такое слева?
Что написано слева?
Ну слева тоже написано количество объектов среди вот этих вот.
То есть среди тех объектов отсюда, которые обладают свойством αk + 1,
и которые в то же время не обладают ни одним из оставшихся свойств.
То есть вот эта вот величина (давайте я здесь напишу),
M(α1′, ..., αk′) = N(α1′,
..., αk′, αk + 1 без штриха).
Мы смотрим те объекты, которые, с одной стороны,
обладают αk + 1 свойством, но при этом не обладают ни одним из первых k свойств.
α1′, ..., αk′ — вот ни одним из них не обладают.
В итоге получилась такая замечательная формула.
Давайте ее еще раз перепишем.
N(α1′, ..., αk′,
αk + 1) = N(αk + 1) (и
эта формула доказана строго, потому что она вытекает
из предположения индукции) − N(α1, αk + 1) −...
− N(αk, αk + 1) +...
+ N от...
сейчас, секунду...
плюс и так далее, давайте вот так плюс...
виноват, немножко запутался.
Значит, +...
+ просто вот это напишем.
( −1) в k-той степени N(α1,
..., αk, αk + 1).
Вот так, покороче записал уже.
Не стал лишнего выписывать.
Вот эти слагаемые писать не стал.
Вот. Это то, что у нас получилось на выходе в
результате рассмотрения второго пункта, да?
Теперь вспоминаем (сейчас мы вернемся немножко сюда), вспоминаем,
что у нас еще есть вот эта формула, которая доказана в первом пункте.
Нудная-пренудная.
Но куда же деваться?
Вот есть такая формула.
Мы ее доказали, а потом — ту.
Давайте знаете что сделаем?
Давайте из вот этой формулы...
из вот этой формулы, из этого равенства вычтем то новое равенство,
которое только что доказали.
Сейчас будем это аккуратно делать на оставшемся у нас месте.
Что значит «вычесть»?
Значит, надо из N(α1′,
..., αk′) вычесть (это вот то,
что находится слева в наших формулах) N(α1′,
..., αk′, αk + 1).
Это вот слева.
А дальше, после знака равенства,
мы тоже будем вычитать все, что написано вот здесь из того,
что было написано в рамках пункта один, который я только что показал и напомнил.
Значит, вот будем вычитать.
Ну давайте посмотрим, а что вот это такое?
Чему это на самом деле равняется?
Значит, здесь у нас написано количество тех объектов,
которые не обладают ни одним из первых k свойств.
А здесь у нас написано количество тех из них,
тех из них, то есть опять же тех, которые не обладают ни одним из первых k свойств,
но которые к тому же еще обладают k + 1 свойством.
То есть вот есть все, которые не обладают k свойствами, а есть среди них те,
которые обладают свойством k + 1.
Ну понятно, сколько их.
Их в точности N(α1′, ..., αk + 1′).
Из всех, которые этими не обладают,
мы вычитаем их же, но с добавлением свойства αk + 1.
Значит остаются те, которые, конечно, по-прежнему не обладают первыми k,
но еще и не обладают k + 1.
Видите, уже вырисовывается формула включений-исключений, по крайней
мере ее левая часть, для случая, когда свойств k + 1, как нам и хотелось.
Осталось разобраться с правой частью.
Ну давайте смотреть.
Вот в той формуле, которая есть в пункте один,
у нас присутствует число N, правильно?
Дальше из него вычитаются числа N(α1) −...
− N(αk) и это все, что вычиталось в рамках той формулы,
которая была доказана в пункте один текущего доказательства.
Но из этой части мы, в свою очередь, вычитаем все, что нарисовано вот тут.
Все, что нарисовано в доказанном в рамках пункта два утверждении.
В частности, мы вычитаем и вот это N тоже.
Мы вычитаем N(αk + 1).
Смотрите, как здорово.
Формула прорисовывается все дальше.
Видите, было общее количество объектов.
Выкинули те, которые знают α1, те, которые знают αk,
но у нас же их k + 1 штука, значит надо еще выкинуть k + 1.
Да, действительно, выкинули k + 1 за счет вот этого вот.
Мы же его вычитаем?
Теперь давайте прибавлять.
В формуле, которая доказана в рамках пункта один доказательства.
Мы прибавляли исключительно N(α1, α2) +...
+ N(α k − 1, αk), потому что на том этапе мы рассматривали только k свойств.
Но здесь явно чего-то не хватает,
чтобы была справедлива формула включений-исключений для k + 1 свойства.
А чего не хватает?
Так, друзья мои, ровно того не хватает, что вот здесь вычитается.
Но вы не забывайте, мы же вычитаем вот это выражение.
То есть вот эти все «минусы» заменяются на «плюсы» при вычитании.
Мы добавляем еще N(α1, αk + 1) +...
+ N(αk, αk + 1).
И таким образом, среди вот этих вот прибавляемых присутствуют уже все
возможные пары свойств, в том числе вот эти вот.
Ну и так далее.
Дальше, я думаю, совершенно понятен принцип.
Последнее вычитаемое будет вот эта вот штука.
Давайте ее напишем.
Будет «плюс», и она пойдет со знаком «минус», вот эта вот величина.
Ну что значит «она пойдет со знаком минус»?
Это значит (−1) в k-той степени умножится на (−1).
Получится (−1) в k + 1.
А в скобочках после N будет в аккурат (α1, ..., αk + 1).
Теперь смотрите на формулировку нашей теоремы,
формулы включений-исключений — и получайте катарсис, если это еще возможно.
Потому что все, мы доказали, действительно,
формулу включений-исключений ровно в том виде,
в котором она заявлена в нашей теореме, но теперь уже для случая k + 1 свойств.
Все, теорема доказана.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2019 Coursera Inc. Todos los derechos reservados.
