Всё очень несложно и запоминается на всю жизнь. Кстати, самостоятельно вспомнить и вывести формулу бинома Ньютона, нарисовав на черновике треугольник Паскаля, тоже намного проще.
Некоторые историки науки приписывают Блезу Паскалю авторство не только треугольника, позволяющего находить биномиальные коэффициенты, но и самой формулы бинома. Они считают, что Паскаль вывел её несколько раньше Ньютона, а тот лишь обобщил формулу для разных показателей степеней.
Что такое бином Ньютона и почему им всех пугают
Продолжаем рассказывать о разных формулах и подходах из математики, которые часто применяются в ИТ и в привычных алгоритмах. Сегодня будет про бином Ньютона — про него много кто слышал, но не все представляют, что это и зачем это нужно. Сейчас разложим по полочкам.
Чтобы понять бином Ньютона, нам понадобится треугольник Паскаля.
Что такое треугольник Паскаля
Треугольник Паскаля — это одно из названий треугольной таблицы чисел.
Его назвали в честь математика Блеза Паскаля, но про такой треугольник математики знали тысячу лет назад.
Работает треугольник так: берём единицу (это будет вершина треугольника), а все остальные числа в каждом ряду получаем сложением левых и правых чисел, которые стоят выше. Если нарисовать, то получится так:
Такой треугольник можно продолжать бесконечно. В математике этот треугольник обладает разными полезными свойствами, но нам он нужен для биномиальных коэффициентов в биноме Ньютона. Вот теперь поговорим про бином.
Что такое бином Ньютона (просто)
Бином Ньютона — это формула, которая помогает посчитать сумму двух чисел, возведенную в какую-то степень.
Разбираем по полочкам:
- У нас есть некие числа a и b. Мы не знаем какие, потому что алгебра.
- Не зная, что это за числа, мы их складываем.
- Эту сумму почему-то очень хочется возвести в какую-то степень — в квадрат, в куб, в четвертую, хоть в девятьсот девяносто девятую — алгебре плевать на ваши чувства.
- Нам нужна формула, как это сделать. Вот эта формула и есть бином Ньютона.
Из школьной программы мы помним такую формулу: (a + b)2 = a2 + 2ab + b2 — это частный случай бинома Ньютона для квадрата суммы.
Может быть, вы помните сумму в кубе: (a + b)3 = a3 + 3a2b + 3ab2 + b3 — это тоже бином Ньютона.
А что если нам нужно возвести сумму не в квадрат, не в куб, а в сто сорок шестую степень? Какая тогда будет формула? Вот для этого нам нужна более обобщенная формула, которая опишет вообще все варианты биномов для любой степени.
Вот как эта формула выглядит в общем виде:
Про знак Σ мы уже говорили — это обозначение суммы, а цифры в больших скобках — это биномиальные коэффициенты. В общем виде они считаются так:
Исходя из этой адской формулы для расчета бинома на компьютере нам нужно будет много раз посчитать факториал — это произведение всех целых чисел от единицы до заданного числа.
Но, оказывается, необязательно считать факториалы — есть способ проще.
Биномиальные коэффициенты и треугольник Паскаля (простая теория в картинках)
Тут нам приходит на помощь треугольник Паскаля. Оказывается, числа в каждом ряду — это биномиальные коэффициенты для каждой степени n:
На практике это работает так: допустим, что по ходу работы алгоритма нам нужно раскрыть скобки и вычислить (x + y)⁴. Применим сюда бином Ньютона и треугольник Паскаля:
Получается, что с помощью этого треугольника можно не считать все эти формулы с факториалами, а быстро находить нужные коэффициенты, подставлять их в формулу бинома и сразу получать ответ. Так можно разложить любой бином и получить ответ гораздо быстрее, чем вычисляя все факториалы подряд.
Где используется бином Ньютона
Кроме математики, где бином нужен для комбинаторики и разных полезных формул, он часто применяется в программировании.
Например, с его помощью можно обойти ограничение на размер оперативной памяти при возведении большого числа в степень: его можно разложить на сумму двух чисел поменьше и посчитать слагаемые через бином.
Также биномиальные коэффициенты часто применяются в матрицах и операциях с векторами — а именно на матрицах построены почти все нейросети. Поэтому если мы сможем быстро находить нужный коэффициент и применять его к матрице, то сможем быстрее создавать дипфейки и генерировать реалистичные пейзажи. Строго говоря, для этого сейчас нужно просто знать команду import, потому что готовых библиотек на эту тему — вагон, без всяких биномов.
Запускаем нейросеть на домашнем компьютере
А ещё на биномиальных коэффициентах работает отдельная непозиционная система счисления — её применяют в проектах, где надо быстро перебирать много различных вариантов и их возможных сочетаний.
Что такое непозиционная система счисления
Что дальше
Дальше мы попробуем применить эти знания и алгоритмы на практике: напишем код, который использует бином Ньютона для решения разных хитрых бытовых задач.
Текст:
Михаил Полянин
Редактор:
Максим Ильяхов
Художник:
Алексей Сухов
Корректор:
Ирина Михеева
Вёрстка:
Кирилл Климентьев
Соцсети:
Виталий Вебер
3.1 Биномиальная теорема Ньютона
Напомним, что $${n\выберите k}={n!\более k!\,(n-k)!}={n(n-1)(n-2)\cdots(n-k+1)\over к!}.$$ Выражение справа имеет смысл, даже если $n$ не является неотрицательное целое число, если $k$ — целое неотрицательное число, и мы поэтому определите $${r\выбрать k}={r(r-1)(r-2)\cdots(r-k+1)\более k!}$$ когда $r$ — действительное число. Например, $${1/2\выберите 4}={(1/2)(-1/2)(-3/2)(-5/2)\более 4!}={-5\более128} \quad\hbox{и}\quad {-2\выберите 3}={(-2)(-3)(-4)\более 3!}=-4. $$ Эти 9{-n}$ — производящая функция для ${n+i-1\choose n-1}$, количество подмножеств $\{\infty\cdot1,\infty\cdot2,\ldots,\infty\cdot n\}$ размера $i$. $\квадрат$
Во многих случаях можно напрямую построить производящую
функция, коэффициенты которой решают задачу подсчета.
{16} + 19{16}$ 180.
Пример 3.1.4 Используйте производящую функцию, чтобы найти количество решений $\ds x_1+x_2+x_3+x_4=14$, где $0\le x_1\le3$, $2\le x_2\le5$, $0\le x_3\le5$, $4\le x_4\le6$.
Пример 3.1.5 Найдите производящую функцию для количество решений для $\ds x_1+x_2+x_3+x_4=k$, где $0\le x_1\le\infty$, $3\le x_2\le\infty$, $2\le x_3\le5$, $1\le x_4\le5$.
Пример 3.1.6 Найдите производящую функцию для числа неотрицательных целых чисел решения задачи $3x+2y+7z=n$.
Пример 3.1.7 Предположим, у нас есть большой запас красных, белых и синих воздушных шаров. Как там много разных связок по 10 шаров, если каждая связка должна иметь хотя бы по одному шарику каждого цвета и столько же белых шариков должно быть четным?
Пример 3.1.8 Используйте производящие функции, чтобы показать, что каждое положительное целое число может быть
записано ровно одним способом в виде суммы различных степеней числа 2.
Пример 3.1.9 Предположим, у нас есть большой запас синих и зеленых свечей и одна золотая свеча. Сколько существует наборов из $n$ свечей, в которых количество синих свечей четное, количество зеленых свечей любое, а количество золотых свечей не больше одной? 94 \end{array}$$$
(В случае, когда в биноме отрицательный знак, знаки развёртки должны чередоваться следующим образом $$+ \ -\ +\ -\ +\ -\ \ ldots$$)
Треугольник Паскаля
Паскаль разработал простой способ вычисления комбинаторных чисел (хотя в некоторых текстах эта идея приписывается Тарталье):
$$$ \begin{array}{ccccccccccc} & & & & & 1 & & & & & & \\ & & & & 1 & & 1 & & & & \\ & & & 1 & & 2 & & 1 & & & \\ & & 1 & & 3 & & 3 & & 1 & & \\ & 1 & & 4 & & 6 & & 4 & & 1 & \\ 1& & 5 & & 10 & & 10 & & 5 & & 1 \end{массив}$$$
Метод получает название треугольника Паскаля и строится в следующем виде (ребристые линии и сверху вниз):
- В вершине помещается $$1$$.
