6-я задача. Итак, нам нужно упростить следующее выражение: C из n по 1 + 2 * C из n по 2 + 3 * C из n по 3 +... + n * C из n по n. Ну давайте я расскажу 2 способа как это считать. 1-й способ, он более прямолинейный, а именно: мы просто возпользуемся формулой для биномиальных коэффициентов. Давайте перепишем каждое слагаемое. Значит, k * C из n по k — это что такое? Значит, это k * n!/((n – k)! * k!). Заметим, что мы здесь можем просто сократить на k, тогда это будет n!/((n – k)! * (k – 1)!). Ну чтобы это было биномиальным коэффициентом, нужно просто вынести отсюда n. Ну вот чтобы это был биномиальный коэффициент, это нужно чтобы сумма чисел в знаменателе была равна сумме в числителе. Сумма чисел в знаменателе — это n – 1, поэтому это равно, перепишем это как n * (n – 1)!/((n – k)! * (k – 1)!). Ну и это биномиальный коэффициент, значит, это будет С из n – 1 по k – 1, то есть n * С из n – 1 по k – 1. Так, давайте подставим полученное нами тождество в эту формулу, меняя каждое слагаемое. Значит, пишем C из n по 1 + 2 * C из n по 2 + 3 * С из n по 3 +... + n * C из n по n. Так, чему это равно? Значит, C из n по 1. По этой формуле, значит, у нас k = 1, ну а n — какое есть. Значит, это будет n * C из n – 1 по 0. Значит, второе слагаемое — это будет n * C из n – 1 по 1 +.... Последнее слагаемое будет какое? Значит, у нас было n * C из n по n, а будет n * C из n – 1 по n – 1. Так, ну и видим, что n выносится за скобки, остается в скобках сумма биномиальных коэффициентов по основанию n – 1. Значит, C из n – 1 по 0 + C из n – 1 по 1 +... + C из n – 1 по n – 1. Так, ну эта сумма по одному из тождеств, доказанных на лекции, равна 2 в степени n – 1, поэтому получаем в итоге: n * 2 в степени n – 1. Так, хорошо. Теперь давайте я расскажу немножко другое доказательство, которое без формул, которое более наглядное. Так, давайте, значит, я начну здесь формулировать, а дальше продолжу на соседнюю доску, а именно: значит, представим себе, что у нас есть мальчик Петя, который ходит в столовую. Значит, в столовой у него есть меню, которое состоит из количества блюд от 0 до n. Значит, у нас есть, то есть всего есть n блюд, и каждый раз меню состоит из какого-то набора из этих блюд. И Петя хочет перепробовать все возможные меню, которые только можно. [ПИШЕТ НА ДОСКЕ] То есть имеется в виду, что все блюда разные, и мы перебираем все подмножества из блюд, какие только можно. Хочется узнать: сколько тогда Петя съест всего блюд за это время? [ПИШЕТ НА ДОСКЕ] [ПИШЕТ НА ДОСКЕ] Значит, я утверждаю, что это на самом деле будет вот эта формула. Давайте поймем почему. Ну смотрите. Давайте я тогда нарисую вспомогательную табличку для n = 3. [РИСУЕТ НА ДОСКЕ] Значит, у нас есть 3 блюда, и Петя хочет опробовать все возможные меню. Значит, ну давайте: первое меня — это вообще не состоит из блюд, еще есть 3 меню, которые состоят только из одного блюда, есть 3 меню, которые состоят из двух блюд. А, я промахнулся. Ага, значит, лишняя. Так, итак, значит, у нас есть всего, смотрите, 8 разборов меню, и, значит, у нас есть 0 наборов, в котором 0 блюд, значит, есть 3 набора по 1 блюду, 3 набора по 2 блюда и 1 набор, состоящий из 3-х блюд. Значит, давайте поймем, что происходит. Значит, я хочу сказать, что вот это — это в точности C из 3 по 1, потому что у нас есть, значит, мы выбираем 1 блюдо и его потребляем. Значит, дальше здесь мы съедим сколько блюд? Здесь мы съедим: значит, количество способов выбрать 2 блюда — это C из 3 по 2, и каждый раз мы съедаем по 2 блюда. Ну и здесь мы выбираем количество способов выбрать 3 блюда и съедаем 3 блюда. Значит, количество блюд, которое мы съедим — это будет ровно вот эта сумма, если написать в общем случае. Ну то есть на самом деле количество крестиков — это и есть вот эта сумма. Вот, давайте ее теперь посчитаем другим образом, а именно: докажем просто, что количество крестиков в этой таблице — это половина от общего размера этой таблицы. Ну какие у нас размеры у этой таблицы? Значит, всего здесь столбцов, их будет ровно n, а строчек будет столько же, сколько подмножеств, а подмножеств множества из n элементов — их ровно 2 в степени n. [ПИШЕТ НА ДОСКЕ] Значит, а тут у нас. Значит, всего в таблице элементов n * 2 в степени n. Докажем, что крестиков ровно половина. Ну для этого мы просто возьмем и возьмем для каждого выбора, вот, например, выберем такой набор блюд. К нему есть набор из блюд, который его дополняет до всего множества. То есть это то меню, которое состоит из блюд, которые не вошли в это. Вот, например, дополнительным для этого меню будет вот это меню, а, скажем, дополнительным для вот этого меню будет меню, состоящее из дополнительных к нему блюду: если меню состоит из первого блюда, то дополнительным для него будет меню, состоящее из второго и третьего блюда. Но если мы так для каждой пары найдем одно множество из n элементов, то есть мы, — все это 2 в степени n, — количество меню разбиваем на пары, и в каждой паре у нас ровно n элементов. Значит, всего количество блюд — будет половинка, то есть n * 2 в степени n – 1. Ну, собственно, как и утверждала наша предыдущая формула. Значит, мы получили этот ответ другим способом. Все.