Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Пример на правило умножения
Loading...
From the course by Moscow Institute of Physics and Technology
Комбинаторика для начинающих
731 оценки
From the lesson
Правило сложения и умножения. Принцип Дирихле
Правило сложения. Правило умножения. Принцип Дирихле.
Meet the Instructors
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Вот ну а пример, который в этом месте традиционно рассматривается,
ну или Бог его знает, я во всяком случае всегда его рассматриваю,
потому что мне кажется он очень естественный, понятный.
Пример, конечно, с количеством автомобильных номеров.
Количество автомобильных номеров кажется очень уместным.
Автонобильных, нет, ну конечно — ...Мобильных, это я описался.
Количество автомобильных номеров,
которые могут возникнуть, ну скажем, в рамках одного региона нашей страны.
Ну кто ж помнит, сколько у нас сейчас регионов?
Количество меняется.
Благо еще и даже в рамках одного региона возникает куча
разных номеров этого региона.
У Москвы, я уже сбился со счета, сколько номеров региона, честно говоря.
Там какие-то 777 уже появляются, прямо какие-то портвейновые числа, я бы сказал.
Так, количество автомобильных номеров, да, но как выглядит типичный
автомобильный номер в нашей стране, если, повторяю, не учитывать номер региона?
Но это К 884 МХ, что-нибудь вот в таком духе, например.
Или там, Х 486 ВВ.
Или К 268 ОВ.
Ну и так далее, то есть у нас на первую позицию номера всегда идет какая-то
буква русского алфавита, дальше идет 3 позиции, занятые цифрами, то есть
мы находимся буквально в рамках тех примеров, с которыми до сих пор работали.
Ну и наконец, последние две позиции снова занимают буквы русского алфавита.
Вот эти три примера,
они показывают как может быть устроен наш типичный автомобильный номер, если,
повторяю, не учитывать номер региона, которых количество я все равно не помню.
Но тогда у нас получается, что вот в этом следствии мы работаем вот с чем:
А1 — это множество букв русского алфавита,
множество букв русского алфавита,
А2 — это множество цифр.
То же самое есть А3, это тоже множество цифр, конечно.
Так, ну и А4 — это тоже множество цифр, ну елки-палки, это понятно.
А4 — это тоже множество цифр, соответственно,
А5 и А6 идентичны множеству А1, то есть это снова множество букв.
Ну кто ж сказал, что множества обязаны быть различными?
Важно только то, что мы вслед друг за дружкой ставим элементы этих множеств,
а то, что элементы могут быть взяты из, по сути, одного множества,
ну вот путем такого размножения этих множеств вполне себе достигается.
Вот, и вот в этом месте прозорливые слушатели, те,
которые знают, как устроены автомобильные номера, должны меня поправить.
Дело в том, что на самом деле, конечно, множество А1, А3 и А4 — это множества,
которые состоят отнюдь не из всех букв русского алфавита.
Банальный ответ состоит в том, что, ну елки-палки, ну неужели вы
где-нибудь видели номер, на котором написана буква «Ё» там, или буква «Ы»?
Или буква «Ъ»?
Но объяснение очень простое.
Дело в том, что мы ж стали теперь открыты всему миру.
В советское время использовались вполне себе нетривиальные буквы русского
алфавита.
Но сейчас этого не происходит,
потому что наши автомобили зачастую выезжают за границу.
И считается, что использовать в рамках номеров можно только те буквы русского
алфавита, которые имеют аналоги в латинском алфавите.
То есть вы не увидите не только экзотических букв, типа «Ы» или «Ъ»,
но вы не увидите и вполне нормальных букв, казалось бы,
типа «Я», потому что «Я» не имеет никакого аналога в латинском языке.
А, вот скажем, буква «У» считается вполне уместной, потому что «У» похожа на «Y».
Вот, ну и таких букв, оказывается, всего 12 штук.
Поэтому n1, то есть количество объектов внутри множества А1,
с которым мы сейчас имеем дело, равняется n3,
равняется n4, сейчас, «n3, n4» — это не правда.
n5, n6, извините, я не туда посмотрел.
Конечно, буквы у нас в начале или в самом конце.
Значит n1 = n5 = n6 = всего лишь 12.
Из 33 букв русского алфавита есть только 12, которые имеют аналоги и в латыни тоже.
В английском, скажем, или в французском.
Так, вот их 12 штук.
Соответственно, n2, n3, n4 — это,
все-таки, любая цифра, поэтому таковых 10 штук.
И вот если воспользоваться нашим следствием, то получается,
что в рамках одного номера региона, повторяю, не в рамках одного региона,
а в рамках одного фиксированного номера региона, например, 197 московского,
да, существуют всего… сколько вариантов составить номер?
Значит, мы друг за другом, последовательно располагаем буквы и цифры,
количество которых здесь вполне себе указано.
Ответ, естественно, получается согласно формуле, то есть мы должны 12
умножить само на себя 3 раза, и это все еще умножить на 10 в кубе.
Ну то есть, если хотите, на 1000.
Ну если кто наизусть помнит, 12 в кубе — это 1728.
Итого мы получаем: 1 728 000 номеров в рамках одного номера региона.
Это, естественно, объясняет именно то обстоятельство,
что для таких жирных регионов как Москва и Московская область или, скажем,
Санкт-Петербург и Ленинградская область,
для таких жирных номеров этого 1 728 000 отнюдь не хватает,
требуются дополнительные номера регионов, отсюда их многообразие.
Вот такой вот классический пример на применение правила
умножения в комбинаторике.
Но смотрите, если бы, скажем, мы хотели посчитать количество способов составить
номер такого типа или составить номер какого-нибудь другого типа, то нам сначала
пришлось бы применить правило умножения для вычисления вот этого количества.
Затем пришлось бы применить правило умножения для вычисления
другого количества, отвечающего другому принципу формирования номеров.
И вот после этого мы применили бы принцип сложения,
мы взяли бы это количество, прибавили бы второе и получили бы ответ,
то есть можно сочетать эти правила в зависимости от ситуации, так или иначе.
Главное, не ошибиться — где надо сложить, а где надо умножить.
Вот эти правила устроены таким образом.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
