Как я уже говорил, доказательства, в общем-то, ничем не отличаются от того
рассуждения, которое мы только что провели в частном случае.
Ну, давайте все-таки аккуратно напишем слово «доказательство», как водится.
Пропишем все, что нам нужно.
Значит помните, у нас было тринадцать позиций,
мы из этих тринадцати позиций выбирали какие-то позиции для букв «к»,
потом из оставшихся выбирали для букв «о», и так далее.
Вот здесь то же самое.
Есть всего n позиций, из которых можно составлять
нашу последовательность, то есть на которой можно ставить наши объекты.
Ну давайте напишем, что c из n, по n1 – это количество способов,
количество способов,
выбрать позиции, выбрать позиции для,
ну букв или объектов первого типа.
Давайте.
Позиции для объектов, все-таки, – здесь у нас объекты, а не буквы...
для объектов первого типа.
После того как мы выбрали n1 позицию для объектов первого типа,
в нашем распоряжении, конечно же осталось только n − n1 позиция,
n − n1 позиция осталась в результате,
и вот на эти n − n1 позиции мы можем как угодно расставлять вторые объекты,
третьи объекты, четвертые и так далее.
Ну давайте напишем ,что c из n − n1 по n2
– это количество способов выбрать позиции.
Ну давайте для объектов напишу словами, для объектов второго типа,
хотя можно было их тоже загнать под такую черточку.
Для объектов второго типа у нас остается такое количество способов выбора.
Дальше позиции становятся еще на
n2 меньше: c из n − n1 − n2 И из них мы выбираем конечно же n3.
И я даже, наверное, не буду писать, что это значит, потому что конечно это опять
количество способов выбрать позиции для объектов третьего типа на тех позициях,
где мы еще можем в принципе их ставить.
Потому что эти забиты, эти забиты, вот осталось n − n1 − n2,
давайте ..., попробуем сообразить, какая последняя будет C.
Вот что будет аналогом того C из 1 по 1,
которое у нас возникло в примере с «комбинаторикой».
Там, если помните, в самом конце было C из 1 по 1.
Здесь будет уже, наверное не C из 1 по 1, но, тем не менее...
Так что же у нас тут получится, смотрите,
мы уже выбрали позиции для объектов первого типа,
их было n1 штука, выбрали n2 позиции для объектов второго типа,
ну выбрали n3 для объектов третьего, давайте посмотрим и так далее.
А какие объекты мы расставили в предпоследнем шаге, так сказать?
У нас всего есть объектов k типов.
То есть в последней C, мы должны расставлять объекты k-того типа.
Это значит, что на предыдущем шаге мы уже задействовали объекты k −1 типа.
Ну их у нас n с индексом k −1.
И на них мы задействовали, на вот эти вот объекты k −1 типа.
разумеется n с индексом k −1 позиции.
Потому что ровно столько объектов k −1 типа имелось в нашем распоряжении и все
их мы должны были задействовать И так n1, n2,
n3, ..., nk−1, – это мы удалили из нашего n.
А выбрать нам нужно позиции для объектов k-того типа.
То есть n с индексом k.
Ну вот видите, если бы я не рассказывал про комбинаторику, это наверное было
бы очень страшно, а с примером понятно, что в общем, что-то такое и происходило.
Более того, давайте вспомним, что у нас n ведь,
это есть n1 + … + nk, но это просто по определению,
мы так расклассифицировали изначально все наши объекты.
Столько первого типа, столько второго, столько k-того: в сумме как раз столько,
сколько есть всего объектов.
Поэтому если мы сейчас перекинем в левую часть этого равенства все слагаемые,
кроме последнего.
Вот так: −n1 − … − n с индексом k − 1,
то с одной стороны мы получим то, что у нас написано вот в этой C снизу,
а с другой стороны, разумеется, мы получим n с индексом k.
То есть, понятно, что эта вот C длиннющая,
страшнющая – это есть ничто иное, как C из n с индексом k.
по n с индексом k, то есть единица, но это само по себе не удивительно, потому что
после того как мы выбрали позиции для всех типов объектов, кроме последнего,
для последнего уже остается однозначно куда расположить эти объекты.
Однозначно вот она единица и вылезла, но там была C из 1 по 1, потому что nk = 1,
там кратность соответствующей буквы, я не помню какой, наверное «р», была равна 1.
Вот, ну а здесь кратность последнего объекта, она какая-то,
может быть не равная единице, но в любом случае сама C – это свидетельство тому,
что у нас просто не остается никаких вариантов для расположения последних
объектов – они загнаны в угол, так сказать.
Вот, ну понятно.
Тогда итоговое количество, то есть то,
что мы с вами обозначили P(n1,
..., nk) итоговое количество, естественно,
выражается по принципу умножения, по правилу умножения.
Ну как произведение вот этих всех C,
то есть C из n по n1 на C из n − n1,
по n2 на C из n − n1 − n2, по n3 и так далее.
Ну и давайте напишем в первоначальном виде без сокращения,
это был просто комментарий некий, а тут вот эту длиннющую штуку я напишу.
−n1 − … − nk, − первая.
По nk = … и дальше рассписываем через факториалы
также точно точно как расписывали в случае с «комбинаторикой», с примером с нашим.
Через факториал это выглядит так: n!
n1!(n − n1)!
в следующем сомножителе вот эта вот штучка (n − n1)!
оказывается в числителе.
(n − n1)!
В знаменателе n2!
(n − n1 − n2)!
Ну, давайте я уж буду максимально зануден,
чтобы всем все было сходу видно: (n − n1 − n1)!
мы делим на n3!
и на совсем длинную разность (n − n1 − n2 − n3)!
и так далее.
Ну и на конец последние сомножитель вылезает вот из этой гадости,
которую надо честно написать: (n − n1 − … − nk − 1)!
Правильно?
Дальше...
Вот здесь вот nk!.
А следующий сомножитель, это надо из n во-первых,
вычесть все вот эти вот буковки n1, nk − 1, и, кроме того, еще вычесть nk.
Но мы-то с вами знаем, что если из n вычесть сумму всех этих чисел вплоть
до nk-того, то получится просто 0.
Помните пресловутый 0!, который я,
в конце концов, при рассмотрении примера перестал вообще учитывать.
Но он уж совсем куцый, так сказать.
0! он и в Африке 0!.
Он такая единица, о которой и думать не хочется.
А почему не хочется думать?
Потому что теперь шлеп, шлеп, шлеп.
Очевидно, что это тоже шлепнется следующим.
И так они будут шлепать друг друга, пока не перешлепают вплоть до сюда.
Это вроде, как совершенно понятно.
0! мы не учитываем, а в знаменателе у нас,
извините, так и осталось как хотелось – n1!
n2!, n3!, …, nk!.
При этом в числителе выжил только n!.
То есть?
в итоге мы действительно получаем n!
поделить на n1!, n2!
… nk!
и теорема полностью доказана уже в совершенно общем случае.
Вот такая вот замечательная штуковина.
Дмитрий Ильинскийпреподаватель
Андрей Райгородскийпрофессор, доктор физико-математических наук
