Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Доказательство первых двух тождеств(*)
Loading...
From the course by Moscow Institute of Physics and Technology
Комбинаторика для начинающих
730 оценки
From the lesson
Комбинаторные тождества
Темы этой недели: бином Ньютона и треугольник Паскаля, и разные полезные комбинаторные тождества. Также мы будем выбирать посуду и слова из чётного количества букв.
Meet the Instructors
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
И вот я сейчас хочу его доказать, не используя никакой формулы с факториалами,
а используя чисто комбинаторные соображения.
Чисто комбинаторные соображения будут состоять в том,
что мы одно и то же множество объектов будем перечислять двумя разными способами.
С одной стороны, как просто количество всех k сочетаний из n объектов,
а с другой стороны, вот как-то разобьем его на части и представим соотвественно C
из n пока в виде суммы.
Ну давайте это сделаем.
Вот пусть у нас есть множество, состоящее из n-объектов: a1, ..., an.
Ну какое-то абстрактное множество, как всегда,
природа объектов нас не очень интересует.
Давайте из этого множества вытаскивать все возможные k-сочетания без повторений,
все возможные k-сочетания без повторений.
Понятное дело, что всех этих возможных k-сочетаний без повторений,
ну просто по определению, C из n по k штук.
Давайте зафиксируем это глубокое знание.
Значит, их ровно c из n по k штук.
Давайте попробуем как-нибудь перечислить все эти k-сочетания без
повторений по-другому.
Ну действительно, давайте, с одной стороны,
рассмотрим те k-сочетания, те k-сочетания,
без повторений, без повторений,
которые содержат внутри
себя в качестве одного из элементов объект a1,
которые содержат в качестве одного из своих элементов объект a1.
Понятное дело, что среди всех возможных k-сочетаний,
такие k-сочетания безусловно присутствуют.
Вот те, которые содержат объект a1 в качестве одного из своих элементов.
Но с другой стороны, все оставшиеся k-сочетания,
те, которые мы еще как бы вот здесь не рассмотрели, это ведь те k-сочетания,
которые, напротив, элемента a1 не содержат.
Значит, давайте, с другой стороны,
рассмотрим те
k-сочетания без повторений,
которые не
содержат внутри себя
элемент a1.
Вот просто разобьем фактически множество всех возможных k-сочетаний на две части.
В одной части находятся все k-сочетания, которые содержат объект a1,
в другой части, соответственно, те, которые его не содержат.
Понятно, что таким образом мы исчерпываем все возможные k-сочетания,
просто рассмотрением двух таких ситуаций.
Так, ну давайте попробуем понять сколько
у нас есть k-сочетаний
первого, так сказать, типа.
Ну я имею в виду, что первого типа, это те самые, которые содержат объект a1.
А второго типа, соответственно, это те, которые не содержат элемент a1.
Вот сколько k-сочетаний первого типа?
Давайте посмотрим.
Значит, они содержат объект a1, это сочетание без повторений.
То есть, объект a1 в них может присутствовать только один раз.
И если мы знаем, что он присутствует, ну вот все, он присутствует,
больше никакой новой важной информации у нас по отношению к этому объекту не будет.
Дальше у нас есть, давайте, вот он зафиксирован, он присутствует в нашем
k-сочетании, и дальше у нас есть еще объекты a2, ..., an.
Их всего n − 1 штука.
И вот это наше k-сочетание первого типа.
Оно ж как устроено, в нем всего k-объектов поскольку это k сочетание.
Причем, среди этих k-объектов, которые в него входят, мы знаем, видите,
мы его обвели, заведомо присутствует объект a1.
Ну значит надо добавить еще k − 1 объект, так чтобы получилось в точности k.
Иными словами, мы вот из этого, отделенного фигурной скобкой,
множества объектов, должны извлечь произвольное
k − 1 сочетание, k − 1 сочетание.
Извлекая, повторяю, произвольное k − 1
сочетание из вот этого множества объектов, состоящего всего из n − 1 штуки,
мы вместе с элементом a1,
про который мы знаем, что он присутствует в нашем k-сочетании первого типа,
вместе с элементом a1 и с вот этим k − 1 сочетанием,
мы действительно получаем k-сочетание первого типа.
И таким образом, мы перечисляем все возможные k-сочетания первого типа.
Естественно, их оказывается С из n − 1 по k − 1.
Просто повторяю, вот из этих n − 1 объектов мы вытаскиваем
произвольные k − 1, так чтобы они образовывали сочетание, возникает C.
Ну а когда мы к этим k − 1 добавляем еще и a1,
мы получаем в точности k-сочетание первого типа.
Ну и соответственно,
k-сочетание первого типа оказывается в точности C из n − 1 по k − 1 штука.
Так, ну давайте подумаем, а сколько есть k-сочетаний второго типа.
То есть таких k-сочетаний, которые не содержат объект a1 второго типа.
Ну с одной стороны, можно сразу догадаться,
потому что мы же хотим доказать наше тождество, а с другой стороны,
ну чего, понятно, вот есть элемент a1.
Мы знаем, что наше k-сочетание принадлежит второму типу, то есть a1, оно не содержит.
Ну давайте, я его, наоборот, перечеркну.
То есть, этот элемент ни в коем случае в наше k-сочетание теперь не входит.
А дальше, у нас снова есть элементы a2,
..., an, каковых по прежнему n − 1 штука.
Но теперь, для того чтобы сформировать k-сочетание второго типа,
мы уже не должны использовать элемент a1.
Вот он перечеркнут.
А мы можем лишь использовать любой из вот этих n − 1 элементов.
Ну то есть, мы из этого множества должны просто вытащить произвольное k-сочетание.
И в итоге получится k-сочетание второго типа.
Значит, вот отсюда вытаскиваем произвольное k-сочетание,
оно как раз не содержит элемент a1,
и таким образом мы получаем произвольное k-сочетание второго типа.
Но ясно, что таковых C из n − 1 по k.
И если вспомнить, что множество k-сочетаний первого типа вместе
с множеством k-сочетаний второго типа исчерпывают множество всех k- сочетаний.
И при этом, конечно, те, кто относится к первому типу, и те,
кто относится ко второму – это разные k-сочетания.
Мы получаем, что общее число k-сочетаний,
это есть число k-сочетаний первого типа плюс число k-сочетаний второго типа.
И как видите, мы даже могли не знать никакой формулы для каждой из этих C,
для каждого из биномиальных коэффициентов, желая доказать вот это тождество.
Чисто комбинаторное такое вот, аккуратное рассуждение.
Для тех, кто этого не знал, я думаю, что это должно звучать достаточно красиво.
Видите, никаких приведений к общему знаменателю, никакфакториалов дурацких,
– просто вот, чисто комбинаторное рассуждение.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
