Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Поход в театр
Loading...
From the course by Moscow Institute of Physics and Technology
Комбинаторика для начинающих
731 оценки
From the lesson
Правило сложения и умножения. Принцип Дирихле
Правило сложения. Правило умножения. Принцип Дирихле.
Meet the Instructors
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Ну что же, давайте продолжим разбираться с базовыми правилами комбинаторики,
с правилом умножения и прочее для начала,
то есть вот с теми основами, которые у нас были заложены на первой лекции.
И еще одна типичная простая задачка, совсем простая на самом деле.
Ну давайте.
Она звучит следующим образом: есть 6 человек,
компания из шести человек,
среди которых имеется, ну давайте считать ровно 2 девушки.
Значит, 6 человек, среди которых 2 девушки.
Как-то не поровну, да?
Ну вот так сложилось.
Значит, среди которых 2 девушки.
Вот эти 6 человек пришли в Большой театр и хотят рассесться в ложе Большого театра.
Места, естественно, занумерованы, то есть от того,
куда какой человек сядет, ситуация зависит: важно сел, там,
условный Петя на первое место или Петя сел на второе место, или,
там, из девушек какая-нибудь Катя села на третье место или на четвертое.
Всего в ложе 6 мест вот по числу людей, 6 человек и мест в этой ложе столько же,
сколько у нас есть товарищей в компании.
Значит, давайте 6 мест в ложе.
Вот и есть еще одно
ограничение: предполагается, что девушки не должны сидеть с краю.
Дальше они могут рассаживаться как угодно, лишь бы девушки с краю не садились.
Девушки не могут сидеть с краю.
Не сидят: раз не могут, значит и не сидят с краю.
То есть девушкам доступны только 4 промежуточных места,
всего у нас мест 6, по краям, естественно, справа и слева по одному месту, итого два.
Вот девушки на этих двух местах не сидят, сидят только на одном из четырех,
так сказать, внутренних мест.
Ну вот и спрашивается, сколько существует различных способов рассадить товарищей по
вот этим шести местам в ложе?
Вот давайте я напишу: сколько существует рассадок, что ли?
Сколько всего рассадок?
Ну давайте разбираться.
Это в общем тоже совершенно просто.
Смотрите, раз у нас 2 девушки не могут сидеть с краю,
у нас остается только 4 человека, каждый из которых может расположиться с краю.
Вот давайте этот факт зафиксируем, то есть я начинаю уже решать эту задачу.
Вот я фиксирую тот факт, что у нас есть 4 человека, ну это, по-видимому,
как раз молодые люди, раз у нас только 2 девушки на шестерых, да?
Значит, у нас есть 4 человека, которые могут и,
соответственно, сидят, могут сидеть и, соответственно, сидят с краю.
Ясно, что все четыре человека не могут сидеть с краю,
это была бы нелепость, у нас с краю всего 2 места.
Значит, нам нужно выбрать из этих четырех человек кого-нибудь сначала ну,
условно говоря, на левый край, и из оставшихся троих человек надо выбрать
кого-нибудь так, чтобы он сел на правый край.
В любом случае девушек вот этих двух мы на эти места усаживать никак не имеем права.
Таким образом, у нас есть 4, внимание, 4 способа выбрать человека,
который сядет на левый край этой ложи, ну, условно говоря, на первое место,
если нумеровать слева направо: есть всего 4 варианта выбрать человека на левый край.
И вслед за этим, вслед за тем, как мы уже выбрали одного человека на
левый край ложи, у нас остается 3 варианта,
— всего было 4 человека, одного уже выбрали одним из четырех способов,
— значит, у нас остается 3 варианта усадить человека на правый край ложи.
Вот, поскольку порядок значение имеет, то есть важно,
где сидит Петя: слева или справа, то мы пользуемся в чистом виде
правилом умножения и получаем, что 4 * 3 — это количество способов,
это количество способов распределить тех людей, которые имеют
право сидеть по краям, ну вот по этим самым краям, распределить по этим местам,
которые находятся по краям ложи, всего 4 * 3 способов.
Вот после того, как мы это сделали, внимание, тут очень важный момент.
После того, как мы выбрали двоих товарищей из вот этих вот четверых для
усадки их по краям ложи, — всего таких способов,
напоминаю, 12 штук, — вот после этого, вслед за этим, опять напоминаю,
это правило умножения, да, вслед за этим у нас остается сколько людей вообще?
Значит, после того как мы выбрали двух человек из четырех, у нас остается 2
человека, которым совершенно все равно где сидеть, и, кроме того,
у нас остаются 2 девушки, которые обязаны сидеть на внутренних местах.
Итого у нас есть всего 4 человека, всего есть 4 человека.
Из них двое — это те, которые еще не были задействованы при рассадке по краям,
и 2 девушки, которые не могли быть задействованы в этом процессе.
Вот всего остается 4 человека, которых надо рассадить по внутренним местам.
Я даже так бы нарисовал: вот есть края ложи, первое и, условно, шестое место,
а вот здесь у нас есть еще 4 позиции, 1, 2, 3, 4, на
каждую из которых мы можем посадить любого из вот этих оставшихся четырех человек.
Ну я могу совсем подробно для занудства это, конечно, сказать: ясно,
что ответ получается 4!
Я не очень хочу занудствовать, у меня нет такой цели, но, с другой стороны,
давайте уж совершенно аккуратно разбираться.
Вот у меня есть 4 человека.
Я первого из них, условно первого с каким-то там именем Миша,
например, могу посадить сюда, могу посадить сюда, могу посадить сюда, могу
посадить сюда — всего есть 4 варианта куда я этого первого товарища могу посадить.
Итак, у меня есть 4 варианта, для того чтобы усадить первого из
вот этих оставшихся четырех человек на какое-либо место в центре нашей ложи.
После того как я этого первого товарища усадил, допустим, куда-нибудь вот сюда,
у меня остается еще 3 позиции, на каждую из которых я с равной возможностью
готов усадить второго человека из вот этих четверых изначально оставшихся.
Значит, есть 3 варианта рассадки для второго человека вслед за
теми четырьмя вариантами, которые были для первого.
Итого, понятно, надо применить правило умножения и 4 * 3.
Дальше мы смотрим на третьего человека.
Для третьего человека, после того как мы посадили второго,
остается всего 2 возможности,
и вот эти 2 возможности мы присовокупляем после знака умножения вот сюда.
Ну и, наконец, у меня остается четвертый человек.
Для него — давайте вот третьего посадили — для него вариантов больше нет,
он оказывается на единственном оставшемся свободном месте.
Ну если хотите, это умножить на 1,
потому что есть ровно 1 способ выбрать это оставшееся свободное место.
И то, что мы написали, — это в аккурат 4!, 24.
Итого: сначала мы выбираем двух людей из множества,
так сказать, не девушек, это мы делаем по правилу умножения 4 * 3 способами.
Затем, когда мы уже это сделали, у нас остается 4 человека,
которых мы вольны как угодно рассаживать по четырем внутренним местам.
Ну и как вот мы только что продемонстрировали,
количество подобных рассадок — это 4!, 4 * 3 * 2 * 1.
Поскольку это делается вслед за этим, то опять, применяя правило умножения,
получаем итоговый ответ: это 4 * 3 * 4!.
Ну и если постараться и посчитать, то мы что увидим?
Это 12 надо умножить на 24, получается вроде бы как 288.
Вот такой вот числовой ответ, но, я повторяю, что число не так важно,
главное понимать принцип, что здесь, конечно, работает правило умножения.
Вот все.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
