Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Формулы для числа k-размещений
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Комбинаторика для начинающих
761 оценки
Из урока
Основные комбинаторные величины и их свойства
На этой неделе мы начнём изучать основные комбинаторные величины: введем определения размещений и сочетаний с повторениями и без. После этого мы найдём формулу для количества размещений. В приложениях вас ожидают выборы на корабле, формирование составов и сложный выбор одежды.
Познакомьтесь с преподавателями
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Итак, давайте напоследок докажем, наверное,
два утверждения относительно тех чисел, которые мы только что ввели.
Иначе будет тяжело.
Давайте, теорема 1.
Если можно называть это теоремой.
Ну да, конечно, а почему ж не теорема?
На том уровне знаний, на котором мы находимся, это утверждение – тоже теорема.
А то, что есть какие-то более сложные факты, ну это уж, как водится.
Начинать надо с простых.
Итак, как я и говорил, самое просто устроенная,
с точки зрения своей величины, чиселка – это A из n по k с чертой.
И она просто равна n в степени k.
То есть реальное значение гораздо короче записывается, чем обозначение для него.
Это довольно забавно.
A из n по k с чертой, а тут просто n в степени k.
Именно поэтому, в частности, в литературе, конечно,
вот эти A из n по k с чертой особо не используются.
Ну давайте докажем.
Я не говорю, что это очевидно.
Ну кому-то очевидно, а кому-то нет, так что, конечно, надо доказать.
«Д-во» – это доказательство.
Давайте посмотрим, что здесь происходит.
Итак, у нас есть некоторое множество объектов по-прежнему,
которое состоит из n штук этих самых объектов.
Давайте, как обычно, их обозначим.
И вот из этого множества мы извлекаем объекты с повторениями, с повторениями.
То есть у нас имеется вот эта самая божественная коробка,
в которой содержится бесконечно много объектов a1,
бесконечно много объектов a2 и так далее, бесконечно много объектов an.
И вот мы из нее извлекаем последовательные элементы.
Ну давайте думать, что значит извлечь такие последовательные элементы.
Так это, по сути, задача на номер автомобиля.
Задача на правила умножения.
Смотрите, на первую позицию,
на первую позицию в будущем
k-размещении с повторениями,
в будущем k-размещении с повторениями на первую
позицию, мы можем выбрать любой из этих объектов.
Мы можем выбрать любой из n объектов.
Мы можем выбрать
любой из наших n объектов.
Но ведь и на вторую позицию мы тоже можем выбрать любой из наших n объектов.
То есть...
Ну давайте я, конечно, это напишу не столь подробно, но ничего ж не меняется.
На вторую позицию в строящемся k-размещении
мы тоже можем выбрать любой из наших n объектов.
И так далее.
На k-тую позицию, на k-тую позицию
[ШУМ] мы тоже можем выбрать любой из имеющихся в нашем распоряжении объектов.
То есть, иными словами, мы составляем такой автомобильный номер,
у которого на первой позиции используется любой из объектов вот этого множества,
на второй позиции – любой из объектов вот этого множества,
на k-той позиции – любой из объектов вот этого множества.
Ну понятное дело, что мы количество таких вот номеров,
количество таких размещений с повторениями и будем вычислять как n × n ×...
× n.
И этих умножений будет ровно k штук.
То есть мы просто n умножим на себя k раз, потому что имеет место правило умножения.
А это и есть n в степени k.
То есть в этом случае доказательство теоремы совершенно элементарно.
Ну я не знаю, я надеюсь, что это было понятно.
По сути, k-размещение с повторениями – это такой номер автомобиля,
у которого на каждой позиции используется один и тот же набор объектов.
Если в реальном номере мы сначала использовали буквы, потом какие-то цифры,
потом снова буквы, то здесь тупо и здесь буквы, и тут буквы, и тут буквы,
и так на каждой позиции.
Ну букв этих n штук.
Перемножаем по следствию из правила умножения,
и получаем в аккурат n в степени k.
И давайте я вам докажу еще одну теорему.
На сегодня этого явно хватит, а то переборщим, сложно будет.
Давайте докажем еще, чему равняется A из n по k.
Я утверждаю, что A из n по k нужно вычислять вот так: это
n × (n − 1) ×...
× (n − k + 1).
Ну давайте разбираться, почему это правильно.
Видите, пока я никаких факториалов не использовал, хотя факториал и ввел.
Ничего, это сегодня появится все-таки.
То есть я докажу теорему, а потом порассуждаю немножко про факториал.
Ну доказательство у этой теоремы, друзья мои,
абсолютно такое же, конечно, как доказательство у предшествующей теоремы,
только теперь надо говорить так: на первую позицию – сейчас
будет прямо полная параллель с предыдущим доказательством,
с предыдущим рассуждением – на первую позицию в k-размещении,
в k-размещении без повторений (видите, разница в том,
что мы теперь работаем без повторов), значит, на первую позицию в k-размещении,
в k-размещении без повторений мы можем выбрать любой из объектов.
Мы можем выбрать абсолютно любой из объектов.
Ну то есть,
если угодно, когда мы составляем будущий номер такой абстрактный,
обобщенный номер автомобиля, то на первую позицию в этом номере
мы можем поставить любой из имеющихся в нашем распоряжении n объектов.
Давайте я вот здесь напишу, что количество способов такого выбора – это в точности n.
Но когда мы переходим на вторую позицию,
ведь мы на первой позиции уже какой-то объект зафиксировали,
но размещение, которое мы хотим построить, оно ведь не допускает повторений.
Поэтому когда мы будем ставить какой-то объект на вторую позицию,
мы ни в коем случае не сможем использовать вот тот единственный объект,
который уже стоит на первой позиции.
Поэтому здесь все-таки надо сказать аккуратнее.
На вторую позицию, на вторую позицию
в строящемся k-размещении,
размещении без повторений мы не можем
взять тот объект, который уже стоит на первой позиции,
и потому мы можем выбрать любой из оставшихся (n − 1) объектов.
Мы можем выбрать,
можем выбрать любой из оставшихся
в нашем распоряжении – после того, как мы зафиксировали первый объект
– любой из оставшихся (n − 1) объектов.
И дальше, естественно, происходит абсолютно
тоже самое: когда мы выбираем объект на третью позицию, мы уже помним,
что мы зафиксировали некоторый объект на первой позиции,
некоторый отличающийся от него объект – на второй позиции.
Соответственно, на третью позицию у нас есть вариантов выбора сколько?
Только, конечно же, (n − 2).
А теперь смотрите, вот так, чтобы было предельно понятно.
На первую позицию у нас есть n вариантов выбора.
На вторую позицию у нас уже есть (n − 1).
Смотрите, 2 – вторая позиция, но (n − 1).
На третью позицию (три!) (n − 2) варианта
выбора; на четвертую (четыре!) – (n − 3); на пятую
– (n − 4); на шестую – (n − 5); на k-тую – разумеется, (n − k + 1).
Я надеюсь, что в такой последовательности изложения это должно быть понятно.
Соответственно, пользуемся правилом умножения, тем же самым,
ну вот в таком немножко видоизмененном варианте.
То есть теперь у нас номер не может состоять из одинаковых букв.
Он обязан состоять из разных букв.
Все буквы должны быть разными.
И правило умножения дает нам, как следствие, ровно то, что было заявлено.
Сначала у нас есть n вариантов выбора, вслед за ними (n − 1),
последовательность, по правилу умножения, можно составить n × (n − 1) способами,
дальше (n − 2) – это когда мы третий объект устанавливаем на свою позицию,
и так вплоть до k-того объекта, который дает сомножитель (n − k + 1).
И теорема 2 доказана полностью.
Теперь давайте небольшие комментарии в терминах
пресловутых факториалов сделаем и на этом сегодняшнюю лекцию завершим.
Ну смотрите, вот здесь написано такое произведение: n × (n − 1) ...
(n − k + 1).
Понятно же, что его можно записать в терминах факториала следующим образом...
Разделим n!
на (n – k)!.
Ну, действительно, сверху стоит произведение всех чисел от 1 до n,
по определению факториала: 1 * 2 *,..., * n,
а снизу стоит произведение всех чисел от 1 до (n – k),
то есть и здесь есть это произведение от 1 до (n – k),
и здесь оно полностью содержится.
Когда мы сократим, у нас ровно останутся вот эти вот сомножители,
которые здесь написаны.
Так, конечно, очень удобно изображать: n!/(n – k)!
— это и есть вот это вот длинное произведение.
Так, ну, единственное, что хотелось бы заметить,
это, наверное, вот такие вот ситуации.
Что такое A из n по 0?
Вообще, что это такое?
Что значит посчитать количество способов ничего не выбрать?
Ведь A из n по 0 — это 0-размещение.
Что такое 0-размещение?
Это мы ничего не размещаем, мы вообще не запускаем руку ни в какую коробку,
мы просто ничего не делаем.
Ну, сколькими способами можно ничего не сделать?
Сколькими способами можно вытащить, так сказать, пустое множество объектов?
Понятное дело, что есть только 1 способ вытащить пустое множество объектов,
это единственный способ.
Но это вполне себе согласуется с нашей формулой,
потому что это действительно равняется
n!/(n – 0)!, то есть 1.
Так что формула верна и в этом специальном случае.
И есть еще один замечательный специальный случай,
который обязательно стоит здесь обсудить.
Это наоборот: A из n по n.
Что такое A из n по n?
Что значит выбрать n объектов из
множества мощности n — из множества, в котором присутствует n объектов?
Но не просто выбрать, а именно разместить,
то есть выбрать с учетом последовательности, с учетом порядка.
Ну, что дает нам наша формула?
Она дает нам, конечно, n * (n – 1) *...
* (n – n + 1), то есть здесь у нас стоит в точности 1,
то есть это получается произведение от 1 до n, а это есть n!.
И заметьте, если мы подставляем вот в эту формулу k = n, то внизу оказывается 0!.
Но мы с вами договорились, 0!
— это 1.
И тогда эта формула благополучно согласуется с тем,
что у нас здесь написано.
Именно ради этого,
в особенности ради этого мы и договаривались о том, чтобы считать 0!
равным 1.
Если 0!, действительно, равен 1, тогда и эта запись,
и эта запись — суть одно и то же.
И последнее, что я в этом месте скажу.
Это вот был комментарий по поводу того, почему 0!
нужно считать равным 1,
и что пустое множество можно выбрать только одним способом.
А последнее, что я скажу, вот этот n!,
количество размещений, n размещений без повторений в
множестве из n объектов — это на самом деле по существу что такое?
Это просто перестановка этих объектов, это просто...
Давайте не перестановка, а число перестановок,
число различных перестановок.
Ну, в самом деле, вот если у нас было какое-то множество объектов,
скажем, {1, 2, 3}.
Что значит выбрать какое-то размещение без повторений из этого множества?
Можно сначала выбрать 1, потом выбрать 2, потом выбрать 3.
Можно сначала выбрать 1, потом выбрать 3, потом выбрать 2.
Ну, и так далее.
Сначала выбрать 2, потом 1, потом 3.
Сначала выбрать 2, потом 3, потом 1.
Сначала выбрать 3, потом 2, потом 1.
И, наконец, сначала выбрать 3, потом 1, потом 2.
Всего 6 вариантов, и это есть в точности 3!,
который у нас здесь благополучно получился.
Это классическая формула для числа перестановок.
Конечно, количество способов переставить между собой элементы нашего множества
— это и есть количество n-размещений без повторений элементов вот этого
n-элементного множества, количество всевозможных перестановок,
и оно вычисляется просто как факториал от числа элементов этого множества.
По большому счету, это следствие нашей теоремы 2,
количество перестановок в множестве.
Давайте на этом, наверное, сегодняшнюю лекцию завершим, а продолжим рассуждением
о том, как посчитать C из n по k и, что самое сложное, C из n по k с чертой.
А дальше займемся какими-то очень красивыми и развлекательными свойствами
всех этих замечательных комбинаторных характеристик.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
