Треугольник Паскаля

Loading...

From the course by Moscow Institute of Physics and Technology

Комбинаторика для начинающих

731 оценки

Moscow Institute of Physics and Technology

Комбинаторика для начинающих

731 оценки

Комбинаторика для начинающих - это базовый курс, закладывающий самые основы комбинаторного знания. На этом курсе слушатели, которые почти не знают комбинаторику или прочно ее забыли, откроют ее для себя впервые или заново. Курс очень полезен всем, кому трудно с ходу включиться в продвинутый курс современной комбинаторики. Однако фактические бонусы те же: в итоге человек, прослушавший курс, получит путевку в увлекательный мир комбинаторных задач и их далеко идущих приложений. Более того, даже в нем самом мы уже расскажем об инструментах, позволяющих решать некоторые задачи такой важной прикладной области знаний, как биоинформатика. Курс состоит из 7 учебных недель и экзамена. Каждую неделю слушателю предлагается выполнить тест, составляющий 10% от общей оценки. Экзамен состоит из задач по всему курсу и составляет 30% от общей оценки. Для получения сертификата необходимо набрать не менее 50% от общей суммы баллов. Данный курс является упрощённой версией курса "Современная комбинаторика" и рекомендуется к прохождению перед курсом "Теория вероятностей для начинающих".

From the lesson

Комбинаторные тождества

Темы этой недели: бином Ньютона и треугольник Паскаля, и разные полезные комбинаторные тождества. Также мы будем выбирать посуду и слова из чётного количества букв.

Бином Ньютона для степеней 2,3,49:30

Доказательство формулы Бинома Ньютона (*)12:59

Формулировка первых двух тождеств3:51

Доказательство первых двух тождеств(*)8:03

Треугольник Паскаля6:51

Meet the Instructors

Дмитрий Ильинский
преподаватель
кафедра дискретной математики МФТИ
Андрей Райгородский
профессор, доктор физико-математических наук
кафедра дискретной математики МФТИ

Замечательно то, что это тождество, которое мы только что доказали,

а мы его доказали, как видите.

Замечательно то,

что оно лежит в основе построения всех биномиальных коэффициентов.

Есть такой прекрасный объект,

который называется треугольник Паскаля.

Паскаль в свою очередь — это замечательный

математик и философ французский, который жил в XVII веке.

И вот, в частности, он придумал некий треугольник, который мы сейчас нарисуем,

который многие школьники знают, но вот не все все-таки.

Давайте вспомним, как можно сформировать все биномиальные коэффициенты.

Ну, давайте, во-первых, я вам напомню, что если вы возводите x + y.

Ну мы с вами в квадрат начинали возводить прошлый раз,

потом в третью степень, потом в четвертую.

Давайте начнем, совсем, так сказать, с яйца.

И будем возводить сначала в нулевую, потом в первую, потом в квадрат,

в куб и так далее.

То есть добавим еще нулевую и первую степень.

Понятно, что если x + y возводить в нулевую степень,

то это получится просто 1.

И никаких больше интересных слагаемых тут не будет.

Дальше, если вы возведете x + y в первую степень, то у вас получится x + y.

То есть множество биномиальных коэффициентов, которые присутствуют в этом

разложении – это 1 и 1, коэффициенты при x и y.

Дальше мы напишем x + y в квадрате.

Это будет x квадрат + 2xy + y квадрат.

То есть стало быть коэффициенты – это 1, 2, 1, правильно?

Ну я уж напомню все по полной программе,

чтобы как-то соответствовать прошлой лекции.

Здесь у нас будут коэффициенты 1, 3, еще раз 3.

Симметрия, повторяю, обусловлена первым тождеством,

которое мы доказали еще в прошлый раз.

И снова 1 при y в кубе.

Ну и давайте, наконец, x + y в четвертой для полноты картины и, повторяю,

для полного соответствия с тем, что было в прошлый раз.

