Давайте я еще третье тождество напишу. Ну «еще» – это сильно сказано, сейчас их будет довольно много. Ну третье – оно тоже простое. Это вот такое утверждение, которое часто бывает полезным, что если мы сложим вообще все биномиальные коэффициенты, просто сложим их между собой, то получится ровно 2 в степени n. Доказательства этого факта. Ну можно привести 2 доказательства. Одно вытекает сразу из бинома. И это полезно. Потому что если вы возьмете (1 + 1) и возведете в степень n, то чем не бином? Бином самый натуральный. С одной стороны, это, конечно, 2 в степени n. Это не вопрос. (1 + 1) в степени n – это 2. Вот, с другой стороны, вы, действительно, применяете бином, и у вас получается (C из n по 0) × (1 ну, скажем, в степени 0) × (1 в степени n). Это все перемножается. Дальше прибавляется (C из n по 1) × (1 в степени 1) × (1 в степени n − 1) +... + последнее слагаемое, это (C из n по n) × (1 в степени n) × (1 в степени 0). Ну единица, она, как вы понимаете, и в Африке единица. То есть с ней ничего делать не надо. Вот получилась та самая сумма, которая и должна равняться 2 в степени n. То есть тривиальное доказательство. Тривиальное. Можно дать прямое комбинаторное рассуждение, которое обозначает то же самое. Давайте, второй вариант доказательства. Это первый. Ну второй вариант доказательства такой: давайте рассмотрим множество V. Будем рассуждать прямо как в предыдущем тождестве. Рассмотрим множество V, состоящее из всех последовательностей нулей и единиц длины n. Разумеется, |V| = 2 в степени n, потому что на каждую позицию в нашей последовательности мы можем поставить независимо от остальных 0 или 1. Ну это очевидно. Вот. Очевидно, правда? А то вдруг неочевидно? Не дай бог! Так, с другой стороны, мы можем разбить его на кусочки V0, U V1, U... U Vn, где Vi-тое – это множество всех последовательностей длины n, естественно, с k единицами. Согласны, что это разбиение? Э! Действительно! Правильное недоумение – с i единицами, конечно. Виноват. Ну правильное разбиение, да? Есть последовательность, в которой вообще нет единиц. Она одна, и она относиться к V0. Есть последовательность, в которой одна единица. Их таких n, и они относятся к V1. Ну и так далее. Понятно, что мы получили разбиение. Вот, ну и, конечно, ясно, что |Vi| = это в точности C из n по i, потому что нам надо выбрать из n позиций те i, на которые мы поставим единицы. Это делается (C из n по i) способами. Все, вторым способом тождество доказали. Так... Ну давайте четвертое я сразу напишу такое. Давайте просуммируем... Давайте даже так: смотрите, вот что мы здесь сделали? Мы зафиксировали n и просуммировали все возможные биномиальные коэффициенты, да? Ну а давайте зафиксируем n и просуммируем все возможные полиномиальные коэффициенты. Что это значит? Это значит, суммировать надо, конечно, P от (n1, ..., nk), а варьировать вот эти вот величины n1, nk нужно так: нужно брать всевозможные упорядоченные кортежи, наборы из этих (n1, ..., nk). Всевозможные упорядоченные наборы, ну которые обладают понятными свойствами. Для любого i ni-тое у нас натуральное. И сумма чисел (n1, ..., nk) равняется фиксированному нами числу n. Мы фиксировали n. Мы смотрим всевозможные упорядоченные наборы, состоящие из натуральных чисел, в сумме дающие n. И суммируем по всем возможным таким наборам вот эту величину P (полиномиальный коэффициент). Так, внимание, что у нас получится? Не расслабляться. Вообще, можно догадаться, глядя сюда. Сумма всех биномиальных коэффициентов – это 2 в степени n. Но биномиальный коэффициент – это ведь частный случай полиномиального, правда? Бином – это полином при k = 2. k в степени n, правильно! Подсказал. А понимаете, почему? Вот глядите на это доказательство. Здесь такое же работает. Ну просто пишем (1 + 1 +... + 1) k раз, и это все возводим в степень n. Это, конечно, k в степени n, а с другой стороны, это, конечно, вот это. Это понятно? Полиномиальную формулу доказывали в прошлый раз. Ну там на единички в каких-то степенях надо умножить, но они не влияют. Разумеется, то же самое можно доказать и вот так. Вместо последовательностей, состоящих из нулей и единиц, надо рассматривать последовательности, которые состоят из чисел 0, 1, 2, 3, ..., (k − 1), и потом просто классифицировать их по количеству нулей, единиц и прочих чисел, входящих туда.