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