Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".
Доказательство формулы Бинома Ньютона (*)
Loading...
En provenance du cours de Moscow Institute of Physics and Technology
Комбинаторика для начинающих
771 notes
À partir de la leçon
Комбинаторные тождества
Темы этой недели: бином Ньютона и треугольник Паскаля, и разные полезные комбинаторные тождества. Также мы будем выбирать посуду и слова из чётного количества букв.
Rencontrer les enseignants
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Итак, доказываем бином.
Просто все, сейчас будет.
Доказательство.
Значит, нам надо с вами взять выражение (x + y) и возвести в
какую-то там n-ную степень.
Ну, это означает, что у нас есть n одинаковых
скобок (x + y), (x + y) *...
* (x + y).
Всего n таких скобок, и вот их надо как-то перемножить.
Ну, если вы прочно забыли, как перемножаются скобки, то,
конечно, тут уже все.
Это уже будет проблема.
Но, наверное, вы помните, как перемножаются скобки.
Как? Мы берем первую скобку и выбираем из нее
какую-нибудь из двух вот этих переменных: то ли x, то ли y.
Ну, скажем, x выбираем.
Но кого-то одного должны выбрать обязательно.
Потом берем вторую скобку и из нее выбираем то ли x, то ли y.
Ну допустим, тоже выбрали x.
Берем третью скобку, из нее какую-то переменную выбираем, скажем, y.
И так дальше, пока не дошли до n-ной скобки.
Из каждой скобки мы выбираем ровно одну из этих двух буковок,
ровно одну переменную и перемножаем эти переменные между собою.
Потом берем, как-нибудь по-другому выбираем эти переменные.
Отсюда, скажем, не x берем, а y, а дальше, например, все то же самое, что и раньше.
То есть каждый раз мы как-то по-своему выбираем буковки из
соответствующих скобок.
В итоге, естественно, получаются слагаемые.
Давайте я буду писать вот так.
Какие-то.
Дальше появляется слагаемое, например, такое.
Давайте считать, что у нас из k скобок, из k скобок из вот этих n взят x.
А из остальных (n − k) скобок, соответственно, y.
Из k скобок взят x,
а из (n − k) скобок взят y.
Но тогда при перемножении у нас возникнет x в k-той степени,
потому что ровно k раз мы взяли x и сам на себя k раз, соответственно, умножили.
* y в степени (n − k).
Ну, тоже совершенно понятно, потому что у нас было (n − k) скобок,
из которых взяли по y.
y всего (n − k) штук, мы их перемножили, и возникло выражение вот такого вида.
Видите, уже что-то напоминает.
Очень похоже на то утверждение, которое мы с вами и хотели доказать.
Но на самом деле вот здесь вот я бы
оставил некое свободное место, а именно смотрите,
вот это x в k-той степени * y в (n − k)-той степени,
оно ведь возникает не единственным образом.
Давайте опять пример, чтобы было совсем понятно.
Пусть, скажем, n = 3.
Тогда вот у нас есть это выражение: (x + y)(x + y) (x + y).
И для определенности возьмем, скажем...
Вот так напишем: многоточие x в квадрате * y.
И здесь я специально оставил пустое место для того, чтобы понять,
как именно может образоваться вот такое выражение при раскрытии скобок.
Смотрите, как оно может образоваться.
Мы можем взять, вот из этой скобки вытащить x,
из этой скобки вытащить x, а из этой скобки вытащить y.
Тогда при перемножении, конечно, у нас получится, x квадрат y, это понятно.
Но можно действовать и по-иному.
Можно вот из этой скобки взять x, из этой скобки взять x, а из этой скобки взять y.
Вроде бы это другой способ раскрытия, правильно?
И такой тоже присутствует в нашем процессе раскрытия скобок.
Тем не менее, он дает абсолютно тот же самый результат.
x в квадрате y.
Ну и есть третий вариант, при котором такое действие возможно.
а именно мы извлекаем x отсюда,
извлекаем x из этой скобки, а из этой скобки извлекаем y.
И снова получаем x в квадрате * y.
Это третий отдельный способ.
Никаких других, если вы внимательно посмотрите, нету,
поэтому получается + 3 x квадрат y, ну, дальше...
То есть мы просто привели то, что называется, подобные слагаемые,
как в школе учат.
Взяли одинаковые выражения, которые получились
при разном способе выбора x из скобок и сложили их между собой.
Их получилось 3 штуки.
Вот хочется вместо этой галочки нарисовать какой-то коэффициент,
то есть какое-то число, которое бы означало, вот сколько есть различных
способов выбрать k скобок среди вот этих наших n возможных,
из которых мы затем будем извлекать x.
Видите, мы здесь выбрали фактически две скобки из трех возможных,
и из этих скобок извлекали x.
В первом случае мы выбрали первые две скобки,
извлекли из них x, y по остаточному принципу.
Во втором случае мы выбрали...
Где тут у нас второй случай?
Во втором случае мы выбрали последние две скобки,
извлекли из них x, y по остаточному принципу.
И в третьем случае мы выбрали первую скобку и последнюю скобку,
извлекли из этих скобок x, ну а y по остаточному принципу, вот он здесь.
То есть мы просто посчитали количество способов
зафиксировать две скобки, из которых будет извлекаться x,
и это количество способов, ну очевидно, оказалось равным 3.
Потому что всего было три скобки, и из этих трех скобок нужно было выбрать две
для последующего взятия из них x и перемножения этих x между собою и с y.
Ну вроде бы понятно, что здесь происходит.
Вот у нас есть n скобок, которые,
как и в доказательстве формулы для C из n по k с чертой на финальном этапе...
Нет, это не бараны никакие, на финальном этапе.
Мы эти n скобок можем считать тоже объектами.
Это тоже объекты.
Давайте их как-нибудь обозначим: b1...
bn. b1 — это первая скобка,
b2 — это вторая скобка, bn — это последняя, n-ная скобка.
И вот из этих n скобок нам нужно выбрать какие-то k скобок,
из которых мы затем будем извлекать x, и эти x перемножать.
Есть n скобок,
из них надо выбрать,
выбрать k скобок.
Ну давайте я уж не буду это писать: из каждой из которых мы возьмем x,
x перемножим, y возьмем из остальных,
y перемножим и получим вот это общее выражение x в k-той * y в (n − k)-той.
Ну спрашивается, сколькими способами из n объектов скобок можно выбрать k штук?
Опять, нам как-нибудь важен порядок этих скобок?
Вот смотрите, например, мы же не глядели на то, в каком порядке эти x извлекаются.
Просто мы взяли и зафиксировали кучку из двух скобок.
Вот одна кучка из двух скобок, вот другая кучка из двух скобок,
и вот третья кучка из двух скобок.
Ну таких кучек, естественно, C из n по k.
Это k-сочетание.
Естественно, все скобки разные, и порядок их нам не важен.
Число таких способов
выбрать из n объектов k неупорядоченных — C из n по k.
Ну а это в точности и означает,
что когда мы раскрываем скобки, у нас ровно столько раз — C из n по k —
возникает величина x в k-той * y в (n − k)-той.
Вот давайте я галочку аккуратненько заменю на C из n по k.
Ну и многоточие нарисую, наверное, справа тоже, подразумевая, что
при каждом отдельно взятом k получается свое вот именно такое слагаемое.
Вообще-то формулу бинома мы с вами доказали,
потому что это ровно то, что заявлялось в формулировке за маленьким,
может быть, небольшим замечанием.
Дело в том, что, честно говоря, покуда я писал доказательство,
я забыл, в какой последовательности я складывал слагаемые в формулировке.
Давайте вернемся к формулировке и посмотрим на нее внимательно.
То есть смотрите, я утверждаю, что теорема доказана.
Вот надо, чтобы была отсечка: все, теорему «бином Ньютона» я доказал.
Но сейчас для того, чтобы ни у кого не возникло каких-то вопросов и
недопониманий, я сделаю еще один полезный комментарий, и на этом, наверное,
сегодняшнюю лекцию закончу, потому что мне кажется, что она уже получилась достаточно
объемной для восприятия, нужно как-то осознать, что происходит.
Ну смотрите, я писал вот так: (x + y) в n-ной
степени = сумма по k от 0 до n C из n по k,
наверное, y в k-той...
Нет, y...
Как же я писал?
По-моему, я писал вот так изначально.
По-моему, я писал вот так.
Да, наверное, y в k-той, да, все правильно, зря стер, * x в (n − k)-той.
Все, я вспомнил, я писал вот так.
Точно, точно, я писал вот так.
Но кажется, что я сейчас стал писать вот так.
x в k-той * y в (n − k)-той.
И слушатели, которые не совсем моментально схватывают,
что тут происходит, они могут подумать, что я где-то ошибся или их обманул.
Ничего подобного.
Конечно же, это в точности то же самое,
что сумма по k от 0 до n * C из n по k * x в k-той * y в (n − k)-той.
Вот это очень важный момент.
Помните симметрию, которая была в тех формулах,
которые я приводил в начале для примера?
Когда я в куб возводил, да?
Там было вот так: x в кубе + 3x²y
+ 3 xy² + y³.
Потом было x⁴ + 4x³y + 6x²y² + y⁴.
Ой, извините, + Что-то я...
Так.
+ 4xy³ + y⁴.
Абсолютная симметрия, видите?
Тут коэффициенты 1, тут коэффициенты 4,
ну и центральный коэффициент такой вот красивый, 6, выделяется.
Мы потом обсудим, как они себя ведут, это очень интересный момент.
Но это не сегодня мы сделаем.
Вот. То есть видна полная симметрия.
Эта-то симметрия и означает,
что записать в таком порядке и в таком порядке суммирование можно.
А все дело в том, что, конечно же, друзья мои,
C из n по k — это абсолютно то же самое, что C из n по (n − k).
Ведь C из n по k по формуле, которую мы сегодня доказали — это n!
/ (k!
* (n − k)!) А C из n по (n − k) опять же по той самой формуле,
которую мы сегодня доказали — это есть n!
/ (n − k)!
А дальше надо из n вычесть (n − k), и от этого взять факториал.
Ну это, конечно, есть k!
И это, конечно, равные величины.
То есть симметрия обусловлена просто вот этим вот замечательным, очень легким,
очень понятным тождеством C из n по k и C из n по (n − k) суть одно и то же.
Именно поэтому C из n по 0 и C из n по n суть одно и то же.
C из n по 1 и C из n по (n − 1) суть одно и то же.
Ну и если n является четным числом, тогда в серединке возникает нечто,
у которого нету пары.
Но все остальное спаривается.
Вот.
Поэтому написать в таком порядке суммирование или написать суммирование в
таком порядке — от этого ничего не зависит.
Это роли не играет.
Ну и, собственно, в доказательстве, конечно, я тоже мог рассуждать, говоря не
про x в k-той * y в (n − k)-той, а наоборот, про x в (n − k)-той * y в k-той.
И коэффициент, естественно, получился бы тем же самым.
Вот.
Все.
Бином доказан, откомментирован, пользуйтесь, радуйтесь.
На сегодня все.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
