Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Основные комбинаторные величины
Loading...
Do curso por Moscow Institute of Physics and Technology
Комбинаторика для начинающих
736 classificações
Na lição
Основные комбинаторные величины и их свойства
На этой неделе мы начнём изучать основные комбинаторные величины: введем определения размещений и сочетаний с повторениями и без. После этого мы найдём формулу для количества размещений. В приложениях вас ожидают выборы на корабле, формирование составов и сложный выбор одежды.
Conheça os instrutores
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Вторая тема, которую мы сегодня начнем изучать, – это основные
комбинаторные величины.
Величины, относящиеся к перечислению объектов.
Основные комбинаторные величины.
Ну эти комбинаторные величины, на самом деле, очень естественным
образом связаны с организацией выбора объектов внутри какого-то множества.
Поэтому давайте действовать следующим образом: пусть,
[ШУМ] как обычно, нам дано
какое-то множество объектов, естественно, конечное, которое, как обычно же,
обозначается A и состоит из элементов объектов a1, ..., a с индексом n.
Вот дано такое множество.
Давайте подумаем...
Представляйте себе все время про себя множество букв русского алфавита.
Так будет удобнее.
Значит, давайте, – ну я тоже буду к этому апеллировать, конечно, – давайте подумаем,
как именно можно извлекать объекты из этого множества?
Ну как можно, например, извлекать объекты из множества букв русского алфавита?
Ну давайте, действительно, давайте начнем с примера.
Так, может быть, просто будет понятнее,
чтобы не рассказывать сразу абстрактную теорию, а пояснить на примере то,
что может возникнуть, коль скоро мы осуществляем какой-то выбор.
Вот давайте на примере, у нас опять A состоит из букв русского алфавита.
Я уж наличие «ё» подчеркивать не буду, мы с вами помним, что букв 33 штуки.
Что можно с этими буквами делать?
Ну можно представить себе,
что каждая из этих букв нарисована на некоторой карточке.
Дайте я прям, как дети играют, да.
Или на кубике.
Каждая буква нарисована на карточке.
Вот одна буква «а».
Вот одна буква «б».
И так далее.
Вот буква «я».
Эти все карточки там как-то перемешаны, заброшены в коробку,
лежат там себе, если хотите, перевернутым образом.
Такой фокус можно поставить какой-нибудь.
И вот мы запускаем пригоршней пригоршней запускаем руки в эту коробку,
в которой лежат наши карточки.
Как-то это даже называлось в старые времена, типа «разрезная азбука».
Что-то такое.
Вот, ну неважно.
Значит, запускаем в эту коробку руки и пригоршней извлекаем
некоторое количество букв.
Значит, один вариант, первый вариант, который я только что озвучил, – это,
действительно, взять и пригоршней зачерпнуть буквы.
Давайте я пока буду неформален максимально, я же примеры рассматриваю,
потом мы это все аккуратно формализуем.
Первый вариант, – в кавычках, конечно, это все, потому что это просто призвано
как-то промотивировать слушателя понимать, что же, что же на самом деле происходит,
– значит, зачерпнуть пригоршней некоторое количество букв.
Ну давайте, я не знаю, k букв,
где k – это какое-то число в пределах от 1 до 33.
Ну просто мы не можем выбрать больше букв при таком подходе,
нежели их всего есть в нашей коробке.
Либо мы вытаскиваем вообще все, либо мы вытаскиваем какие-то 32,
либо мы вытаскиваем там одну букву.
В любом случае вот эта k, которое мы вытаскиваем,
оно где-то в пределах от 1 до 33.
То есть, ну, короче говоря, мы зачерпываем пригоршней и получаем такую кучку букв.
Получаем такую кучку букв.
Ну представим себе, что, скажем, для примера,
вот совсем уж специального примера, k = 7.
Ну так вот захотелось нам вытащить 7 букв.
Вытащили пригоршней, и оказалось,
что это буквы такие: л, я,
г, у, ш, к, а.
Повторяю, мы же их ни в коем случае не последовательно выбирали,
мы их зачерпнули пригоршней.
То есть я просто для удобства вашего восприятия написал их в таком порядке,
чтоб порадовать вас появлением еще одного любимого мною животного.
Если вы помните, кроликов люблю, вот еще лягушек.
Но это пригоршня.
То есть буковки лежат в каком-то хаотическом порядке.
Они могут лежать и как-нибудь вот так: ш, я, л, г, у...
Какие тут нам еще?
к, а где-нибудь вот здесь.
Они просто перемешаны.
Так, их не хватает?
Нет, все правильно.
1, 2, 3, 4, 5, 6, 7.
То есть это все наши 7 букв.
Вот они пригоршней зачерпнуты лежат на ладони, как карточки просто.
Вот.
То есть из этой кучки можно еще составить кучу разных слов,
потому что помимо лягушки, наверное,
можно упорядочить эти буквы и как-нибудь по-другому, скажем,
гуляшка или ялгушка, или еще что-нибудь в таком духе.
То есть вот этот вариант он не учитывает ни в коем случае порядка букв, не говорит
ни о каких конкретных словах, а он говорит лишь о том, что мы зачерпнули пригоршней и
получили кучку букв, из которых дальше еще можно что-то составлять.
Вот это один вариант.
Второй вариант,
[ШУМ] способ,
второй способ, второй вариант выбора букв, ну скажем,
из множества букв русского алфавита, да, он другой.
Вот лежат те же самые карточки внутри той же самой коробки.
Но мы теперь не пригоршней их зачерпываем, а начинаем их извлекать последовательно.
Извлекли одну букву – положили перед собой.
Извлекли вторую букву – положили вслед за первой.
Извлекли третью букву – положили вслед за второй.
И так далее.
Так, покуда не извлечем k букв, ну или скажем 7 букв,
если говорить о совершенно конкретном примере.
Последовательно
извлекаем буквы
из коробки,
буквы из коробки, покуда не извлечем их k штук.
Покуда не извлечем их k штук.
И получаем на выходе вполне конкретное слово.
Не кучку из букв, которую дальше можно еще как-то по-разному упорядочить,
а вполне конкретное слово.
Получаем на выходе на
выходе слово из k букв.
Например, лягушка.
Или, например, гуляшка.
То есть, с точки зрения первого способа выбора,
лягушка и гуляшка – суть одно и то же, это одна и та же кучка букв, но с точки зрения
второго варианта выбора, лягушка и гуляшка – это разные вещи, это разные слова.
Чего не хватает?
Чего явно не хватает в рамках вот этих двух вариантов?
Ну особенно это видно во втором варианте.
Особенно очевидно это во втором варианте, что чего-то не хватает.
А вот чего!
Лягушка, замечательным образом, состоит из разных букв русского алфавита,
а вот любимый кролик – другой любимый зверь – он состоит из,
вообще-то, иногда совпадающих букв.
У него два раза повторяется, как минимум, буква «к».
Ну да, другие буквы вроде не повторяются, а «к» повторяется дважды.
И что это не слово что ли?
Но ни в рамках первого варианта,
ни в рамках второго варианта мы слово «кролик» не получим.
Даже если зададим наше вот это k (количество букв,
которые мы хотим извлекать) равным 6.
Кролик он из 6 букв состоит.
Тем не менее как-то вот кролику не посчастливилось попасть ни в этот ящик,
– если говорить, так сказать, с аллюзией на принцип Дирихле, – ни в эту клетку.
Кролик как-то выпал из нашего рассмотрения.
А все дело в том, что и в этом подходе,
и в этом подходе мы требовали действительно различия букв.
То есть либо зачерпывали их пригоршней из коробки,
в которой на карточках были написаны разные буквы,
либо последовательно извлекали их из такой же коробки.
Ну так представьте себе теперь, что у вас в коробке лежит не 33 карточки,
на каждой из которых написана своя отдельная буква русского алфавита.
Представьте себе, что в вашей коробке лежит бесчисленное множество карточек.
Такая божественная коробка, которая содержит бесчисленное множество карточек.
Есть бесчисленное множество карточек, на которых написана буква «а»;
бесчисленное множество карточек, на которых написана буква «б»; бесчисленное
множество карточек, на которых написана буква «ё» и так далее вплоть до буквы «я».
То есть у вас есть 33 бесчисленных множества,
и все они запихнуты в эту божественную коробку.
И вот теперь из этой божественной коробки вы можете, опять же,
двумя способами извлекать наборы букв.
Поэтому возникает третий вариант.
Зачерпнуть пригоршней
k букв из божественной коробки.
Зачерпнуть пригоршней
k букв,
где k – какое-то конкретное число, из..
божественной коробки, в которой бесконечно много букв каждого вида.
И четвертый вариант –
последовательно извлекать k букв из божественной коробки.
Последовательно друг за другом
извлекать k
букв из божественной коробки.
[ПИШЕТ НА ДОСКЕ] Вот.
Все четыре основных варианта, с помощью которых можно,
вообще, составлять разные комбинации.
Если абстрагироваться теперь от ситуации с буквами и перейти к
все-таки более общей ситуации с произвольными объектами, то, я надеюсь,
слушатели понимают, что ничего не меняется.
Мы просто на карточках, которые, надеюсь, им наглядно как-то показывают,
как с этим всем работать, пишем не буквы от А до Я,
а пишем обозначения этих объектов a1, ..., an.
А уж какова природа этих объектов – это могут быть люди,
в аудитории сидящие; это могут быть какие-нибудь детали, которые производятся
на определенном производстве; это могут быть автомобили – все что угодно,
что вы хотите использовать для ваших исследований.
Короче говоря, короче говоря,
если у нас все-таки есть абстрактное множество
объектов, то в случае первого варианта,
когда мы из него пригоршней зачерпываем k различных букв,
в случае первого варианта мы говорим о k-сочетаниях,
k-сочетания без повторений,
k-сочетания без повторений.
И вот слово «сочетание», вот это слово «сочетание»,
оно подчеркивает то обстоятельство, что мы выбираем пригоршней.
Сочетание – значит пригоршней, значит порядок букв,
порядок объектов внутри сочетания нас не беспокоит.
Важно, как они сочетаются, но не важно,
как они последовательно друг за другом размещены.
А то что «без повторений» – это вот то, что мы каждую букву, каждый
объект записали на отдельные карточки, и коробка у нас обычная, а не божественная.
Соответственно, второй вариант в общем
случае называется k-размещением без повторений.
Слово «размещение» подчеркивает, что нам уже важно,
как друг за другом мы последовательно разместили эти объекты.
У нас получается такое как бы слово из этих объектов, последовательность из них.
...без повторений k-размещений, но по-прежнему без повторений, потому
что мы по-прежнему извлекаем эти объекты из обычной коробки, а не божественной.
И наконец, третий и четвертый варианты, они по вот этим
первым словам совпадают с вариантами соответствующей четности, то есть третий
вариант – это то же самое, что первый; четвертый – это то же самое, что второй.
А вот здесь вместо «без повторений», мы сейчас напишем «с повторениями».
То есть третий вариант – это k-сочетания с повторениями.
k-сочетания с повторениями.
[ПИШЕТ НА ДОСКЕ] А
четвертый вариант – это k-размещения с повторениями.
Так вот они называются...
Вариант – это k-размещения, k-размещения с повторениями.
[ПИШЕТ НА ДОСКЕ] Давайте,
наверное, введем обозначения для количества способов
осуществить выбор в рамках каждого из вариантов.
Ведь у нас всего изначально есть n объектов.
И нас, по идее, интересует: а сколькими способами мы можем извлечь, например,
из этого множества k-сочетаний без повторений?
Или сколькими способами мы можем извлечь из этого
множества k-размещений без повторений?
И так далее.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
