Добрый день! Давайте сегодня изучим в рамках этого курса, последний содержательный принцип комбинаторики ну, он не последний вообще, в комбинаторике есть огромное количество самых разных и задач, и методов, и принципов, но сегодня мы изучим тот последний принцип, который мне хотелось бы изучить в рамках этого простого совсем такого вот базового курса по комбинаторике, это то что называется «формула включений и исключений» давайте я напишу. Такое вот красивое выражение формула включений и исключений. Но так если совсем занудствовать по поводу названия, здесь за частую вместо «и» рисуют просто «дефис», – формула включений-исключений без всякого союза. Вот ну можно как угодно. Значит давайте рассмотрим пример задачи, чтоб понять о чём на самом деле пойдёт речь, чтоб я не был слишком абстрактным, ну а пример задачи традиционно вот какой-нибудь такой, совсем простой, чтоб мотивировать эту деятельность, пример следующий: есть у нас аудитория, вот здесь вот сидит перед мной аудитория в которой находится, ну скажем, 30 человек давайте считать что в аудитории находится 30 человек. Ну и давайте посмотрим на какие-нибудь содержательные свойства, которыми эти вот люди, каждый из этих 30 людей, может обладать или же не обладать. Ну, как вы понимаете, свойства могут быть самыми разнообразными, то есть в принципе можно посмотреть на кучу разных проявлений, которыми может обладать или не обладать человек, но поскольку мы рассматриваем пример, то в какие-то карнавальные проявления мы вдаваться точно не будем, мало ли какие свойства бывают. Вот говорят есть люди, которые способны забраться на дерево и выпить 2 бутылки водки, но это хорошее свойство конечно, однако мы его сейчас рассматривать не станем. Вот значит 30 человек, ну давайте посмотрим просто на какие-нибудь знания языков, например, вот есть какие-то иностранные языки: английский язык, французский язык, ну и, скажем, немецкий язык, я не буду опять же выпендриваться, говорить про какие-то хитрые языки, пускай будет просто банально – английский, французский и немецкий. Понятно, что каждый из наших 30 человек, которые присутствуют в аудитории, может как знать, так и не знать любой из этих языков, может знать или не знать английский, может знать или не знать французский, и, наконец, может знать или не знать немецкий. Никакие другие языки нас сейчас, с точки зрения постановки задачи, не интересуют. Вот нас интересуют только эти 3 свойства человека, знание или же незнание какого-то из этих языков. Ну, давайте для примера считать, что среди наших 30 человек, ну, скажем, 20 человек в сносной мере владеют английским языком. Давайте... английским языком владеет 20 человек из наших 30, соответственно французким языком давайте считать, что владеет, скажем, 5 человек. Ну более или менее понятно, что французкий как-то не настолько распространён среди людей в нашей стране как английский, английский всё-таки сейчас язык международного общения, а французский не настолько популярный. Ну вот то же самое касается немецкого языка. Популярность его не столь велика, давайте для примера считать, что в нашей аудитории есть ровно 5 человек, которые в сносной мере владеют немецким языком, что достаточно меньше чем 20, вот. И вы конечно понимаете, что когда у нас 30 человек, вот эти вот множества, то есть множества людей, которые владеют английским, множества людей, которые владеют французким языком, и, наконец, множества людей, которые знают немецкий язык, – они могут как пересекаться так и не пересекаться вовсе, то есть тут могут быть самые разные ситуации. Вполне может случиться, что есть люди, которые знают английский, но при этом ещё знают и французский и даже немецкий, такое вполне даже может произойти, а может и не произойти, потому что 30 это как раз 20 + 5 + 5. Варианты возможны всякие, но поскольку мы рассматриваем конкретный пример, давайте будем считать, например, что одновременно английский и французский язык – я вот так буду обозначать А, Ф – подразумевает, что человек знает сразу и английский и французский язык одновременно. Давайте считать, что знает, скажем 2 человека. Вот есть 2 человека из наших 30, которые всё-таки знают одновременно английский и французкий, то есть вот эти 2 множества, множества людей, знающих английский и множества людей, знающих французский – они пересекаются ровно по 2-м общим элементам, при этом я не говорю, что среди этих 2 людей нету тех, которые могли бы знать немецкий, вполне могут быть. Так и давайте то же самое, английский и немецкий будем предполагать, что знают одновременно 2 человека, и наконец вот то, о чём я говорил: никто не исключает наличия пересечения всех 3-х языков, то есть наличия полиглотов в нашей аудитории, товарищей которые владеют сразу 3 языками из перечисленных. Ну это, соответственно, надо как-то вот так обозначить: А, Н, Ф – это люди, которые обладают всеми 3-мя перечисленными знаниями. Ну, давайте считать для разнообразия, что это 1 человек. 0 – это было бы неинтересно, потому что тогда это бессмысленное утверждение, а 2 – это тоже, ну как то не очень интересно, потому что зачем я тогда писал отдельно вот эти, А, Ф А, Н, так... подождите... А, Н, Ф я ещё не написал, да, я же забыл ещё пересечение товарищей вот каких: немецкий и французский, ну давайте тогда вот так напишем для примера: немецкий и французский знают однавременно 1 человек, английский и французский – 2, английский и немецкий тоже 2, а все 3 – ну вот тот самый 1 человек, который знает и немецкий и французский, вот он знает ещё и английский тоже. Вопрос возникает следующий. Давайте я его прям его зафиксирую здесь, под рубрикой вопрос: а можно ли имея эти вот данные на руках... сейчас я это всё напишу, а можно ли имея эти данные на руках, посчитать сколько у нас наоборот есть людей, которые не знают ни одного языка? Ну, я это напишу коротко и просто: сколько человек, в нашей аудитории не знают ни английского, ни французского ни немецкого? Можно это как-то вычислить, имея на руках те данные, которые я здесь выписал: всего 30 человек из них 20 человек знают английский и возможно ещё какие то языки, 5 человек точно знают французский и возможно ещё какие-то, 5 человек знают немецкий и возможно ещё какие-то, дальше идут пересечения немецкий и французский знает 1 человек, но он, как потом мы выясним, знает ещё и английский. Английский и французский знают двое, но среди них есть те, которые к тому же знают немецкий. Ну и наконец, английский и немецкий знают двое, опять же среди них есть точно какой-то человек, который знает одновременно французский язык тоже, вот как теперь посчитать, сколько людей не знают вообще ни одного языка? Ну вот это и есть, то что называется формула включений и исключений. Идея очень простая, действительно, вот мы хотим посчитать число людей в аудитории, которые не знают ни одного языка из вот этих трех. Давайте действовать так. Всего, понятное дело, у нас 30 человек но конечно нелепо думать, что люди, которые не знают – вот их столько, что их 30. Но как же их 30? Мы точно знаем, что среди этих 30 товарищей есть как минимум 20 человек, которые хоть какой-то язык знают, а именно это 20 человек, которые заведомо знают английский. Значит, если мы желаем посчитать количество людей, которые не знают вообще ничего, наверное мы из этих 30 точно должны удалить те 20, вычесть те 20, которые заведомо знают английский язык и возможно ещё какие-то. Но ведь есть же люди, которые знают французский язык, и их тоже по идее надо вычесть. Ну а как же, если мы будем включать этих людей в наше множество людей, которые ничего не знают, то это будет нонсенс! Они же знают французский, как их можно включить? Их надо исключить. Видите вот, мы исключаем людей, которые знают английский, исключаем людей, которые знают французский, и наконец, исключаем людей, конечно, которые знают немецкий. Но при этом, если внимательно посмотреть на написанное, мы понимаем что, ну ёлки-палки, ведь среди людей, которые знали английский язык, были в том числе и те, которые знали французский. И наоборот, среди людей которые знали французский, и которых мы исключили, вместе с этими условными англичанами, есть люди, которые заведомо знают английский, поэтому исключая 20 здесь и исключая 5 вот тут, мы исключили лишнее – мы исключили пересечение вот этих двух множеств. Мы лишний раз выкинули тех, кто одновременно знает английский и французский, значит, надо компенсировать, надо включить этих товарищей в нашу формулу, добавить их. Мы их вычли и вот здесь, вычитая 20, и вот здесь, вычитая 5. Ну это у нас английский, это у нас французский вроде бы, да? Значит надо добавить тех, кто знает английский и французский одновременно, а их у нас 2 человека. Вот мы добавляем двоих, которых вычли здесь лишний раз. И дальше рассуждаем точно так же: ведь вычитая вот эти 20 и вычитая вот эти 5, мы, опять же, лишний раз произвели вычитание тех людей, которые одновременно знают английский и немецкий, вот здесь у нас уже пятеро немцев вычитались. Значит, надо компенсировать это путём включения тех товарищей, которые одновременно знают английский и немецкий, а таковых двое. Включаем этих двоих. Ну и наконец, вот это двухкратное вычитание пятёрок означает, что мы один раз вычли товарищей, которые знают французский и, возможно, знают немецкий, а здесь мы ещё раз вычли тех же товарищей, которые знают немецкий и, возможно, знают французский. То есть, и здесь есть товарищи, знающие немецкий и французский, и здесь есть товарищи, знающие немецкий и французский — их, как мы помним, один человек — значит, надо добавить ещё вот этого одного человека. И последний шаг в этой занудной истории состоит в том, чтобы заметить: когда мы производили вот это приплюсовывание, когда мы осуществляли нашу компенсацию, так сказать, включение, после вот этого исключения, мы на сей раз опять лишнего навключали. Дело в том, что добавляя вот эту двойку, добавляя вот эту двойку и добавляя вот эту, наконец, единицу, мы лишний раз посчитали тех людей, которые знают одновременно английский, немецкий и французский. Вот их надо вычесть, исключить. Значит смотрите, друзья: я думаю, что многие из вас, глядя на этот пример, особенно, так сказать, увлекшись моей убедительностью, что ли — я могу на вас давить всем своим авторитетом — посмотрят и скажут: «Да, это конечно, это очевидно абсолютно». С другой стороны, есть всегда в любой аудитории, сколько б там человек ни было – 30, или 130, или сколько хотите… 10 тысяч, есть, безусловно, пытливые люди, которые скажут: «А почему, собственно вот, мы здесь только один раз вычитали? Ведь вроде бы мы этих англо-немце-французов и вот здесь вот лишний раз учли, и вот здесь лишний раз учли, и вот здесь лишний раз. Может быть, надо было вычесть не единицу, а тройку?» То есть, на самом деле, при всей своей интуитивной очевидности, та формула, которую мы сейчас написали, не является доказанной строго. Конечно, можно, как водится, там, в школе, как делают в пятом классе, наверно, можно нарисовать круги, символизирующие множества людей, знающих английский, немецкий и французский. Ну вот как-нибудь вот так: круг людей, знающих английский — это как раз наши 20 человек, дальше у нас есть круг людей, знающих французский, это вот здесь вот давайте 20, вот здесь 5, есть круг людей, знающих немецкий, их тоже 5 человек, и мы знаем величины вот этих всех пересечений. А найти нам нужно множество тех людей, которые не знают никакого языка, вот в таком универсуме, в котором изначально всего 30 человек. Универсум — это просто аудитория наша. В ней 30 человек, 20 из них — английский, 5 — французский и 5 — немецкий, все пересечения, в том числе вот это, малюсенькое, состоящее из одного человека, мы знаем. Все пересечения мы знаем, легко сообразить просто вот теоретико-множественно, что останется вне вот этих вот всех множеств. И действительно, после аккуратного рассмотрения этой ситуации вы увидите, что да, надо вычитать только один раз единицу, никакой ошибки здесь не допущено. Это не только интуитивно понятно, это не только моя убедительность, моя, так сказать, харизма, давление на вас, это ещё и реальность — то есть, вполне доказуемая вещь. Но вот в этой конкретной ситуации это доказать легко, просто, повторяю, перебрав все возможные пересечения этих кругов и честно написав, что в итоге получится. Когда мы сейчас перейдём от вот этого конкретного примера к общей ситуации, вы поймёте, что в общей ситуации просто взять, нарисовать кучу кругов и как-то сапеллировать к этой картинке уже не получится. По идее, потребуется доказательство. Но об этом чуть позже. Значит, давайте, прежде чем переходить, собственно, к общей ситуации, посмотрим, что же у нас в итоге получилось, сколько есть таких вот неучей в нашей аудитории. Если вот эти товарищи — это полиглоты, то, соответственно, то, чего мы вычислили — это количество неучей, кто не знает никакого из трёх языков. Хотя, может быть, они знают китайский, например — это тоже замечательно. Значит, 30 − 20 — это 10, − 5, − 5 — это 0, + 2 + 2 + 1 — это 5 − 1 — это 4. И мы получили вполне себе конкретный, однозначный ответ — задача полностью решена. Вот. Идея понятна, получилась, действительно, вот такая вот формула включений и исключений, мы включаем-исключаем, включаем-исключаем, и получаем в итоге ответ. Давайте попробуем понять, как это напишется в общем случае. Общую постановку вопроса сделаем.
