Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Количество беспорядков
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Комбинаторика для начинающих
787 оценки
Из урока
Формула включений и исключений
Как отпраздновать новый год, нарисовать картину Ван Гога, посетить все города России и составить правильный отчёт в школе - в 6-й неделе курса. Формально, мы познакомимся с формулой включений и исключений - очень полезным комбинаторным инструментом. В частности, мы выведем новое тождество и получим формулу для нахождения числа беспорядков.
Познакомьтесь с преподавателями
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Ну, давайте в завершение лекции, в последней части лекции, что ли,
рассмотрим два примера на применение формулы включений/ исключений,
каждый из которых будет, ну все-таки гораздо содержательнее, чем та затравка,
с которой мы начали то есть, чем задачка про английский, немецкий,
французский языки — там все очень просто.
Вот давайте рассмотрим такую классическую задачу — это называется задача
о беспорядках.
Задача о
беспорядках.
Одно из ее названий во всяком случае такое.
Задачу ставят следующим образом.
Опять, пусть у нас 30 человек в аудитории.
Давайте считать, что у нас такой неразменный пятак в каком-то смысле.
Есть 30 человек в аудитории.
Но на сей раз мы не будем говорить о знании ими каких-то языков,
умении выпить бутылку водки или еще что-то...
Мы будем говорить о совершенно другой вещи.
Представьте себе, что у них в этой аудитории,
за каждым из них закреплено какое-то свое место, то есть каждый из людей знает,
на каком месте он должен в этой аудитории сидеть.
У каждого человека есть свое место.
У каждого человека есть свое место.
Ну, всего мест, разумеется, 30.
То есть вот есть аудитория на 30 мест, все эти места помечены: одно для
первого человека, другое — для второго, третье — для третьего и так далее.
Задача состоит в следующем: сколько существует способов сколько
существует способов так
рассадить людей по аудитории,
так рассадить людей
по аудитории,
чтобы ни один человек не сел на свое место.
На то место, которое за ним изначально закреплено.
Ни один человек не
сел на свое место.
Ну, такой очень естественный вопрос.
Полный беспорядок.
Казалось бы, это вообще очень сложно сделать.
Так вот перетасовать людей, чтобы и первый сел не на первое место,
и второй не на второе, и третий не на третье.
Так интуитивно, по идее, кажется, что должно быть не очень много таких способов.
Но сейчас мы увидим, что эта интуиция не совсем, мягко выражаясь, верна.
А верно нечто совершенно другое.
Ну, давайте подумаем, как вообще это решать.
Вот что здесь является объектами, а что является свойствами, если мы действительно
хотим считать, что это задача на применение формулы включений/исключений?
То есть априори,
конечно,совершенно непонятно вообще задача ли это на формулу включений/ исключений.
Но я утверждаю, что да.
Задача.
И объекты, товарищи, объекты — это не люди, как то было в случае,
когда мы изучали знание английского, немецкого и французского.
Нет, это не наши люди в аудитории.
Смотрите, ведь вопрос-то как ставится?
Вам еще предстоит же самим решать какие-то задачки на формулу включений/исключений.
Вот вдумайтесь, почему я ее здесь применяю и к чему я ее здесь применяю.
Вопрос же как ставится: сколько существует способов так рассадить людей?
Не «Сколько существует людей в аудитории?», а сколько существует способов
рассадки, сколько существует перестановок из этих людей?
Перестановок на множестве из этих людей.
Вот ведь как вопрос ставится.
Поэтому на самом деле объекты,
которые мы будем рассматривать с точки зрения формулы включений/исключений, это,
повторяю, не люди, объекты — это рассадки людей по аудитории,
рассадки людей по аудитории.
Ну, что такое рассадки людей?
Это, я повторяю, просто перестановки на множестве из 30-ти человек.
Можно рассадить в таком порядке, можно в эдаком.
То есть, по сути, просто переставить между собою 30 человек,
по-разному расположив их на местах.
Поэтому N большое — это есть просто 30 факториал.
N = 30!
Количество всех возможных перестановок на множестве из 30-ти человек.
Но это мы с вами проходили, мы знаем, что перестановок будет, конечно,
30 факториал в этом случае.
Вот рассадка людей по аудитории — это в точности перестановка этих людей,
а перестановок у нас факториал от общего числа людей/штук.
То есть вот это количество наших объектов — N большое.
Осталось, для того чтобы применить формулу включений/исключений,
описать какие-нибудь свойства.
Ну, смотрите: нас интересуют способы рассадить людей так, чтобы — внимание!
— ни один из них не сидел на своем месте.
Вот присутствует уже какое-то отрицание.
Сразу видно, что что-то стоит со штрихом, да?
Ни один человек не сидит на своем месте — НЕ сидит.
Ну, значит, наверное, свойство состоит в том,
что человек сидит на своем месте, правильно?
Вот!
Ну, давайте так и обозначим: αi-тое — это свойство
рассадки (перестановки)
свойство рассадки людей, которое выполнено,
выполнено если конкретный i-й человек сидит на своем месте выполнено,
если i-й человек сидит на своем месте.
Остальные — не важно, как, на своих, не на своих.
На своем месте.
Как обычно, нам лишь важно,
чтоб было выполнено свойство αi-тое, про остальные мы ничего не говорим.
Значит, αi-тое, это свойство рассадки, которое выполнено,
если i-й по счету человек сидит на своем месте.
Ну, то есть n маленькое, конечно равняется 30-ти.
n = 30 Всего у нас 30 свойств.
α1 — это, что первый человек сидит на своем месте, α2 — что второй.
и так далее.
Ну, давайте посмотрим, что такое N(α1, ...,
α30) что это просто по сути, до применения формулы включений/ исключений.
Что это означает?
Но это и есть количество рассадок, при которых и первый человек не сидит на
своем месте, и второй человек не сидит на своем месте, и тридцатый, наконец,
человек тоже не сидит на своем месте.
То есть, это и есть та величина, которую мы ищем.
Количество рассадок,
при которых случился полный беспорядок: ни один человек не сидит на своем месте.
Всё! Применяем формулу включений/ исключений.
У нас есть N большое, которое 30 факториал.
Из этого надо вычесть...
А что надо вычесть?
Ну, надо вычесть N большое от α1 –...
– N(α30) Давайте подумаем, что такое, N большое, например, от α1.
Сколько существует таких перестановок на множестве людей, таких способов рассадить
наших товарищей по аудитории, при которых первый человек сидит на своем месте.
Ну, очень просто: первого сажаем на свое место, а остальные, хоть трава не расти,
рассаживаются как угодно, их 29, поэтому их расстановок (рассадок) 29!.
Абсолютно то же самое, касается, естественно, 30-го человека.
Его сажаем на свое место, остальных перетасовываем как угодно.
Получаем все тот же 29!.
Дальше добавляем N(α1,
α2) +...+ N(α29, α30).
Что же мы в результате добавляем?
Ну, вот какие это величины?
Ну тоже понятно: мы первого товарища сажаем на свое место,
второго товарища сажаем на свое место,
а остальные 28 человек перетасовываются, пересаживаются как угодно.
То есть, вот это 28!, и это тоже 28!.
минус...
+...
Так! Минус единица у нас будет в тридцатой
степени, поэтому последнее слагаемое идет со знаком плюс (–1 в 30-й степени).
N(α1, ..., α30) Ну, это, конечно, равно единице,
потому что рассадить людей таким образом, чтобы и первый сидел на своем месте,
и второй на своем месте, и тридцатый на своем месте — такое количество
способов равно единице и тут уже нечего особенно вычислять.
Так, давайте попробуем все-таки прикинуть, чему это на самом деле равняется,
потому что написана какая-то страшная формула,
в которой куча всего то прибавляется, то вычитается.
И хотелось бы все-таки понять, а как соотносится это количество с общим
количеством рассадок, каковых, как мы знаем, 30!.
Ну, давайте напишем так: = 30!
Теперь — сколько вот здесь слагаемых?
Ну, их 30, конечно.
30 * 29!
Прибавляется C из 30 по 2.
Давайте честно напишем C из 30 по 2 на 28!.
Вычитается C из 30 по 3 на 27 факториал, прибавляется, и так далее.
Ну вот здесь уже C из 30-ти по 30, ну давайте, я напишу C из 30-ти по 30,
это просто единица, ровно одно добавляется и, если хотите Это у нас что такое?
Это у нас получается даже, я бы сказал, 0!.
Это у нас 0!, потому что, смотрите, вот это вот 29 — это 30 минус одно свойство,
которое стоит в скобках, вот это 28 — это 30 минус 2 свойства,
которые стоят в скобках, вот это 27 — это 30 минус 3,
вот этот 0 — это 30 – 30, то есть тут не 1!, а именно 0!
стоит.
Вот, ну давайте дальше расписывать, что у нас получится.
30!
–...
Ну давайте я все-таки оставлю, наверное, 30 * 29!.
Вы мне скажете: зачем я так оставляю, это же 0?
Ну сейчас посмотрим, мне не очень так хочется писать, посмотрим.
Посмотрим, посмотрим, посмотрим, а, может, и ничего, кстати, может быть, и ничего.
Значит, вот здесь напишем 30!/(2!
* 28!) — это C из 30 по 2, записанное согласно
стандартной формуле, и дальше надо умножить на 28!.
С минусом идет 30!/(3!
* 27!) * 27!
+ +...
Видно, что факториалы вот эти вот все время сокращаются: 28!, 28!
убили друг друга, 27!, 27!
кокнулись, вот.
Ну в конце — это лишь формальность будет какая-то.
Значит, последняя у нас — 30!/(30!
* 0!) и на 0!.
Это стандартное издевательство — сокращать 0!
с 0!. Это довольно смешно,
потому что и то и другое равно 1 просто по соглашению.
Ну тем не менее.
Так, ну, наверное, вот этих товарищей тоже нужно переписать в каком-то таком же виде.
Давайте я уж проявлю максимальное занудство, и выглядеть это будет так.
Мы 30!
вынесем за скобку, а в скобках у меня останется: так (1/0!
– 1/1!
+ 1/2!
– 1/3!
+...
+ 1/30!).
Вот. На самом деле можно в такой совершенно
симметричной форме записать то, что у нас получилось.
Вынести общий 30!
за скобки, а в скобках ну вот так вот преобразовать первые два слагаемых,
чтобы было правильно.
0, он и в Африке, конечно, 0, но вот я его так переписал, а остальные, они, видите,
они как бы за ними идут очень естественным образом: 0, 1, 2, 3...
30.
Вот ну а дальше надо сказать так: если, друзья мои,
вы анализ еще не очень хорошо знаете математический и не слышали,
что такое ряд Тейлора, например, для экспоненты, то,
конечно, вам не судьба узреть здесь сразу нечто знакомое.
Если вы анализ на уровне, там, первого курса университета какого-нибудь изучали,
то вы, конечно, углядите здесь знакомую формулу для экспоненты,
а именно: для e в –1 степени.
Ну утверждение такое: e в –1 степени раскладывается вот в такой ряд 1/0!
–1/1!
+ 1/2!
–...
+ 1/30!
– 1/31!
+...
И так до бесконечности.
Вот есть такой бесконечный ряд, и можно доказать,
что этот бесконечный ряд представляет собой в точности 1/e,
где e — это основание натурального логарифма, 2,71...
Вот если вы не знаете этого утверждения,
если вы его никогда не встречали раньше, ну вы сильно не расстраивайтесь,
вы возьмите компьютер и попробуйте просто запустить машину.
Чем дальше вы будете складывать, тем, как вы увидите,
у вас будет ближе и ближе получаться число к пресловутому
2,718281828459045...
ну и так далее.
То есть чем больше вы таких слагаемых сложите...
А, ну это e, конечно, а вам нужно будет получить e в –1 степени, 1/e.
Вот чем больше вы таких слагаемых сложите,
тем ближе к единице, поделенной вот на это загадочное число, у вас и получится.
Короче говоря, вот это вот примерно,
поскольку 30 — это число уже очень большое, — это примерно 30!/e.
Так или иначе, — то ли вы это знаете,
то ли вы это получили с помощью компьютера — но факт таков, что это примерно 30!/e.
То есть смотрите пафос-то какой.
Пафос состоит в том, что беспорядков-то очень много, их больше
трети от общего числа расстановок людей по аудитории, больше трети.
Ведь мы делим здесь на 2,71, а не на 3.
Ну не половина, да, но очень значительное количество.
Причем, чем больше людей, тем ближе это вот к такой величине.
Полностью как бы решенная задача, несмотря на,
казалось бы, страшный вид формулы включения исключений.
Вот, оказывается, формула включения исключений позволяет решать такие красивые
задачи и немножко даже разрушать интуицию, которая за ними, казалось бы, стоит.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
