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.
Ну, собственно, как и утверждала наша предыдущая формула.
Значит, мы получили этот ответ другим способом.
Все.