Здесь у нас будет коэффициент 1, потом будет коэффициент 4.

Потом будет коэффициент 6 с квадрат y квадрат.

Дальше будет снова 4, xy в кубе, ну и 1 при y в четвертой степени.

Ну даже на этой картинке видно, что вырисовывается некий треугольник.

И это не удивительно,

потому что коэффициентов в разложении x + y в нулевой степени по биному 1.

Коэффициентов в первой степени – 2, в квадрате – 3.

В кубе – 4, ну и так далее,

то есть такое происходит расширение в форме треугольника.

И вот давайте выпишем просто эти коэффициенты.

1 – это единственный коэффициент, который возникает в разложении x + y в нулевой.

Дальше идет 1 1, вот буду рисовать прямо как треугольник.

Дальше идет 1 2 1.

Дальше 1 3 3 1 1

4 6 4 1 и так далее.

А теперь, товарищи, посмотрите, пожалуйста,

на принцип формирования этого треугольника.

Вот если вы глядите на него, то вы видите некую закономерность.

Ну здесь единица, она ж называется и в Африке единица,

тут как-то вот некий базис такой, вершинка этого треугольника.

Дальше идут 2 единицы, но, по большому счету,

они тоже в своей Африке находятся, то есть – это тоже некий базис.

Вот, а дальше начинается понятное формирование.

По бокам все время стоят единицы,

а вот эта вот двойка – это сумма вот этих 2 единиц.

Двойка – это сумма 2 единиц.

Тройка – это сумма единицы и двойки.

Эта тройка – это сумма двойки и единицы.

Четверка – это сумма 1 и 3.

Шесть – это сумма 3 и 3.

Четверка – это сумма 3 и 1.

Ну а единица, она уже обрамляющая.

То есть, такой очень понятный принцип формирования.

То есть я могу вот это многоточие стереть и попробовать порисовать дальше,

не выписывая явно никакие степени.

А именно обрамляю единицей, складываю 1 и 4, получаю 5.

Складываю 4 и 6, получаю 10.

6 и 4 тоже получаю 10, 4 и 1 – получаю 5,

ну и дальше ставлю обрамляющую единицу.

И давайте я нарисую многоточие.

Дальше я могу формировать этот треугольник до бесконечности, пользуясь ровно этим.

Но откуда такое свойство?

Почему это верно?

Ну а ровно, потому что у нас было справедливо вот это тождество.

Ведь это тождество – это и есть утверждение о том,

что очередной биномиальный коэффициент c из n по

k это есть c из n-1 по k-1 плюс c из n-1 по k.

Вот так вот, смотрите.

Вот это, фактически, c из n по k.

С определенными n и k.

Вот это строчкой выше – это c из n − 1 по k − 1.

При этом мы сместились влево, поэтому по k − 1.

А здесь мы смещаемся по диагонали вправо, поэтому это будет просто по k.

C из n-1 по k.

K − это просто номер элемента внутри строчки, а n – это номер строчки.

То есть вот это вот – это c из 0 по 0.

Если хотите, ну c из 0 по 0 равняется по определению равняется 1.

Из ничего выбрать ничто можно ровно одним способом, и это вполне согласуется,

что у нас 0 факториал равен единице.

Соответственно вот это – c из 1 по 0.

Вот это c из 1 по 1, ну и так далее.

Такой вот замечательный принцип формирования так называемого треугольника

Паскаля.

Если вы не хотите честно раскрывать скобки.

Если вы не хотите честно считать биномиальные коэффициенты по формулам с

факториалами, то вы вполне можете вот так вот портянку такую вырисовывать и в конце

концов вы найдете всю последовательность коэффициентов очередного бинома.

То есть такое нехитрое искусство.

И многие тождества комбинаторные, которыми мы сейчас еще пожонглируем,

они так или иначе пляшут вокруг различных свойств этого самого треугольника Паскаля.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play