Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Правило умножения
Loading...
Do curso por Moscow Institute of Physics and Technology
Комбинаторика для начинающих
734 classificações
Na lição
Правило сложения и умножения. Принцип Дирихле
Правило сложения. Правило умножения. Принцип Дирихле.
Conheça os instrutores
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Давайте я сформулирую следующее, вероятно, чуть более сложное правило.
Хотя, в общем, ну, так.
Для обычного начинающего оно тоже является достаточно простым утверждением.
И можно догадаться, на самом деле, как оно называется.
Ну, конечно, не очень прозорливый человек мне, наверное,
сейчас скажет: это правило вычитания.
Но нет. Это, конечно, не правило вычитания.
Это правило умножения.
Следующая основная операция,
которая бывает в арифметике после сложения — это, конечно, умножить.
И, соответственно, в комбинаторике второе, чуть-чуть более содержательное правило,
нежели то, которое мы только что обсудили, — это правило умножения.
Правило умножения.
Давайте начнем его с тех же самых «пусть», с которых мы начинали правило сложения.
То есть у нас по-прежнему есть два множества объектов.
Пусть А — первое множество объектов, которое состоит из n элементов.
Ну, вот, если как-то проще, для начала, себе это по-другому представлять,
считайте, что это множество букв русского алфавита, каковых, повторяю, 33 штуки.
Ну и B — это, соответственно, второе множество объектов,
которое состоит, соответственно, из m этих самых объектов.
Из m-элементов.
И для простоты можете представлять в голове своей, что это — какое-то,
не какое-то, а просто множество цифр.
Так, для примера.
Ну вот есть какие-то 2 абстрактных множества объектов, вообще говоря.
Теперь, что мы делаем?
Мы говорим следующее: давайте сперва извлечем какой-нибудь объект
из множества А.
Ровно один.
Извлечем, запомним и вслед за ним извлечем какой-нибудь объект из множества B.
То есть у нас получится такая последовательность из двух объектов,
первый из которых выбран из множества А, второй из которых выбран из множества В.
Спрашивается: сколькими способами можно организовать такую последовательность?
Каково количество способов один за другим выбрать объекты?
Сначала первый — отсюда, второй — отсюда.
Ну, слушатели, конечно, уже догадались.
Раз правило называется правилом умножения, то, естественно, количество,
которое здесь ищется — это есть произведение числа n и числа m.
И более или менее этот факт тоже очевиден.
Ну, давайте я его зафиксирую, а потом еще немножко прокомментирую.
Итак, количество способов выбрать,
выбрать сперва ровно
один объект из множества А,
а вслед за ним ровно один объект из множества В,
а вслед за
ним ровно один
объект из
В, равно n умножить на m.
И вот в этом, собственно, состоит правило умножения.
В этом, собственно, состоит правило умножения.
Ну, если кого-то по ходу дела еще не убедило вот
это вот рассуждение и ему (ей) не кажется, что это,
в общем, очевидно, ну, давайте я уж совсем подробно это как-то поясню,
чтобы было понятно, откуда произведение взялось.
Ну давайте прямо перебирать.
Вот можно сначала выбрать объект a1, потом вслед за ним поставить объект b1.
Дальше можно сперва выбрать объект a1, но вслед за ним поставить объект b2.
Ну, то есть, представляете себе вот так вот: a0, если в нашем примере.
Да? Дальше идет a1,
если в примере с буквами и цифрами работать.
Дальше идет a1b3.
Ну и так далее, вплоть до a1bm.
Такая вот строчка, в которой, в качестве первого объекта из множества
А (большое), выбран самый первый объект этого множества — а (маленькое) первое.
Ну, скажем, в случае букв русского алфавита, это просто буква «а».
А вслед за ней, а этой буквой «а»,
мы ставим каждую из имеющихся в нашем распоряжении цифр.
Ну, если множества объектов какие-то другие, то, соответственно,
делаем вот эту вот самую процедуру.
В следующую строчку этой таблицы рисуем такие последовательности,
которые начинаются с объекта А2.
Например, в случае русского алфавита, это будет буква b.
А вот вслед за ней можно поставить цифру 0, а в общем случае — какой-то объект b1.
Вслед за а2 можно поставить b2, можно поставить b3.
Ну и так далее, вплоть до b с индексом m.
Понятное дело, что вот здесь надо нарисовать такое здоровенное многоточие.
И последняя строчка, она будет начинаться,
разумеется, с последнего же объекта, которое принадлежит множеству А большое,
то есть а маленького с индексом n, а продолжаться она может чем угодно.
Аn b2, an b2, an b3 и так далее, an bm.
Ну и уже глядя на эту таблицу, я думаю, каждый из слушателей с очевидностью
убедится в том, что в этой таблице ровно n умножить m различных элементов.
И таким образом действительно последовательности,
которые можно составить из двух объектов, их получается n умножить на m штук.
Ну, я не знаю.
Может быть я зря уж так подробно жевал.
Может быть я кого-то усыпил по ходу дела, но что ж поделать.
Вот, все-таки, базовые вещи надо разбирать.
Просыпайтесь, пожалуйста, сейчас будет что-то более интересное.
Но прежде, чем будет что-то более интересное,
давайте рассмотрим чуть более общую ситуацию.
Вот вследствие с правилом умножения, давайте я так и напишу прямо.
Вследствие из того правила умножения, которое мы изучили.
Оно состоит в том, что, в принципе, можно рассматривать не два множества объектов,
а несколько: 3, 10, 25.
Сколько хотите.
И делать то же самое: из первого множества объектов извлекать 1 объект,
потом вслед за ним вставить какой-нибудь ровно один объект из второго множества.
Из 3-го, из 4-го, из 25-го и так далее.
Вот давайте это зафиксируем.
Скажем, пусть у нас есть множества А1, ...,
Аk, каждое из которых состоит из некоторого числа объектов.
Это вот множества объектов.
Множества объектов.
Множества я буду традиционно сокращать вот так: мн-ва.
Значит, множества объектов.
Ну и действительно, давайте зафиксируем величину их мощности.
Повторяю, мощность — это просто количество элементов множеств.
Итак, мощность Ai, количество элементов в этом множестве —
давайте просто обозначим как-нибудь N с индексом i.
N с индексом i — это просто количество объектов,
которые входят в данное множество.
Тогда число способов
извлечь сперва,
давайте, сперва один объект,
давайте я напишу просто «об.», значит 1 объект из множества А1,
поставить вслед за ним,
вслед за ним,
один объект из множества А2,
один объект из множества А2,
расположить вслед за этими двумя еще один, ровно один объект из множества А3.
Ну давайте я это еще напишу для полноты картины.
Расположить за ними, за этими двумя уже выбранными,
еще один, ровно один объект
из множества А3 и так далее.
И всю эту цепочку последовательно выбираемых объектов завершить
ровно одним объектом из множества Аk и всю эту
цепочку последовательно извлекаемых объектов,
последовательно извлекаемых объектов,
объектов, завершить
ровно одним объектом из Ak, каким угодно,
завершить ровно одним
каким-нибудь объектом из Ak.
Фраза длинная.
Она начиналась со слова «число способов» и вот это все сделать: извлечь,
за ним извлечь, за ним расположить, за ним поставить, там, и так далее.
Вот все это количество способов, все это число способов равно произведению
чисел N1, это было количество объектов в А1, N2,
это было по определению количество объектов А2, и так далее, вплоть до Nk.
Это количество объектов в Аk.
Ну, это действительно прямое следствие из того, что мы делали в рамках правила
умножения, но если у кого-то очень развито геометрическое мышление, и он или
она хочет получить следствие не как следствие отсюда, а как непосредственно
доказанную теорему, то представляйте себе картинку следующим образом.
Видите, мы нарисовали такую табличку, да?
Когда доказывали справедливость правила умножения.
То есть у нас получилось n умножить на m потому что было n строчек,
отвечающих количеству объектов в первом множестве, и было m
столбцов в этой таблице, отвечающее количество объектов во втором множестве.
Теперь у нас множеств больше.
Ну, скажем, представьте себе, что их — три штуки.
Тогда вы можете нарисовать такое третье измерение, то есть сделать такую,
так уж если угодно, трехмерную таблицу, добавляя очередную,
очередной символ какой-нибудь, там,
с и d из следующего, третьего множества, располагая его вот по этой,
так сказать, третьей координате в пространстве, в размерности 3.
Но если вы себе представляете вдруг, каким-то чудом, более многомерные
пространства, то вы увидите вот эту вот картинку в общем случае.
Но, конечно, на самом деле, это просто очень легкое упражнение,
очень легкое следствие, которое сразу вытекает вот из этого рассуждения.
Наверное, жевать его в таких подробностях тоже не стоит, но, повторяю, если
кому-то геометрия ближе, представляйте себе такие многомерные таблицы,
в которых расположены все возможные эти последовательности,
и тогда у вас действительно получится нужное вам произведение.
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.
