Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Слова в языке
Loading...
来自 Moscow Institute of Physics and Technology 的课程
Комбинаторика для начинающих
761 个评分
从本节课中
Основные комбинаторные величины и их свойства
На этой неделе мы начнём изучать основные комбинаторные величины: введем определения размещений и сочетаний с повторениями и без. После этого мы найдём формулу для количества размещений. В приложениях вас ожидают выборы на корабле, формирование составов и сложный выбор одежды.
与讲师见面
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Так, ну, поговорив некоторое время о размещениях без повторений, да,
совершенно верно, давайте немножко поговорим о размещениях с повторениями,
это кажется абсолютно естественным.
Ну самое естественное, что бывает касательно размещений с повторениями,
— это какие-нибудь все-таки слова в каком-то языке.
И вот давайте рассмотрим, например, вот такую задачу: Маша и Петя условные,
Маша и Петя придумали некий язык,
в котором символами являются не обычные буквы, а треугольник, квадрат и круг.
Давайте я так напишу коротко: придумали язык, и в нем всего три буквы,
как бы это смешно не звучало: треугольник, квадрат и круг.
Я надеюсь, что все так это и понимали с самого начала: три буквы —
это треугольник квадрат и круг.
Вот, ну давайте прежде всего зададимся совсем простым вопросом,
это будет у нас пункт А: сколько существует,
сколько существует различных
слов из 5 букв,
которые можно составить на этом языке.
Которые можно составить, если хотите, из символов этого языка.
Ну я уж не буду это записывать, понятно,
сколько существует различных слов состоящих из 5 букв.
Ну как вы помните из лекции, собственно, размещения с повторениями,
они обозначаются сложнее, чем та формула, которая на самом деле их выражает.
То есть, конечно, нам нужно выбрать из трех возможных символов.
Вот это наше множество из 3 объектов — треугольник, круг и квадрат.
Вот из этих 3-х символов нам нужно выбрать 5, причем с возможными повторениями.
Мы можем взять 5 треугольников, например.
Мы можем взять 5 квадратов.
Или четыре квадрата и один треугольник.
Понятно, что речь идет о размещениях, причем с повторениями,
потому что буквы в словах, конечно, вполне себе могут повторяться.
У нас есть три объекта, из них мы выбираем какие угодно 5,
при этом возможны, естественно, повторы.
Даже обязательно будут повторы, если 5 из 3.
Вот, ну и понятное дело, получается вот такая штуковина,
которая, ну если угодно, по формуле из лекции,
а на самом деле просто по элементарному правилу умножения, дает нам 3 в 5 степени.
Ну и в численном выражении это есть 243.
То есть всего есть 243 различных слов из 5 букв,
которые можно составить на языке Маши и Пети.
Это совсем простой пункт.
Ну давайте зададимся вопросом, а сколько можно составить слов,
у которых, у каждого из которых, длина не больше 5?
То есть можно задействовать 5 букв для составления слова,
а можно задействовать и меньше.
Ну давайте так и напишем: сколько слов
из не более 5 букв.
Из не более 5 букв.
Ну ответ напрашивается сам собой,
мы уже знаем, сколько есть слов, каждое из которых состоит из ровно 5 букв,
дальше мы можем совершенно аналогично посчитать количество слов,
в каждом из которых ровно 4 буквы.
Понятное дело, это будет А из 3 по 4 с чертой.
Дальше мы посмотрим на слова,
которые содержат всего три буквы — это будет А из 3 по 3 с чертой.
Две буквы: А из 3 по 2 с чертой.
И одна буква — А из 3 по одному с чертой, при этом заметьте,
ну ноль буквенных слов мы все-таки не рассматриваем,
потому что как-то странно представляю себе слово, которого вообще нету.
То есть, конечно, пустые подмножества в множествах встречаются, и формально
размещение с повторениями нулевой длины, ну почему бы такое не рассмотреть, но с
точки зрения содержательной постановки нашей задачи, конечно, такого не бывает.
Поэтому писать А из 3 по 0 с чертой нелепо.
Итого мы получаем формулу такую: 3 в 5 степени, то есть 243,
плюс 3 в 4 степени, то есть плюс 81.
Итого это уже получается 325.
Плюс 3 в кубе- 27.
325 плюс 27, это — 352,
плюс 3 в квадрате — плюс девять, это 361.
И, наверное, я где-то обсчитался, потому что мне кажется,
что когда я добавлю 3 в 1 степени, должно получиться не так.
В принципе, конечно, ответ получен, зачем нам, собственно, численное выражение,
как я уже не раз говорил.
Ну ладно, давайте попробуем еще раз пересчитать, где ж это я ошибся то?
Э-э, кажется вот в этом месте ошибся: 243 плюс 81, сказал, будет 325.
Нет, конечно 324, глупости.
Да, 324 плюс 27 — это 351.
Да, всё, ошибся, да, плюс 9 — это 360,
и плюс 3, итого получаем 363.
Ну вполне милое число.
Вот, ну и давайте еще один пункт рассмотрим до кучи,
чтоб была какая-то полная картинка того, как может быть жизнь устроена.
Давайте посчитаем, сколько можно составить слов из
не более 5 букв,
из не более 5 букв,
если на первой позиции обязательно стоит треугольник.
Если первая буква в каждом из этих слов, если первая буква —
это обязательно треугольник.
То есть вот нас интересуют не все возможные слова длины 5,
а только те слова длины 5, в которых первая буква треугольник.
Тут есть некая своя специфика, которую мы сейчас отразим.
Смотрите, ну все, вот у нас есть первая буква треугольник,
она застолблена, и здесь остается 4 позиции,
на каждую из которых мы по прежнему можем выставлять все, что угодно.
Хоть треугольник, хоть круг, хоть квадрат.
Таким образом А из 3 по 4 с чертой, это количество способов составить
вот здесь вот четырехбуквенное слово, так чтоб в сумме получилось пятибуквенное.
Дальше мы можем ставить не 4, а 3, потому что нас интересуют слова
длины не более 5, то есть у нас будет получаться А из 3 по 3 с чертой,
дальше мы можем ставить не 3, а 2, будет А из 3 по 2 с чертой,
можем ставить одну, это будет А из 3 по одному с чертой, ну а можем,
в чём специфика то этой ситуации, можем вообще ничего не добавлять.
И ведь получится то на выходе не пустое множество, потому что треугольник все-таки
это первая буква, и она останется, такое однобуквенное слово, союз какой, да?
Вот, то здесь надо еще добавить А из 3 по нулю с чертой,
ну то есть просто 3 в 0 степени.
Итого мы получим 3 в 4-ой, плюс 3 в кубе,
плюс 3 в квадрате, плюс 3 в первой, плюс 3 в нулевой.
Ну и давайте опять попробуем не обсчитаться, здесь у нас стоит 81 плюс
27 — это 108, плюс 9 — это 117,
плюс 3 — это 120 и плюс 1 — это симпатичная 121,
которая является точность в точности одной третью от ответа в пункте В.
Вот такая вот милая задачка.
