Значит, давайте я просто напомню, что бином Ньютона, он пишется вот так: x + y в n-ой степени — это есть сумма по k от 0 до n C из n по k * x в степени k * y в степени n − k – называется бином Ньютона. И в честь этого C, которые мы до сих пор называли, – правильно, конечно, называли, – числами сочетаний, их же можно называть и биномиальными коэффициентами. Значит, называются вот еще биномиальными коэффициентами. Потому что они выступают в роли коэффициентов в биноме Ньютона. Числа сочетаний и биномиальные коэффициенты — это одно и то же. Вот. Ну наверное, действительно, доказывать это не надо. А давайте мы еще одну задачку решим, которая позволит нам обобщить этот факт на более широкую ситуацию. Вот такая вот задача. Смотрите. Есть n1 символов букв a1. Есть одна штука символов a1 в нашем распоряжении. Дальше есть n2 символов a2 ,опять же, в нашем распоряжении. И так далее. Давайте, есть nk символов ak. И наконец, давайте обозначим через n сумму вот этих количеств n1 +... + nk. Это общее количество символов, которые имеются у нас в нашем распоряжении. Спрашивается: а сколько можно составить различных слов, имея на руках такие данные? Я имею в виду различных слов длины n? То есть самых длинных какие бывают. Ну давайте я это напишу. Сколько, в принципе, существует различных слов, различных слов, длины n, которые можно составить, имея на руках ровно n вот таких вот повторяющихся символов? Вы знаете ответ? Да, ну наверное не только вы. Да? Кто-то еще знает? Вот видите? Довольно многие знают ответ. Это хорошо! Но не все его знают, поэтому я сейчас его напомню. Значит ответ — это теорема, которая утверждает следующее. Давайте через P(n1, ..., nk) обозначим искомое количество, то есть вот это вот — это и есть число различных слов длины n. Так вот оно равно по теореме: n! / (n1! n2!... nk!) Вот такая вот красивая простая формула, которая, если приглядеться, напрямую обобщает формулу биномиального коэффициента. Ну тоже мы факториал делим на произведение факториалов. Как это доказывается? Ну это интуитивно, в общем, понятно. Правда же? Что есть всего n! перестановок, но если мы между собою переставляем буквы a1, перестановки же не меняются. Если мы между собой переставляем буквы a2, перестановки тоже не меняются. Ну вот интуитивно понятно, что надо поделить. Давайте я чуть более строго скажу. Мне нравится вот так это сформулировать. Сейчас будет более аккуратное доказательство. Но интуитивно понятно, понятно сразу. Итак! Посмотрите, как можно посчитать количество слов, которое нас интересует? Можно как с C, да, но можно вот так. У нас есть всего n позиций, на которые мы с вами будем сейчас расставлять буквы, чтобы сформировать слово. Есть всего n позиций. Ну давайте из них выберем произвольные n1 позиции. Произвольные совершенно. Ну, естественно, кучкой, поэтому C надо брать. Произвольные n1 позиции, на которые расставим буквы a1. В каком порядке – совершенно неважно. Они ж все одинаковые. Значит, вот выберем столькими способами места, на которые мы поставим буквы a1. А теперь смотрите: ну если эти места зафиксированы, то сколько у нас осталось свободных мест? n − n1, конечно! У нас осталось n − 1 свободных мест, на каждое из которых мы, например, можем размещать буквы a2. Ну естественно, вариантов выбрать позиций для букв a2 у нас C из n − n1 по n2. Совершенно аналогично. Дальше буквы a3 мы можем размещать вот столькими способами: умножить и так далее. Так. Последняя C как выглядит? Вопрос. Контрольный. Так, ну Cn − n1 − n2 −... − … последнее что вычитается? nk − 1, совершенно верно! И берем мы, соответственно, по n с индексом k. Берем мы, соответственно, по n с индексом k. Ну я хочу заметить, что вот эта вот разность-то чему равна по определению? nk! То есть это C из nk по nk. Ну и это, в общем, довольно естественно, потому что если мы расставили все буквы, кроме последней, то для последней буквы у нас просто абсолютно однозначно уже осталась просто nk-тая позиция и все. Поэтому здесь, конечно, должен быть сомножитель единицы и мы видим, что он получился. Ну а дальше расписываем по формуле через факториалы. n! / n1! (n − n1)! * (n − n1)! / n2! * (n − n1 − n2)! *... ой, что это я такое огромное нарисовал! Так. (n − n... да что ж он перестал писать-то, окаянный! вот гад! Так. Вот видите, что происходит? Он убивает.. Так... (n − n1 −... − nk − 1)! / nk! (n − n1 −... − nk)! Вот так. Ну и дальше никакой, конечно, не катарсис, а просто очевидно все. Шлеп, шлеп, шлеп, шлеп. Да? Да? Вот это вот тоже укокошили. По аналогии они все крест-накрест сокращаются.Так, вот это что такое? Это 0!. Вот это вот 1. Очевидно, это просто 0!. Ну и все. В числителе осталось только n!, а в знаменателе – n1!, n2!, nk! Формула доказана.