Ну хорошо. Пока-то мы доказали только два тождества. Давайте докажем ещё одно. Третье тождество, которое, мне кажется, каждый должен сходу знать, с которого надо начинать, как и с этих первых двух, это вот такое утверждение. Давайте посмотрим, чему равна сумма всех возможных элементов очередной строчки треугольника Паскаля. То есть просто сложим между собою вот эти вот чиселки, которые находятся в очередной строчке. C из n по 0 — вот оно: единичка. C из n по 1 — вот в данном случае n равно пяти, поэтому C из n по 1 равняется пятёрке. C из n по 2, c из n по 3 и так далее. Вплоть до c из n по n. Что будет, если просуммировать все элементы какой-нибудь фиксированной строчки треугольника Паскаля? Что будет? Ну вот давайте посмотрим на эту строчку. Что будет? 1 плюс 5, 6 плюс 10, 16 плюс 10, 26 плюс 5, 31 плюс 1, 32 Ну конечно, кто-нибудь скажет, что 32 — это замечательное число, потому что у человека столько зубов во рту. Ну это правильно. Давайте попробуем сложить вот эту строчку. 1 плюс 4 — это 5, плюс 6 — это 11, плюс 4 — это 15, плюс 1 — это 16. Ну 16 — это половина от общего числа зубов в человеческом рту. Не знаю, к какому возрасту остаётся обычно в среднем столько зубов, но замечательно то, что здесь тоже степени двойки — это 16, это 32, наводит на какие-то мысли. Ну вот дело в том, что действительно сумма всех элементов фиксированной строчки, — это просто 2 в степени n. И на самом деле, несмотря на весь мой шуточный пафос, который я наводил вокруг этой формулы, доказательство можно сделать просто в одну секунду. А именно: давайте напишем вот такое вот выражение. (1 + 1) в n-ой степени. Ну чем не бином? Просто здесь вместо x поставлена 1 и вместо y поставлена 1. Ну хорошо. Давайте напишем. Это есть сумма пока от 0 до n. Я просто пишу бином Ньютона в случае, когда вместо x подставлена 1, вместо y подставлена 1. Дальше идёт c из n по k, понятное дело. А дальше вроде как должны идти x в степени k умножить на y в степени n минус k. Ну правильно, вот он x в степени k, вот он y, который в данном случае тоже 1 в степени n − k. Ну, понятное дело, что умножение на 1 в какой угодно степени — это просто никак не меняет формулу. Умножать не нужно. То есть это в точности то же самое, что и сумма пока от 0 до n. Просто c-шек, c из n по k. Сумма по k от 0 до n вот таких вот c-шек. Ну или, извините, просто в точности c из n по 0 + c из n по 1 +, ..., + c из n по n. Просто можно по-разному написать. В виде значка суммирования такого или многоточия между плюсиками. Можно написать как угодно. Но прекрасно то, что слева-то написано 2 в степени n — это, я надеюсь, очевидно абсолютно всем присутствующим на лекции? То есть действительно сумма всех возможных c — это 2 в степени n. Видите? В одну строчку доказали. Можно доказать по-другому. Так сказать, чисто комбинаторно, в духе того, как мы рассуждали, когда доказывали тождество номер два для треугольника Паскаля. Можно доказать так. Давайте другое доказательство. Вот чтоб вы понимали: одно доказательство всё — уже есть, оно правильное, никто в нём не сомневается, но можно сделать другое, более комбинаторное, менее, так сказать, аналитическое доказательство. Более комбинаторное доказательство такое. Давайте рассмотрим все возможные последовательности из 0 и 1, в которых всего n этих самых 0 и 1, и подумаем, сколько таких последовательностей. Значит, мы рассмотрим все возможные последовательности из 0 и 1 длины n, то есть каждая последовательность ровно n каких-то там 0 и 1. Ну так ясно, что на каждую позицию такой последовательности, ясно, что на каждую позицию такой последовательности, можно либо поставить 0, либо поставить 1. То есть для каждой позиции есть всего два варианта. Это чистое правило умножения. Помните, как формируются автомобильные номера? На первую позицию ставим любую букву, на вторую позицию ставим любую цифру. Ну, короче говоря, ясно, что по правилу умножения количество таких последовательностей — это в точности 2 в степени n. Значит, ясно, что количество таких последовательностей — это 2 в степени n. 2 умножаем на 2, умножаем на 2 n раз — получаем 2 в степени n. Но можно с другой стороны проклассифицировать некоторым образом эти последовательности. Вот по аналогии с тем, как мы действовали, когда доказывали тождество номер два. Давайте сделаем так. Есть последовательность, она одна такая, которая состоит сплошь из нулей. У ней n нулей и ни одной единицы. Дальше есть последовательности, в которых ровно одна единица. Вот такие. Понятно, что это какие-то другие последовательности: здесь вообще единицы не было, здесь она ровно одна. И понятно, сколько таких последовательностей. Ну вы скажете n. Правильно, конечно n. Но я скажу по-другому. Я скажу, что их с из n по 1. Почему c n 1? А помните давешние паспорта для баранов? Вот мы ровно так их формировали — это были последовательности из нулей и единиц. И нам нужно было, если мы говорили о паспорте, в котором одна единица, выбрать одну позицию из n возможных. Это делалось c из n по 1 способами. Но и неудивительно, с из n по 1, конечно, равняется n. Выбрать одну позицию из n возможных, естественно, можно только n способом. Вот. Ну я вам даже больше скажу. Вот здесь вот можно написать c из n по 0. Потому что ровно одна последовательность вполне себе выражается формулой c из n по 0. c из n по 0 равно 1. Давайте я здесь запишу: c из n по 0 = 1. Дальше есть последовательности, которые содержат две единицы. Я уже их не буду все перечислять. Я просто напишу: есть последовательности с двумя единицами и n минус с двумя нулями. Но опять, какое у них количество? Их количество — это просто количество способов выбрать две позиции из n возможных. Так, чтобы на эти две позиции поставить единичку. То есть их c из n по 2. Ну у нас это было с паспортами баранов. Ну и так далее. Есть, наконец, последовательности с n единицами. Их, разумеется, c из n по n, то есть одна. Одна-единственная последовательность, которая состоит из n единиц, и мы видим, что общее число последовательностей — это ровно 2 в степени n, и его можно представить как сумму числа последовательности такого вида, числа последовательности такого вида, числа последовательности такого вида и так далее, вплоть до этих. Естественно, никаких других последовательностей из нулей и единиц не бывает. В каждой последовательности из нулей и единиц — сколько-то единиц. Ноль, одна, две, n, но сколько-то есть. Отсюда мы и получаем, что 2 в степени n, общее количество последовательностей может быть разбито вот в эту замечательную сумму. И таким образом тождество полностью доказано.
