Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Число сочетаний с повторениями. Пример с сортами пирожных
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Комбинаторика для начинающих
790 оценки
Из урока
Сочетания с повторениями и без
Продолжая тему прошлой недели, мы найдём формулы для числа сочетаний с повторениями и без. Кроме того, мы обсудим тяжёлую работу биологов, обмен монет нумизматов, подберём красивый букет и выберем группу альпинистов для похода.
Познакомьтесь с преподавателями
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Вот, и теперь самая, так сказать, на закуску нетривиальная,
самая интересная про что я сейчас немножко поболтаю,
потом аккуратно докажу — это формула для числа сочетаний с повторениями.
Вот тут есть некоторые тонкости, которые придется преодолевать.
Ну те слушатели, которые когда-то с этим сталкивались,
они конечно мой пафос не прочувствуют наверное, они с этим сталкивались,
и для них уже это не является такой красотой необыкновенной.
Ну вот а те слушатели, для которых это все совсем в новинку, я думаю,
что они может быть даже получат некий катарсис.
Конечно, я уже так уработался с людьми,
которые вот это вот знают там вообще всё, ой,
какой там катарсис, да это — триф, мне скажут.
Ну извините, я не сноб.
Я понимаю, что есть люди, для которых это триф, а есть люди, для которых это нечто
абсолютно новое и катарсис можно получить и в этом месте тоже.
Значит, формула такая.
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 сочетаниями без повторений.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
