Мы им все пользовались в школе, но не знали об этом
Продолжаем рассказывать о разных формулах и подходах из математики, которые часто применяются в ИТ и в привычных алгоритмах. Сегодня будет про бином Ньютона — про него много кто слышал, но не все представляют, что это и зачем это нужно. Сейчас разложим по полочкам.
Чтобы понять бином Ньютона, нам понадобится треугольник Паскаля.
Что такое треугольник Паскаля
Треугольник Паскаля — это одно из названий треугольной таблицы чисел. Его назвали в честь математика Блеза Паскаля, но про такой треугольник математики знали тысячу лет назад.
Работает треугольник так: берём единицу (это будет вершина треугольника), а все остальные числа в каждом ряду получаем сложением левых и правых чисел, которые стоят выше. Если нарисовать, то получится так:
Такой треугольник можно продолжать бесконечно. В математике этот треугольник обладает разными полезными свойствами, но нам он нужен для биномиальных коэффициентов в биноме Ньютона. Вот теперь поговорим про бином.
Что такое бином Ньютона (просто)
Бином Ньютона — это формула, которая помогает посчитать сумму двух чисел, возведенную в какую-то степень.
Разбираем по полочкам:
- У нас есть некие числа a и b. Мы не знаем какие, потому что алгебра.
- Не зная, что это за числа, мы их складываем.
- Эту сумму почему-то очень хочется возвести в какую-то степень — в квадрат, в куб, в четвертую, хоть в девятьсот девяносто девятую — алгебре плевать на ваши чувства.
- Нам нужна формула, как это сделать. Вот эта формула и есть бином Ньютона.
Из школьной программы мы помним такую формулу: (a + b)2 = a2 + 2ab + b2 — это частный случай бинома Ньютона для квадрата суммы.
Может быть, вы помните сумму в кубе: (a + b)3 = a3 + 3a2b + 3ab2 + b3 — это тоже бином Ньютона.
А что если нам нужно возвести сумму не в квадрат, не в куб, а в сто сорок шестую степень? Какая тогда будет формула? Вот для этого нам нужна более обобщенная формула, которая опишет вообще все варианты биномов для любой степени.
Заглянуть в глаза ужасу
Вот как эта формула выглядит в общем виде:
Про знак Σ мы уже говорили — это обозначение суммы, а цифры в больших скобках — это биномиальные коэффициенты. В общем виде они считаются так:
Исходя из этой адской формулы для расчета бинома на компьютере нам нужно будет много раз посчитать факториал — это произведение всех целых чисел от единицы до заданного числа. Например, 5! = 1 × 2 × 3 × 4 × 5 = 120. А факториалы в силу своей цикличности жрут довольно много оперативной памяти. Может так получиться, что мы не сможем посчитать коэффициенты бинома, потому что закончилась оперативка.
Но, оказывается, необязательно считать факториалы — есть способ проще.
Биномиальные коэффициенты и треугольник Паскаля (простая теория в картинках)
Тут нам приходит на помощь треугольник Паскаля. Оказывается, числа в каждом ряду — это биномиальные коэффициенты для каждой степени n:
На практике это работает так: допустим, что по ходу работы алгоритма нам нужно раскрыть скобки и вычислить (x + y)⁴. Применим сюда бином Ньютона и треугольник Паскаля:
Получается, что с помощью этого треугольника можно не считать все эти формулы с факториалами, а быстро находить нужные коэффициенты, подставлять их в формулу бинома и сразу получать ответ. Так можно разложить любой бином и получить ответ гораздо быстрее, чем вычисляя все факториалы подряд.
Где используется бином Ньютона
Кроме математики, где бином нужен для комбинаторики и разных полезных формул, он часто применяется в программировании. Например, с его помощью можно обойти ограничение на размер оперативной памяти при возведении большого числа в степень: его можно разложить на сумму двух чисел поменьше и посчитать слагаемые через бином.
Также биномиальные коэффициенты часто применяются в матрицах и операциях с векторами — а именно на матрицах построены почти все нейросети. Поэтому если мы сможем быстро находить нужный коэффициент и применять его к матрице, то сможем быстрее создавать дипфейки и генерировать реалистичные пейзажи. Строго говоря, для этого сейчас нужно просто знать команду import, потому что готовых библиотек на эту тему — вагон, без всяких биномов.
А ещё на биномиальных коэффициентах работает отдельная непозиционная система счисления — её применяют в проектах, где надо быстро перебирать много различных вариантов и их возможных сочетаний.
Что дальше
Дальше мы попробуем применить эти знания и алгоритмы на практике: напишем код, который использует бином Ньютона для решения разных хитрых бытовых задач.