и по идее эту формулу надо аккуратно доказывать. Я могу, конечно это сделать, и наверное я сейчас это проделаю всё-таки. Просто для того, чтобы не оставалось у слушателей какого-то впечатления, будто бы я что-то недоговариваю, будто здесь это как-то очень трудно. Но смотрите, если при первом прослушивании этого курса вам покажется слишком занудным и трудным доказательство этой теоремы- оно в принципе несложное, но немножко такое требующее все-таки аккуратного восприятия, то вы не пугайтесь, это не страшно. На самом деле суть-то интуитивно совершенно понятна. И этой сути вполне достаточно для того, чтобы решать конкретные задачи. После того, как я произнесу занудную речь с доказательством, ну я уж постараюсь его там расцветить всеми возможными способами, но оно все-таки будет немножко занудное, вот после того как я воспроизведу доказательство этой формулы, я приведу обязательно пару примеров задач, которые с помощью этой формулы очень красиво решаются, прокомментирую их, и я думаю, что это будет как раз то, что нам нужно в рамках этой лекции, когда мы действительно как следует с вами осознаем вот этот вот замечательный принцип, как работает формула включений-исключений. Итак давайте сейчас перейдем все-таки к аккуратному доказательству, которое, повторяю, при первом прослушивании можно чуть-чуть пропустить, но можно и не пропускать, можно вникнуть. А после доказательства обсудим примеры. Так, ну давайте все-таки докажем эту теорему, докажем формулу включений-исключений. Тут есть один тонкий момент, который связан с тем, что доказательство будет идти с помощью то что называется метода математической индукции. Значит, конечно, если этот метод сам по себе рассказывать в подробностях, это займет еще одну лекцию как минимум. Но с одной стороны я надеюсь на то, что большинство слушателей так или иначе как минимум слышало, что такой метод существует. С другой стороны, я уже сказал, что в общем, если вы это доказательство в курсе не осознаете- это не смертельно совершенно, потому что я его привожу исключительно для полноты картины, чтобы слушателям не показалось, что я их обманываю и давлю исключительно на интуицию. Ну а в-третьих, идея-то очень простая. Давайте я сейчас буду рассказывать, в чем состоит метод, и идеологически я думаю что вы поймете на самом деле, как это устроено, и действительно поверите в то, что этот принцип должен работать. Итак, смотрите, давайте сперва докажем утверждения для случая n маленькое, то есть количество свойств, равного единице. Давайте во-первых рассмотрим ситуацию, когда у нас есть только одно свойство, которое нас интересует. Ну скажем, знание английского языка. Понятно, что в этом случае все данные, которыми мы располагаем- это лишь количество объектов в нашем множестве, и это, конечно, количество объектов среди них, которые обладают свойством альфа один у нас, n маленькое равняется единице, никаких других свойств кроме альфа один нету, поэтому вот все наши данные. N большое- это общее количество свойств. N большое от альфа один это- извините, не свойств, а объектов, конечно- это количество объектов, которые обладают ровно вот этим одним свойством. И интересует нас по-прежнему количество объектов, которые этим свойством не обладают. N от альфа один штрих- это и есть та величина, которую мы изучаем в теореме. Ну, здесь вроде совершенно понятно, что если мы хотим найти количество людей, которые не знают английский среди всех людей, и при этом знаем, сколько из них владеют английским языком, то действительно надо взять просто количество всех людей, вычесть из них количество тех, кто владеет английским языком, и мы получим товарищей, которые английского не знают. То есть, это абсолютно очевидная штука. С другой стороны, вот эта абсолютно очевидная штука- это и есть частный случай формулировки теоремы. Ну, когда n маленькое равняется единице, никаких других вычитаемых и тем более добавляемых нету. То есть, та формула, которая заявлена в утверждении теоремы, она как раз вот к этому и сводится. Упрощается до такого вот замечательного вида. Иными словами, при n маленькое равном единице утверждение теоремы, вот оно, является очевидным фактом, не требующим какого-то специального доказательства. То есть мы знаем, что для n маленького равного единице это верно. Ну, давайте даже так, я прямо вот напишу: мы знаем, что при n маленькое равном единице верно следующее: верно следующее какие бы N большое объектов мы ни взяли (нас природа этих объектов не интересует) даже вот так: сколько бы объектов мы ни взяли, каково бы ни было число N большое, это значок "для любого" каково бы ни было N большое, и каковы бы ни были сами вот эти вот объекты N а1 и так далее аN большое, и наконец, каково бы ни было одно-единственное свойство альфа один, вот простите за занудство, но я напишу в такой степени подробности, вот какими бы ни были все вот эти вот данные, теорема верна. Формула включений-исключений верна. Мы ее только что доказали. Ну давайте, не верна, чтоб здесь "верно" и здесь "верно" как-то нехорошо, ну напишем "справедлива". Для красоты. Имеет место формула включений-исключений. Не важно, сколько этих объектов, кто они там, это люди, это какие-нибудь, я не знаю, бракованные-небракованные детали, это какие-нибудь машины там, что хотите. Каково бы ни было свойство, но если только оно одно- формула включений-исключений верна, вот это мы доказали.
