Смотрите, до сих пор все тождества, которые мы с вами доказывали, они такие знакопостоянные, там все время плюс, плюс, плюс, плюс, всё складывается и всё. Но, можно и почередовать знаки. Давайте, я парочку таких тождеств приведу. Одно совсем простое, вот такое вот, но в нем есть малюсенький подвох, который я очень люблю, может кто-нибудь сразу его заметит, а может быть и нет. Чему это равняется? Чему равняется такая знакопеременная, знакочередующаяся сумма? Нулю, правильно, да, но, не совсем. Если n = 0, да, да, если n = 0, то она равна 1, потому что из всего этого безобразия выживает только C из 0 по 0. При n = 0 она всё-таки равна 1, и только при n, больших 0 строго, она равна 0. Вот такая вот небольшая закавыка, которую как-то обычно не услеживают по той простой причине, что, в отличие от нас, не считают 0 натуральным числом. А мы считаем. Не, ну а что, действительно, пустое множество, оно же есть? Деваться некуда. Доказательство очевидное. Этот случай я уже разобрал, а если n > 0, если n > 0, тогда корректно записать вот такую вот вещь: (1 – 1) в n-ной степени, и просто к ней применить бином. Ну, понятно, она, с одной стороны, равняется 0, а, с другой стороны, по биному, она равняется в аккурат тому, что написано на доске. Просто бином. Ничто больше. Вот. Давайте я еще одно выведу как раз из формулы включений-исключений, которую мы сегодня успешно доказали. Еще одно тождество выведу из формулы включений-исключений и буду действовать, как в рамках 6-го пункта, то есть я постепенно приду к некоторому тождеству. Не сразу его вам напишу, а постепенно к нему приду. Ну давайте рассмотрим какое-то множество объектов A, которое состоит из элементов а₁,..., аn, а₁, ..., аn, и давайте в качестве V, — надстройки над этим множеством, как обычно, — в качестве V рассмотрим множество всех m-размещений с повторениями, m-размещений с повторениями, которые можно извлечь из А, всех m-размещений. А, да, и давайте считать, что вот это m, оно строго меньше, чем n. Просто ну вот так зафиксировали m < n. Ну сколько их всего? Очевидно? Размещения с повторениями — это просто слова такие: упорядоченные последовательности. Ну просто n в степени m, правда же? Ну А из n по m с чертой, конечно, но это просто n в степени m. На каждую позицию размещения ставим любой из объектов, и в сумме должно получиться m штук. Ну значит будет n в m-той степени. Это понятно. Давайте вот эту штуку обозначим через N, подразумевая, что сейчас к элементам множества V мы будем применять некую формулу включений-исключений. То есть те объекты, которые фигурируют в формуле включений-исключений, в нашем случае — это элементы V. Не вот эти вот объекты, а именно m-размещения, слова являются объектами, и именно они будут обладать или же не обладать какими-то свойствами. Надо перечислить какие-нибудь свойства. Давайте в качестве свойств возьмем такие: αi — это свойство, состоящее вот в чём: давайте так, я напишу двоеточие, что ли. Размещение из вот этого множества V обладает, облада… Что я написал? Смотрите, что я написал, а. Ну это, это стандартная ошибка, это вообще, это психоанализ по Фрейду. Я не говорю, что она стандартная конкретно для этого слова, понимаете, это вообще такое совершенно расхожее явление, оно очень часто приводит к неприличным результатам. Можете сами подумать, как это получается, но вот случается такое, к сожалению. Так, ну, конечно, не «обладел», а «обладает». Так. Ну, вообще, тут если бы «обалдеет» получилось, было бы лучше, конечно. «Обалдает», да? Так, размещение из V обладает свойством αi по определению тогда и только тогда, когда это размещение, это размещение не содержит, подчеркиваю, не содержит, — обладает свойством — это значит, что не содержит, — элемент аi, не содержит элемент аi. Ну давайте обсудим, чему равняется, скажем, N(αi) в обозначениях формулы включений-исключений. Чему равняется N(αi)? Ну это сколько есть всего m-размещений, которые не содержат элемент аi, правильно? Ну, скажем, а₁. (n – 1) в m-той, конечно, да, это просто (n – 1) в m-той. А если мы напишем N(αi, αj) для какой-нибудь пары свойств, то это значит оно уже не содержит элементы αi, αj, а таких размещений (n – 2) в m-той, ну и так далее. Так, давайте еще посмотрим, чего будет для N(α₁,..., αn). Правильно совершенно, да, это будет просто 0 в m-той степени, потому что ну не бывает такого размещения, которое вообще не содержало бы ни одного объекта. Таких не бывает, правда? Их 0 в m-той степени. Так, а что такое N(α′₁, α′n)? Что оно выражает? Оно выражает количество размещений, которые, наоборот, содержат каждый из наших объектов, да? А бывает такое? Нет, потому что m < n. Мы выбрали m специально меньшим, чем n, поэтому размещений размера m, которые бы содержали все n объектов, не бывает: m < n. Нельзя собрать размещение из n объектов, если в нем меньше, чем n элементов. Поэтому это тоже 0. Это тоже 0, И у нас получается такая формула включений-исключений: N, то есть n в степени m, давайте я его еще для красоты, вот это N, умножу на C из n по 0. Ну просто для красоты, сейчас увидите почему. Что из него вычитается? В формуле включений-исключений? Все вот эти вот штуки, правильно? А сколько их? Их C из n по 1, поэтому вычитается (n – 1) в m-той * C из n по 1, прибавляется (n – 2) в m-той * C из n по 2, вычитается и так далее. Ну давайте уж так и напишем: прибавляется –1 в n-ной степени * 0 в m-той и * на C из n по n. Это последнее слагаемое, и всё это равно вот этому вот, то есть 0. Хлоп! Какое красивое тождество! И пойдите вы такое знакопеременное тождество докажите сейчас без формулы включений-исключений. Нет, может и докажете, как повезет, но — красивый, содержательный способ получения нетривиальных тождеств. Просто вы можете сейчас нагенерить море разнообразных тождеств таким вот макаром. Сгенерили красивое — можем использовать на практике.