В этом видео мы наконец разберемся с подсчетом числа неупорядоченных выборок с повторениями. Ну начнем мы все равно с задачи более сложной, чем в прошлый раз. Рассмотрим большие салаты. Пусть у нас теперь есть неограниченное количество помидоров, огурцов, перцев и баклажанов. И мы хотим сделать салат из семи овощей этих четырех типов. Мы при этом, опять же, не обязаны использовать все ингредиенты. Это может быть, опять же, салат из одних помидоров, но, опять же, нас интересует сколько есть разных салатов, сколько мы разных салатов можем сделать. Хорошо, мы снова можем использовать тот же самый рекурсивный подсчет. Можем перебрать разное количество, например, помидоров и разобрать сколько есть салатов при каждом варианте количества помидоров. Но вместо этого мы в этот раз сможем вывести формулу, мы просто выведем формулу для количества таких салатов. И это будет на самом деле решением задачи в общем виде. Хорошо, давайте перейдем к решению. Помидоры, огурцы и перцы изображаем так же как в прошлый раз, баклажаны изображаем вот фиолетовым цветом, и вот у нас салат размера семь, и давайте перейдем к решению, и вспомним еще раз, ну вот есть произвольный салат — той же идеей воспользуемся. Порядок здесь не важен, порядок, в котором мы добавляем ингредиенты в салат, нас не интересует, поэтому давайте упорядочим удобным способом и сначала поместим помидоры, затем перцы, затем огурцы, затем баклажаны — ну это так же, как в прошлом нашем решении прошлой задачи. Хорошо, вот наш салат, и давайте с ним разбираться. Первая идея: чтобы указать конкретный салат, достаточно указать, где сменяются ингредиенты. То есть вот у нас есть ряд из ингредиентов. Мы их упорядочили, достаточно просто указать места, в которых они сменяются. Скажем, мы можем подписать, что вот в этом месте сменяются помидоры — помидоры слева от этой стрелки, перцы — слева от следующей стрелки, огурцы — слева от следующей стрелки, ну а дальше, очевидно, баклажаны. Хорошо, после этого мы можем просто стереть цвета ингредиентов, то есть цвета нам уже больше не нужны. Вот даже не зная цветов, мы можем восстановить какой был салат, просто все подписано. Хорошо, идея следующая: даже текстовое описание нам не нужно. Мы знаем, что помидоры идут первыми, затем идут перцы, потом огурцы, потом баклажаны. И подписывать стрелки на самом деле необязательно, мы знаем, что помидоры идут левее первой стрелки, дальше идут перцы, перед третьей стрелкой идут огурцы, а в конце — баклажаны. Дальше, следующая идея: мы можем указать места смены ингредиентов перегородками. То есть, вместо того чтобы проводить туда стрелку, мы можем просто поставить там некую перегородку. Ну давайте вот так их, например, обозначать, просто мы стрелки заменили на перегородки. И наблюдение теперь такое — мы все еще можем восстановить салат. Помидоры расположены слева от первой перегородки, дальше идут перцы, потом идут огурцы, в конце идут баклажаны. То есть по-прежнему вот из этой картинки мы можем восстановить наш салат. Хорошо, давайте проверим, что у нас во всех случаях все работает. Ну например, вот что если в нашем салате не было перцев. Получится ли такая какая-то подобная картинка вот для этого случая? Ну на самом деле получится, тут нет проблем, просто между перегородками ничего не будет, будет какой-то такой салат. Вот, например, в этом примере у нас два помидора, перцев — ноль, дальше, три огурца и два баклажана. То есть ничего страшного не произойдет, этот случай мы тоже покрываем нашим анализом. Хорошо, теперь, следующее наблюдение: собственно, наших салатов столько же, сколько есть способов поставить вот на этих позициях перегородки. То есть, чтобы указать конкретный салат, вот среди этих десяти элементов нужно указать три позиции, куда мы поставим перегородки и поставить их туда. Как только мы поставим перегородки, салат однозначно восстанавливается, как мы говорили. Перед первой перегородкой у нас будут помидоры, дальше перцы, огурцы и так далее. То есть на самом деле у нас теперь есть десять позиций, и нужно выбрать для них три перегородки, ну а это просто сочетание. У нас есть десять элементов, нужно выбрать из них три без повторения, то есть перегородки должны стоять в разных местах. И получается, что ответ к нашей задаче: c из 10 по 3 = 120. Не 120 факториал, а я вот здесь цветом постарался выделить, это 120! Так что ответ к нашей задаче — 120, есть 120 разных салатов и с вот такими вот ограничениями, которые мы рассматривали в нашей задаче. Хорошо, давайте вспомним как это получилось, как мы пришли к этому. У нас было довольно много разных идей, давайте основные из них снова перечислим. Идея первая: надо упорядочить салат удобным способом. Порядок не важен, давайте упорядочим салат так как нам удобно: сначала помидоры, потом перцы, огурцы и баклажаны. Дальше: салат определяется разделителями, то есть мы можем стереть цвета ингредиентов и поставить разделители, просто тогда они будут говорить нам где изменяются ингредиенты в нашем упорядоченном салате, то есть, по сути, мы упорядочили салат и пометили места, где сменяются ингредиенты. Дальше, следующая идея, которой мы воспользовались: мы поместили разделители в один ряд с ингредиентами — и это довольно важная идея. То есть ничего, по сути, не изменилось, это все те же самые разделители, но мы выписали их вместе с ингредиентами в один и тот же ряд. И после этого нам что осталось делать? Нам, на самом деле, в получившемся списке нужно просто выбрать места для разделителей, то есть список стал длиннее, потому что мы в тот же ряд поставили, в ряд с ингредиентами поставили разделители, но теперь в этом ряду если выбрать три места для разделителей, то все получится — получится конкретный салат. А это уже старая задача, то есть мы знаем сколькими способами можно выбрать три позиции для разделителей в нашем списке. Хорошо, в общем виде все то же самое, и мы получаем такую общую формулу. Если нас интересует число сочетаний с повторениями, число выборок неупорядоченных с повторениями размера k из n возможных объектов, то есть каждый элемент выборки выбирается из n возможных объектов, повторения разрешаются, порядок не важен, то есть (c из k + n − 1 по n − 1) возможных способов построить такую выборку. Здесь, вот в этой общей постановке размер выборки — это размер салата, то есть k — это размер салата, количество овощей, которое мы выбрали в наш салат. Число объектов — это число ингредиентов, мы выбираем из n объектов, в салатах мы выбирали из n возможных ингредиентов, n — это здесь ингредиенты. И работает абсолютно то же самое рассуждение, то есть просто ровно то же самое рассуждение, которое мы провели для четырех ингредиентов и салата размера семь здесь полностью проходит. Давайте только проанализируем почему получаются такие числа, почему там k + n − 1 и n − 1. Ну n ингредиентов означает, что нам в нашем списке салата упорядоченного потребуется n − 1 разделитель. Чтобы указать, где расположены ингредиенты, где они начинаются и заканчиваются, нужен n − 1 разделитель. И когда мы поставим n − 1 разделитель в ряд, то нам потребуется выбрать n − 1 объект, чтобы пометить их разделителями из k + (n − 1) объекта. То есть у нас было k овощей в салате, мы добавили в список n − 1 разделитель, и теперь из этого длинного списка нам нужно выбрать позиции для n-1 разделителя, поэтому получаются вот такие числа. Хорошо, давайте вспомним еще раз, что мы разбирали в этом уроке. Мы рассматриваем выборки k элементов из n возможных вариантов, и у нас была картинка с четырьмя возможными постановками, упорядоченными и неупорядоченные выборки, и с повторениями и без, и вот мы заполнили последнюю клеточку в левом нижнем углу — сочетания с повторениями, то есть неупорядоченные выборки с повторениями. Ответ тут получился c из k + n − 1 по n − 1. Кстати, видно что тут нам тоже пригодились бы номинальные коэффициенты. Оказалось, что ответ выражается через них. [МУЗЫКА]
