Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Число сочетаний без повторений
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Комбинаторика для начинающих
761 оценки
Из урока
Сочетания с повторениями и без
Продолжая тему прошлой недели, мы найдём формулы для числа сочетаний с повторениями и без. Кроме того, мы обсудим тяжёлую работу биологов, обмен монет нумизматов, подберём красивый букет и выберем группу альпинистов для похода.
Познакомьтесь с преподавателями
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Так, ну, давайте,
теорема более простая из двух.
Эта теорема о том, чему равняется С из n по k.
Мы хотим посчитать просто вот это вот число сочетаний без повторений.
Значит, я утверждаю, что C из n по k можно выразить по следующей формуле.
Это на самом деле просто A из n по k, поделенное на k факториал.
То есть, k сочетаний без повторений
в k факториал раз меньше, чем k размещений без повторений.
Вот такое вот очень естественное соотношение между
двумя комбинаторными величинами.
Ну, и если записать явно формулу, которую мы в прошлый раз доказали для A из n по k,
то у нас получится классическое выражение, которое, наверняка,
многие могли видеть, где-то встречать уже раньше.
n! * k!* (n − k)!
Такое вот красивое симметричное выражение, которое служит явной формулой
для подсчета чисел сочетания, сочетания, без, повторяю, без повторения.
Так, ну, давайте, действительно это дело аккуратно докажем.
И почему же сочетаний, которые без повторений ровно
в k факториал раз меньше, чем размещений, которые естественно тоже без повторений?
Ну на самом деле все очень просто.
Давайте, я сначала словами скажу.
И может быть для кого-то так будет сразу понятнее,
после чего я разведу какое-то занудство на доске.
Буду там как-то аккуратно это все расписывать.
Но, на самом деле, все будет очень просто.
Суть-то совсем элементарная.
Смотрите, вот мы вытащили какую-то последовательность объектов,
в которой мы учитываем порядок встречаемости этих объектов.
Конечно, эту последовательность мы можем вытащить столькими способами,
сколько у нас всего есть размещений без повторений.
И это количество есть A из n по k.
Вытащили какую-то последовательность: л, я, г.
у, ш, к, а.
Вот, например, такую вот последовательность букв русского алфавита.
Всего 7 букв.
То есть здесь в этом примере k равняется 7.
Ну вытащили, замечательно.
А могли вытащить другую последовательность тоже одним из вот стольких
вот способов A из n по k.
Ну, в данном случае, там A из 33 по 7.
Потому что у нас 33 буквы русского алфавита, и мы из них, вот здесь видно,
извлекаем 7 штук.
Ну могли вытащить вот такую вот последовательность.
Я об этом в прошлый раз говорил.
И с точки зрения размещений без повторений − это, конечно, другая последовательность,
потому что буквы в ней встречаются в ином порядке.
Действительно, получается просто другое слово.
В начале было слово «лягушка», теперь получилось слово «гуляшка».
Ну там еще какая-нибудь «ялгушка» или еще что-нибудь.
То есть вариантов много.
Но если нас не интересует порядок букв,
порядок объектов в той последовательности, которую вы извлекаем,
а интересует лишь кучка, лишь пригоршня, состоящая из вот этих вот 7,
в данном случае, букв, то и вот это, и вот это – суть одно и то же.
И «ялгушка» и там не знаю, какое-нибудь «шау», что-то такое литовское.
Это тоже, это тоже вполне то же самое сочетание без повторений.
То есть это разные размещения, но это одно и тоже сочетание, понятное дело.
То есть, вот здесь вот есть много различных размещений,
но каждое из них представляет собой одну и ту же кучку букв.
То есть, каждое из них является одним и тем же сочетанием.
Но естественно сочетаний получается во столько раз меньше, сколько вот этих
вот слов можно записать под данной фигурной скобкой.
Но, а сколько можно таких слов записать, например, вот в этом конкретном случае?
Если у нас всего 7 букв и мы их можем между собой переставлять как угодно,
в итоге всякий раз, получая одну и ту же кучку из букв?
Ну понятно, мы в прошлый раз это с вами обсуждали, это то,
что называется число перестановок.
То есть мы просто можем как угодно переставить 7 букв.
Значит здесь у нас получится всего 7 факториал способов.
Есть 7 факториал способов переставить буквы слова «лягушка»,
так что каждый раз буквы-то одни и те же, но слово получается новое.
Ну понятно, значит в 7 факториал раз больше у нас получается этих отдельных
слов размещений без повторений, нежели есть сочетаний без повторений,
каждое из которых это просто кучка букв любого из этих слов.
Вот ну, а теперь, давайте,
я еще раз то же самое, смысл-то, вроде, совершенно понятен, еще раз то же
самое постараюсь максимально формализовано уже, аккуратно сказать, в общем случае,
когда у нас не 7, а произвольное число k, но суть абсолютно та же самая.
Ну действительно, вот у нас есть множество, состоящее из n объектов.
Давайте их как-нибудь стандартно обозначим, как у нас это водилось до сих
пор, обозначим наши объекты a1, ..., a с индексом n.
И вот из этого множества мы извлекает всевозможные k сочетания без повторений.
Значит, извлекаем отсюда все возможные k
сочетания без повторений.
Берем какое-нибудь из этих k сочетаний,
давайте, как-нибудь его так внешне обозначим в виде такой сарделечки.
Я все-таки не могу быть совершенно формальным в каждый момент времени.
Давайте, вот такая вот сарделечка будет у нас обозначать одно конкретное k
сочетание.
Ну, если вы хотите формальности, я конечно,
могу около этой сарделечки написать, что-нибудь вот в таком стиле ai1 ai2,
..., ai с индексом k.
Подразумевая, что k сочетание без повторений состоит вот именно из
этих объектов с какими-то различными индексами i1, ..., ik, и это объекты,
все изначально принадлежащие исходному множеству a1, ..., an.
Но здесь, повторяю, важно, что i1, i2,
ik — это все разные индексы, а это какие-то элементы исходного множества.
Просто вот с какими-то различными индексами.
Ну все-таки мне сарделечка, как-то вот, честно говоря, больше по душе,
сарделечка, она как-то радует душу.
Гораздо в большей степени,
чем какое-то формальное множество со страшными двойными индексами.
Вот.
Это у нас сочетания.
То есть опять же кучка, горстка букв, пригоршня,
в которой порядок пока не имеет никакого значения.
Вот зафиксировали одно такое k сочетание,
потом зафиксировали какое-то другое k сочетание.
Давайте, еще одна сарделечка — это еще одно k сочетание,
которое отличается от данного.
Но что значит оно отличается?
Что значит k сочетание не такое же как предыдущее?
Это значит, что у него другой набор вот этих индексов.
То есть, не то чтобы мы как-то переставили элементы в нем.
Нет, нет...
эта пригоршня, она от этого не меняется.
Нет. Мы берем просто какой-то другой,
вообще говоря, набор букв, в котором есть буквы,
отличные от присутствующих в первом k сочетании, в первой сарделечке.
Ну я не знаю, как для красоты можно написать так aj1, ...,
ajk, подразумевая, что вот это вот множество индексов j1, jk,
отличается от множества индексов i1, ik, как-то вот они не совпадают между собой.
Сами эти множества различны.
Вот ну, и так далее, много, много таких сарделечек, много, много таких сарделечек.
А сколько их?
Товарищи, сколько всего таких сарделечек?
Сколько всего различных k сочетаний без повторений?
Ну допустим мы даже не знаем формулу,
но мы же точно знаем обозначение их С из n по k, просто по определению.
Вот это если хотите, первое, вот это – второе,
вот это – третье, а вот это – С из n по k.
Вот это самое последнее, мы их как-то перенумеровали, ну, мы их знаем,
мы их по определению знаем, что их С из n по k штук.
Хорошо.
А теперь давайте, зафиксируем какую-нибудь их этих сарделечек.
Вот в ней есть буковки, объекты a с какими-то там индексами,
и начнем эти объекты между собой переставлять,
вот буквально как здесь это было сделано в фигурных скобках.
То есть будем записывать эти последовательности в разном порядке.
Ну можно написать сначала a с индексом i1,
потом a с индексом i2, и наконец, a с индексом ik.
Можно в начало поставить вот этот последний объект,
за ним, например, расположить второй.
Ну и так далее.
Но мы с вами знаем, мы это в прошлый раз изучали,
и только что вспоминали относительно слова «лягушка», таких перестановок
на множестве из вот этих вот k различных объектов, это различные объекты,
и таких перестановок на множестве из этих k различных объектов k факториал штук.
Ну давайте, так как-нибудь, это и нарисуем, в виде таких стрелочек.
Здесь будет сарделька побольше.
Во сколько раз эта сарделька побольше?
Ну, ровно в k факториал раз.
Значит, здесь было одно, а здесь получается k факториал.
K факториал чего?
Еще раз.
Здесь у нас есть сочетания без повторений, некоторое совершенно конкретное,
вот как в примере, это было сочетание, состоящее из 7 букв: л, я, г, у, ш.
к, а. А вот здесь этому сочетанию, этой
единственной горстке букв сопоставлены все возможные последовательности букв,
все возможные слова, которые можно из этих букв составить путем их перестановки.
Понятно, что этих слов – k факториал,
и эти слова представляют собой в аккурат k размещения без повторений.
Точно так же здесь есть k факториал
различных порядков, различных размещений,
которые соответствуют данному единственному, конкретному k сочетанию.
Здесь есть точно также k факториал
различных размещений, отвечающих данному k сочетанию.
Ну и наконец, здесь их тоже k факториал.
Картинка абсолютно идентичная.
Понятное дело, сарделька увеличилась.
Здесь у нас получается k факториал размещений.
Хорошо.
А сколько всего размещений?
Смотрите, вот здесь k факториал, здесь k факториал,
здесь k факториал, здесь k факториал.
А суммарно сколько?
Ну суммарно мы получим просто все возможные размещения.
То есть суммарно мы получим в точности A из n по k – количество всех возможных
размещений без повторений из n объектов.
То есть, когда мы сложим вот эти все k факториалы,
мы получим в аккурат A из n по k.
Но сколько всего этих k факториалов?
А столько, сколько было маленьких сарделечек, то есть С из n по k.
То есть получается, что если С из n по k – количество маленьких сарделечек,
умножить на k факториал,
то есть сложить вот эти все k факториалы по всем С из n по k маленьким сарделечкам,
то у нас получится в аккурат A из n по k – количество всех возможных размещений.
Мы просто каждое размещение определили так: взяли некоторое k сочетание и по нему
построили все возможные размещения, которые из него получаются.
Естественно, мы исчерпали таким образом множество всех возможных размещений.
Всех возможных слов из k различных букв.
Ну и в итоге мы получаем ровно ту самую формулу,
которая и была заявлена в формулировке теоремы.
Ну, а это соответственно будет n!
/ k!
* (n − k)!
И теорема, тем самым, полностью доказана.
Ну, товарищи, я не знаю, я конечно очень занудно в этом месте рассказал, но,
с другой стороны, ну, проглотите этот кусок, если он совершенно очевиден.
В конце концов, та затравка, с которой начато было
доказательство для случая «лягушки» любимой, она же, в общем, понятна.
Ну, а если вдруг непонятна, то посмотрите на это внимательно.
Да, вот взяли каждое сочетание, посмотрели все размещения, которые ему соответствуют.
Сочетаний суммарно С из n по k, размещений стало быть в k факториал раз больше.
А сколько всего размещений?
A из n по k.
Ну значит, С из n по k — это A из n по k поделить на k факториал.
и вся недолга.
Теорема полностью доказана.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
