Вот, и теперь самая, так сказать, на закуску нетривиальная, самая интересная про что я сейчас немножко поболтаю, потом аккуратно докажу — это формула для числа сочетаний с повторениями. Вот тут есть некоторые тонкости, которые придется преодолевать. Ну те слушатели, которые когда-то с этим сталкивались, они конечно мой пафос не прочувствуют наверное, они с этим сталкивались, и для них уже это не является такой красотой необыкновенной. Ну вот а те слушатели, для которых это все совсем в новинку, я думаю, что они может быть даже получат некий катарсис. Конечно, я уже так уработался с людьми, которые вот это вот знают там вообще всё, ой, какой там катарсис, да это — триф, мне скажут. Ну извините, я не сноб. Я понимаю, что есть люди, для которых это триф, а есть люди, для которых это нечто абсолютно новое и катарсис можно получить и в этом месте тоже. Значит, формула такая. C из n + k − 1 по k. То есть оказывается, что число сочетаний без повторений, вот это вот оно помогает посчитать число сочетаний с повторениями. Вот мы хотим найти, сколькими способами можно составить кучку из вообще говоря, повторяющихся объектов. Помните, как я в прошлый раз объяснял, что такое сочетание с повторениями, на сочетание с повторениями? Что у нас есть неограниченное количество букв A1, есть неограниченное количество букв A2, есть там и так далее, неограниченное количество букв A с индексом n. И вот из этого огромного бесконечного такого божественного ящика, как я говорил в прошлый раз, в нем же бесконечно много каждого типа букв, мы извлекаем пригоршней k штук. То есть мы можем случайно зачерпнуть k букв, которые все будут равняться A1. А можем случайно зачерпнуть k букв, которые все будут разными, если k меньше, чем n, меньше, либо равняется n. Но если k больше, чем n, то точно какие-то буквы уже начнут совпадать, какие-то объекты будут одинаковыми. Вот сколькими способами можно составить разные пригоршни, то есть пригоршни, в которых содержатся по сути разные количества вот этих самых объектов. Нас видите, сейчас не интересует порядок следования объектов друг за другом, а нас интересует только состав пригоршней. Ну знаете как, вот чтоб совсем было понятно, о чем пойдет речь, чтобы ни в коем случае не было, не было непонятно на начальном этапе, что именно мы доказываем. Типичная задача такая. Вот кто-нибудь, неважно, человек пришел в магазин, пришел в магазин ну магазин он не вполне божественный, конечно, но тем не менее, значит он пришел в магазин и в магазине есть несколько видов пирожных. Вот как написано в классической книжке Виленкина, например, замечательной книжке по комбинаторике. Есть несколько видов, несколько сортов пирожных, там есть: эклеры, есть, не помню уж точно как он там их называет, наполеоны, есть песочные и есть еще какие-нибудь, неважно. Вот есть 4 сорта пирожных. И вот человеку надо купить 20 пирожных. Сколькими способами он может это сделать? Вот это типичная задача про сочетание без повторений, ой, извините, с повторениями. Это типичная задача про сочетание с повторениями. Четыре сорта пирожных и надо купить 20 штук. Речь же не идет о том, в каком порядке их потом сожрать. Конечно, если бы об этом речь шла, тогда появились бы размещения с повторениями. Но порядок нас не интересует. Нам просто нужно их в пакет сложить и домой отнести. Вот сколькими способами можно купить 20 пирожных, так что нас не интересует, как они расположены друг за другом, а нас интересуют только виды пирожных, вот в этом множестве из 20 объектов из 20 пирожных. Вот это типичная задача про сочетание с повторениями. Что кстати мы считаем, вот если 4 сорта пирожных, да, 4 сорта. Давайте я все-таки напишу, чтобы оно как-то отразилось максимально аккуратно: 4 сорта пирожных и нам нужно 20 штук. Нам только важно, сколько из этих 20 первого сорта, сколько из этих 20 второго сорта, сколько третьего, сколько четвертого, а порядок, повторяю, никакого значения не имеет, потому что речь не идет о том, в каком порядке их съесть. Вот ну понятно, у нас есть всего 4 объекта. Первый объект — это пирожное эклер. Второй объект — это пирожное наполеон. Третий объект — песочное и четвертое еще какое-то. Вот поэтому нам нужно из этих четырех объектов составить кучку, в которой будет всего 20 объектов. Видите, никто не сказал, что n должно быть обязательно больше, чем k коль скоро мы здесь рисуем черточку. Потому что объекты могут повторяться. Магазин, повторяю, конечно не является божественным. То есть в нем не то, чтобы неограниченные запасы этих самых пирожных, ну уж 20 то наберется каждого сорта, уж 20 эклеров там есть, 20 наполеонов там точно есть. Поэтому любой состав допустим. И вот нам нужно посчитать, что такое С из 4 по 20, виноват, с чертой конечно. То есть нас интересует именно сочетание с повторениями в данной задаче. Вот я утверждаю, что на самом деле в этой задаче, вот в этой задаче про эклеры и прочее, ответ будет именно такой, как я здесь написал. То есть это будет С из 23 по 20, вот такой вот ответ получается. Ну и дальше это можно расписать конечно, будет 23! поделить на 20! и на 3! Ну то есть можно еще раз сократить 23! и 20! у нас останется 23 на 22 на 21. 3! — это 6, поделить на 6. Ну можно даже попробовать сосчитать: 21, поделенное на 3 — это 7, 22 пополам — это 11, остается 77, ну 23 на 77, давайте друзья я не буду сейчас заниматься арифметикой. Я все-таки не обладаю супер способностями по устному счету, но понятно, вот посчитали количество способов по-разному составить пакет с нашими покупками. Но как посчитали? Пока лишь уверовав в то, что вот эта теорема справедлива. Так вот сейчас, через некоторое время, я вам докажу эту теорему, но прежде, чем ее доказать, я вам расскажу некий, ну, я не знаю, анекдот или не анекдот. Но это в общем, реальный случай из жизни. Я вообще стараюсь всегда на лекциях рассказывать какие-нибудь забавные анекдоты. Вот мне нужно доказать эту теорему, да. Я ее буду доказывать с помощью следующей древней идеи. Значит анекдот состоит вот в чем. Есть такой замечательный венгерский комбинаторщик Петр Франкл — это в общем классик современной комбинаторики придумавший очень-очень много всего, доказавший кучу результатов, сейчас уже человек, безусловно, не молодой, ему там 60 с чем-то лет. В свое время он был победителем международных олимпиад по математике ну в общем, совершенно выдающийся человек, вот он приезжал к нам в Москву по моему приглашению с лекцией в Яндексе. Ну в Яндексе он читал правда совершенно ни про какой не про Интернет, а про комбинаторику в духе той, о которой я здесь рассказываю. Вот просто полтора часа рассказывал о некоторых красивых задачах комбинаторики, и это было исключительно круто в общем. Пришло куча слушателей, там больше 100 человек было, студентов разных, преподавателей. Ну действительно, классик приехал. Вот, человек он безусловно очень оригинальный. Дело в том, что он прославился не только отличным знанием математики, прекрасными результатами по комбинаторике, он еще прославился тем, что в какой-то момент начал жонглировать. Но он из Венгрии сначала, как я понимаю, во Францию уехал, а потом в Японию. И вот он сейчас живет в Японии и периодически занимается разными шоу на телевидении, вот. Ну он не плохо жонглирует. Лекция выглядела так. Он долго рассказывал, что-то про математику, а потом сказал: знаете друзья, я думаю, что вам так уже немножко скучно стало, что я тут жонглирую формулами какими-то. Дайте я вам чего-нибудь другое продемонстрирую. Зашел так за доску, а там доска была, за нее зайти можно было. Вот за эту доску зайти нельзя, а там стояла просто доска, так вот на колесиках. И вот он за нее зашел, а мы сначала не видели, что он за ней находится. Достал оттуда шарики и начал ими жонглировать. Это было очень забавно, вот, но анекдот не про это, анекдот не про это. В этом нет ничего такого, ну приехал замечательный математик большой оригинал, который пожонглировал не только формулами, но еще и шариками. Нет, у меня совершенно другой замысел. Вот он рассказывал значит про некоторую задачу комбинаторики. И в частности, он рассказал следующую древнюю идею, как можно доказывать равенство каких-то двух величин. Вот нам хочется доказать, что эта величина равна вот этой. Количество вот этих объектов, которые в данном случае называются сочетаниями с повторениями, равно количеству вот этих объектов, которые между прочим не являются сочетаниями с повторениями, а являются сочетаниями без повторений. Вот как доказать равенство двух таких величин, равенство двух количеств? И он стал приводить замечательный пример. Он сказал: вот древние люди они считать-то не умели. Ну может 1, 2, 3 они еще были способны, а там до сотни, до тысячи, это они считать не могли. И вот было у этих людей стадо баранов. Он даже очень забавно изобразил барана. Вот я тоже не умею рисовать. Очень забавно, что-то вот такое нарисовал. Вот я вам тоже нарисую. Вот так. Вот у них есть стадо баранов, они не знают сколько баранов, потому что они их считать не умеют. Они количество баранов там могут обозначить какой-нибудь буквой, но они не знают, чему эта буква равна. Как же им добиться того, чтобы проверить, что выпустив с утра этих баранов из стойла на пастбище, они не утратили к вечеру баранов и когда бараны в стойло возвращаются, вернулось столько же баранов, сколько было изначально. Считать-то они не умеют. Они же не могут, выпуская каждого очередного барана, сказать: вот первый вышел, вот второй вышел там, вот третий, а вот 157 например. Да? Этого они не могут. Они считать не умеют. Но им надо вечером убедиться в том, что вернулись все бараны. Как это сделать? Ну очень просто. У них есть куча камней, которые тоже естественно никак не пронумерованы, потому что чисел они не знают. Есть куча камней. Вот такая вот куча, где лежат камни. И когда очередной баран выходит из стойла, они берут очередной камень из этой кучи и перекладывают в другую кучу. Вот так вот, и так до тех пор, пока все бараны не выйдут. Но когда все бараны выходят, естественно вот эти все камни оказываются в новой куче. Когда бараны возвращаются, происходит обратный процесс. Совершенно не важно, какой камень какому барану в данном случае соответствует, важно только, что когда приходит очередной баран назад, мы уже из этой второй кучи перекладываем очередной шарик, очередной камушек в первую кучку. И таким образом, мы убеждаемся, что баранов вернулось столько, сколько нужно. А если камень остался или несколько камней осталось, ну значит кто-то спер нашего барана или он сам куда-нибудь провалился, не дай Бог! Вот такая вот идея. В математике эта идея, на самом деле, имеет название. Это называется взаимно-однозначное соответствие. То есть мы хотим между вот этим множеством объектов, множеством k сочетаний без повторений, ой извините, с повторениями, и вот этим множеством объектов, то есть множеством k сочетаний без повторений, установить взаимно-однозначное соответствие. То есть сделать как с баранами и с камнями. Это было довольно забавно, когда он это рассказывал. Дело в том, что анекдот в чем состоит? Забавно то, что он нарисовал вот эту тварь, а он рассказывать пытался по-русски поначалу и очень неплохо это делал, вот. Он нарисовал эту тварь и спросил: вы знаете, я забыл, как это животное называется по-русски. И неприятность состояла в том, что кто-то решил, что это козел. В общем, было сказано, что это козел. Он некоторое время называл его козлом. Это было довольно забавно. Ну все-таки имелись в виду, конечно, бараны. Вот такая вот интересная история. Ну что? Значит сейчас давайте я перейду к формальному доказательству. То есть действительно буду устанавливать какое-то соответствие между барашками вот этими самыми k сочетаниями с повторениями и камнями, то есть вот этими k сочетаниями без повторений.
