С помощью чего можно легко найти биномиальные коэффициенты
Перейти к содержимому

С помощью чего можно легко найти биномиальные коэффициенты

  • автор:

Расчет биномиальных коэффициентов с использованием Фурье-преобразований

При решении задач комбинаторики часто возникает необходимость в расчете биномиальных коэффициентов. Бином Ньютона, т.е. разложение imageтакже использует биномиальные коэффициенты. Для их расчета можно использовать формулу, выражающую биномиальный коэффициент через факториалы: imageили использовать рекуррентную формулу: imageИз бинома Ньютона и рекуррентной формулы ясно, что биномиальные коэффициенты — целые числа.

Одним из методов, позволяющих значительно сократить количество вычислений, является применение Фурье преобразований и дискретных Фурье преобразований.

Наличие большого числа библиотек, реализующих Фурье преобразований (во всевозможных вариантах быстрых версий), делает реализацию алгоритмов не очень сложной задачей для программирования.
Реализованные алгоритмы являются частью библиотеки с открытым исходным кодом FFTTools. Интернет-адрес: github.com/dprotopopov/FFTTools

Преобразование Фурье функции f вещественной переменной является интегральным и задаётся следующей формулой:

Преобразование Фурье

Разные источники могут давать определения, отличающиеся от приведённого выше выбором коэффициента перед интегралом, а также знака «−» в показателе экспоненты. Но все свойства будут те же, хотя вид некоторых формул может измениться.

Кроме того, существуют разнообразные обобщения данного понятия.

Дискретное преобразование Фурье

Дискретное преобразование Фурье (в англоязычной литературе DFT, Discrete Fourier Transform) — это одно из преобразований Фурье, широко применяемых в алгоритмах цифровой обработки сигналов (его модификации применяются в сжатии звука в MP3, сжатии изображений в JPEG и др.), а также в других областях, связанных с анализом частот в дискретном (к примеру, оцифрованном аналоговом) сигнале. Дискретное преобразование Фурье требует в качестве входа дискретную функцию. Такие функции часто создаются путём дискретизации (выборки значений из непрерывных функций). Дискретные преобразования Фурье помогают решать дифференциальные уравнения в частных производных и выполнять такие операции, как свёртки. Дискретные преобразования Фурье также активно используются в статистике, при анализе временных рядов. Существуют многомерные дискретные преобразования Фурье.

Формулы дискретных преобразований

image

image

Дискретное преобразование Фурье является линейным преобразованием, которое переводит вектор временных отсчётов в вектор спектральных отсчётов той же длины. Таким образом преобразование может быть реализовано как умножение симметричной квадратной матрицы на вектор:

image

Свёртка двух функций

Согласно определению, свёрткой двух функций F и G называется функция FхG:

FхG(t) = SUM F(i)*G(j)|i+j=t

Фурье-преобразования для вычисления свёртки

Одним из замечательных свойств преобразований Фурье является возможность быстрого вычисления корреляции двух функций определённых, либо на действительном аргументе (при использовании классической формулы), либо на конечном кольце (при использовании дискретных преобразований).

И хотя подобные свойства присущи многим линейным преобразованиям, для практического применения, для вычисления операции свёртки, согласно данному нами определению, используется формула

FхG = BFT ( FFT(F)*FFT(G) )

  • FFT – операция прямого преобразования Фурье
  • BFT – операция обратного преобразования Фурье

Биномиальные коэффициенты

Рассмотрим полином F(x)=1+x и его свёртку с самим собой n раз
Fx..xF = SUM С( i, n-1 )*x^i = BFT ( FFT(F)*. *FFT(F) ) = BFT ( FFT(F)^(n-1) )
То есть биномиальные коэффициенты С( i, n-1 ) могут быть получены из значений коэффициентов полинома (1+x)^(n-1)

Программируем:

using System; using System.Drawing; using System.Linq; using System.Numerics; namespace FFTTools < public class BinomialBuilder : BuilderBase, IBuilder < /// /// Performs application-defined tasks associated with freeing, releasing, or resetting unmanaged resources. /// public void Dispose() < >public static void GetLongs(long[] array, long x = 1) < var n = array.Length - 1; if (array.Length >0) array[0] = 1; for (var i = 0; i < n; i++) array[i + 1] = x*array[i]*(n - i)/(i + 1); >public static void GetDoubles(double[] array, double x = 1.0) < var complex = new Complex[array.Length]; if (array.Length >0) complex[0] = Complex.One; if (array.Length > 1) complex[1] = x; if (array.Length > 0) < Fourier(complex, FourierDirection.Forward); complex = complex.Select( value =>Complex.Pow(value, array.Length - 1)/array.Length).ToArray(); Fourier(complex, FourierDirection.Backward); > var index = 0; foreach (var value in complex) array[index++] = value.Real; > public Bitmap ToBitmap(Bitmap source) < throw new NotImplementedException(); >> > 

Проверяем:

using System; using System.Linq; using Microsoft.VisualStudio.TestTools.UnitTesting; namespace FFTTools.UnitTest < [TestClass] public class BinomialUnitTest < [TestMethod] public void BinomialTestMethod() < const int count = 10; var doubles = new double[count]; var longs = new long[count]; BinomialBuilder.GetLongs(longs); BinomialBuilder.GetDoubles(doubles); Console.WriteLine( string.Join(Environment.NewLine, longs.Zip(doubles, (x, y) =>string.Format(" - = ", x, y, x - y))) + Environment.NewLine); Assert.IsTrue(doubles.Zip(longs, (x, y) => x - y).All(x => Math.Abs(x) < 0.001)); >> > 

Зачем?

При вычислении с помощью треугольника Паскаля трудоёмкость имеет оценку O(n^2).
При вычислении с помощью быстрых Фурье-преобразований трудоёмкость имеет оценку O(n*log n).

Примечание:

P.S.
Трудоёмкость расчета биномиальных коэффициентов может быть уменьшена до O(n):
Cn[0]=1
Cn[i+1] = Cn[i]*(n-i)/(i+1)
Доказательство:
Cn[i]*(n-i)/(i+1) = n!/((n-i)!i!) * (n-i)/(i+1) = n!/((n-i-1)!(i+1)!) = Cn[i+1]

Бином Ньютона

Будьте внимательны! У Вас есть 10 минут на прохождение теста. Система оценивания — 5 балльная. Разбалловка теста — 3,4,5 баллов, в зависимости от сложности вопроса. Порядок заданий и вариантов ответов в тесте случайный. С допущенными ошибками и верными ответами можно будет ознакомиться после прохождения теста. Удачи!

Система оценки: 5 балльная

Список вопросов теста

Вопрос 1

Как называются соединения, каждое из которых содержит n элементов, взятых из данных m разных элементов, и которые отличаются друг от друга по крайней мере одним элементом?

Варианты ответов
  • Сочетаниями из m элементов по n в каждом
  • Перестановками из m элементов по n в каждом
  • Размещениями из m элементов по n элементов
Вопрос 2

Выберите верную формулу.

Варианты ответов
Вопрос 3

Отметьте верные равенства.

Варианты ответов
Вопрос 4

С помощью чего можно легко найти биномиальные коэффициенты?

Варианты ответов
  • С помощью треугольника Паскаля
  • С помощью прямоугольника Паскаля
  • С помощью многоугольника Паскаля
  • С помощью квадрата Паскаля
Вопрос 5

Чему равна данная сумма?

Вопрос 6

Вычислите

Вопрос 7

Отметьте верные утверждения.

Варианты ответов
  • Число членов многочлена, получаемого при записи разложения степени бинома, на единицу меньше показателя m степени бинома, т. е. равно m — 1.
  • Показатели степени первого слагаемого бинома последовательно убывают на единицу от m до 0, а показатели второго последовательно возрастают на единицу от 0 до m.
  • Биномиальные коэффициенты, равноудалённые от начала и конца разложения по формуле бинома Ньютона, равны между собой.
Вопрос 8

Чему равна данная сумма?

Вопрос 9

Какое из выражений является разложением бинома (x — 2) 4 ?

Варианты ответов
Вопрос 10

Какое из выражений является разложением бинома (1 + x) 7 ?

Расчет биномиальных коэффициентов на Си (С++) и Python

При решении задач комбинаторики часто возникает необходимость в расчете биномиальные коэффициентов. Бином Ньютона, т.е. разложение imageтакже использует биномиальные коэффициенты. Для их расчета можно использовать формулу, выражающую биномиальный коэффициент через факториалы: imageили использовать рекуррентную формулу: imageИз бинома Ньютона и рекуррентной формулы ясно, что биномиальные коэффициенты — целые числа. На данном примере хотелось показать, что даже при решении несложной задачи можно наступить на грабли.
Прежде чем перейти к написанию процедур расчета, рассмотрим так называемый треугольник Паскаля.

 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 

image

или он же, но немного в другом виде. В левой колонке строки значение n, дальше в строке значения для k=0..n

 n биномиальные коэффициенты 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 7 1 7 21 35 35 21 7 1 8 1 8 28 56 70 56 28 8 1 9 1 9 36 84 126 126 84 36 9 1 10 1 10 45 120 210 252 210 120 45 10 1 11 1 11 55 165 330 462 462 330 165 55 11 1 12 1 12 66 220 495 792 924 792 495 220 66 12 1 13 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 14 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1 15 1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1 16 1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1 

В полном соответствии с рекуррентной формулой значения imageравны 1 и любое число равно сумме числа, стоящего над ним и числа «над ним+шаг влево». Например, в 7й строке число 21, а в 6й строке числа 15 и 6: 21=15+6. Видно также, что значения в строке симметричны относительно середины строки, т.е. image. Это свойство симметричности бинома Ньютона относительно a и b и оно видно в факториальной формуле.
Ниже для биномиальных коэффициентов imageя буду также использовать представление C(n,k) (его проще набирать, да и формулу-картинку не везде можно вставить.

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

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

// расчет факториала n unsigned fakt(int n) < unsigned r; for (r=1;n>0;--n) r*=n; return r; > // расчет C(n,k) unsinged bci(int n,int k) < return fakt(n)/(fakt(k)*fakt(n-k)); >

Вызовем функцию bci(10,4) — она вернет 210 и это правильное значение коэффициента C(10,4). Значит, задача расчета решена? Да, решена. Но не совсем. Мы не ответили на вопрос: при каких максимальных значениях n,k функция bci будет работать правильно? Прежде чем начать искать ответ, условимся, что используемый нами тип unsigned int 4-х байтный и максимальное значение равно 2 32 -1=4’294’967’295. При каких n,k C(n,k) превысит его? Обратимся к треугольнику Паскаля. Видно, что максимальные значения достигаются в середине строки, т.е. при k=n/2. Если n четно, то имеется одно максимальное значение, а если n нечетно, то их два. Точное значение C(34,17) равно 2333606220, а точное значение C(35,17) равно 4537567650, т.е. уже больше максимального unsigned int.
Напишем тестовую процедуру

void test() < for (n=10;n<=35;++n) printf("%u %u",n,bci(n,n/2); // для C++ можно использовать cout<

Запустим ее и увидим

10 252 11 462 12 924 13 532 14 50 15 9 16 1 17 2 18 1 19 0 20 0 21 1 22 0 23 4 24 1 25 0 26 1 27 0 28 1 29 0 30 0 31 0 32 2 33 2 34 0 35 0 

Значение в очередной строке должно быть примерно в 2 раза больше, чем в предыдущей. Поэтому последний правильно вычисленный коэффициент (см треугольник выше) — это C(12,6) Хотя unsigned int вмещает 4млрд, правильно вычисляются значения меньше 1000. Вот те раз, почему так? Все дело в нашей процедуре bci, точнее в строке, которая сначала вычисляет большое число в числителе, а потом делит его на большое число в знаменателе. Для вычисления C(13,6) сначала вычисляется 13!, а это число > 6млрд и оно не влезает в unsigned int.
Как оптимизировать расчет image? Очень просто: раскроем 13! и сократим числитель и знаменатель на 7! В результате получится image. Запрограммируем расчет по этой формуле

unsigned bci(int n,int k) < if (k>n/2) k=n-k; // возьмем минимальное из k, n-k.. В силу симметричность C(n,k)=C(n,n-k) if (k==1) return n; if (k==0) return 1; unsigned r=1; for (int i=1; i <=k;++i) < r*=n-k+i; r/=i; >return r; > 

и снова протестируем

10 252 11 462 12 924 13 1716 14 3432 15 6435 16 12870 17 24310 18 48620 19 92378 20 184756 21 352716 22 705432 23 1352078 24 2704156 25 5200300 26 10400600 27 20058300 28 40116600 29 77558760 30 155117520 31 14209041 32 28418082 33 39374192 34 78748384 35 79433695 

Явно лучше, ошибка возникла при расчете C(31,15). Причина понятна — все то же переполнение. Сначала умножаем на 31 (оп-па — переполнение, потом делим на 15). А что, если использовать рекурсивную формулу? Там только сложение, переполнения быть не должно.
Что ж, пробуем:

unsigned bcr(int n,int k) < if (k>n/2) k=n-k; if (k==1) return n; if (k==0) return 1; return bcr(n-1,k)+bcr(n-1,k-1); > void test() < for (n=10;n<=35;++n) printf("%u %u",n,bcr(n,n/2); // для C++ можно использовать cout<

Результат теста

10 252 11 462 12 924 13 1716 14 3432 15 6435 16 12870 17 24310 18 48620 19 92378 20 184756 21 352716 22 705432 23 1352078 24 2704156 25 5200300 26 10400600 27 20058300 28 40116600 29 77558760 30 155117520 31 300540195 32 601080390 33 1166803110 34 2333606220 35 242600354 

Все, что влезло в unsigned int, посчиталось правильно. Вот только строчка с n=34 считалась около минуты. При расчете C(n,n/2) делается два рекурсивных вызова, поэтому время расчета экспоненциально зависит от n. Что же делать — получается либо неточно, либо медленно. Выход — в использовании 64 битных переменных.

Замечание по результатам обсуждений: в конце статьи добавлен раздел, где приведен простой и быстрый вариант «bcr с запоминанием» одного из участников обсуждения.

Использование 64 битных типов для расчета C(n,k)

Заменим в функции bci unsigned int на unsigned long long и протестируем в диапазоне n=34..68. n=34 — это максимальное значение, которое правильно считается bci, а C(68,34) ~2.8*10 19 уже не влезает в unsigned long long ~1.84*10 19

unsigned long long bcl(int n,int k) < if (k>n/2) k=n-k; if (k==1) return n; if (k==0) return 1; unsigned long long r=1; for (int i=1; i <=k;++i) < r*=n-k+i; r/=i; >return r; > void test() < for (n=34;n<=68;++n) printf("%llu %llu",n,bcl(n,n/2)); // для C++ можно использовать cout<

Результат теста

34 2333606220 35 4537567650 36 9075135300 37 17672631900 38 35345263800 39 68923264410 40 137846528820 41 269128937220 42 538257874440 43 1052049481860 44 2104098963720 45 4116715363800 46 8233430727600 47 16123801841550 48 32247603683100 49 63205303218876 50 126410606437752 51 247959266474052 52 495918532948104 53 973469712824056 54 1946939425648112 55 3824345300380220 56 7648690600760440 57 15033633249770520 58 30067266499541040 59 59132290782430712 60 118264581564861424 61 232714176627630544 62 465428353255261088 63 321255810029051666 64 66050867754679844 65 454676336121653775 66 350360427585442349 67 23341572944240599 68 46683145888481198 

Видим, что ошибка возникает при n=63 по той же причине, что и в bci. Сначала умножение на 63 (и переполнение), затем деление на 31.

Дальнейшее повышение точности и расчет при n>67
double bcd(int n,int k) < if (k>n/2) k=n-k; // возьмем минимальное из k, n-k.. В силу симметричности C(n,k)=C(n,n-k) if (k==1) return n; if (k==0) return 1; double r=1; for (int i=1; i <=k;++i) < r*=n-k+i; r/=i; >return ceil(r-0.2); // округлим до ближайшего целого, отбросив дробную часть // комментарий изменен после обсуждений: такой способ использован, чтобы расхождение с точным значением // было как можно позже. Где-то оно превышало 0.5 и простой round не годился > void testd() < for (n=50;n<=1000;n+=50) printf("%d %.16e\n",n,bcd(n,n/2)); // для C++ можно использовать cout<

Результат теста

50 1.2641060643775200e+014
100 1.0089134454556417e+029
150 9.2826069736708704e+043
200 9.0548514656103225e+058
250 9.1208366928185793e+073
300 9.3759702772827310e+088
350 9.7744946171567713e+103
400 1.0295250013541435e+119
450 1.0929255500575370e+134
500 1.1674431578827770e+149
550 1.2533112137626624e+164
600 1.3510794199619429e+179
650 1.4615494992533863e+194
700 1.5857433585316801e+209
750 1.7248900341772600e+224
800 1.8804244186835327e+239
850 2.0539940413411323e+254
900 2.2474718820660189e+269
950 2.4629741379276902e+284
1000 2.7028824094543663e+299

Даже для n=1000 удалось посчитать! Переполнение double произойдет при n=1030.
Расхождение расчета bcd с точным значением начинается с n=57. Он небольшое — всего 8. При n=67 отклонение 896.

Для экстремалов и «олимпийцев»

В принципе, для практических задач точности функции bcd достаточно, но в олимпиадных задачах часто даются тесты «на грани». Т.е. теоретически может встретится задача, где точности double недостаточно и C(n,k) влезает в unsigned long long еле-еле. Как избежать переполнения для таких крайних случаев? Можно использовать рекурсивный алгоритм. Но если он для n=34 считал минуту, то для n=67 будет считать лет 100. Можно запоминать рассчтанные значения (см Дополнение после публиукации).Также можно использовать рекурсию не для всех n и k, а только для «достаточно больших». Вот процедура расчета, которая считает правильно для n67 при малых k (к примеру, считает C(82,21)=1.83*10 19 ).

unsigned long long bcl(int n,int k) < if (k>n/2) k=n-k; if (k==1) return n; if (k==0) return 1; unsigned long long r; if (n+k>=90) < // разрядности может не хватить, используем рекурсию r=bcl(n-1,k); r+=+bcl(n-1,k-1); >else < r=1; for (int i=1; i<=k;++i) < r*=n-k+i; r/=i; >> return r; > 

В какой-то из олимпиадных задач мне потребовалось вычислять много C(n,k) для n >70, т.е. они заведомо не влезали в unsigned long long. Естественно, пришлось использовать «длинную арифметику» (свою). Для этой задачи я написал «рекурсию с памятью»: вычисленные коэффициенты запоминались в массиве и экспоненциального роста времени расчета не было.

Дополнение после публикации

При обсуждении часто упоминаются варианты с запоминанием рассчитанных значений. У меня есть код с динамическим выделением памяти, но я его не привел. На даный момент вот самый простой и эффективный из комментария chersanya: http://habrahabr.ru/post/274689/#comment_8730359http://habrahabr.ru/post/274689/#comment_8730359

 unsigned bcr_cache[N_MAX][K_MAX] = ; unsigned bcr(int n,int k) < if (k>n/2) k=n-k; if (k==1) return n; if (k==0) return 1; if (bcr_cache[n][k] == 0) bcr_cache[n][k] = bcr(n-1,k)+bcr(n-1,k-1); return bcr_cache[n][k]; > 

Если в программе надо использовать [почти] все коэффициенты треугольника Паскаля (до какого-то уровня), то приведенный рекурсивный алгоритм с запоминанием — самый быстрый способ. Аналогичный код годится и для unsigned long long и даже для длинной арифметики (хотя там, наверное, лучше динамически вычислять и выделять требуемый объем памяти). Конкретные значения N_MAX могут быть такими:
35 — посчитает все коэффициенты C(n,k), n < 35 для unsigned int (32 бита)
68 — посчитает все коэффициенты C(n,k), n < 68 для unsigned long long (64 бита)
200 — посчитает коэффициенты C(n,k), n < 200 и некоторых k для unsigned long long (64 бита). Например, для С(82,21)=~1.83*10 19
K_MAX — это может быть N_MAX/2+1, но не больше 35, поскольку C(68,34) за границей unsigned long long.
Для простоты можно всегда брать K_MAX=35 и не думать «войдет — не войдет» (до тех пор, пока не перейдем к числами с разрядностью >64 бита).

Расчет биномиальных коэффициентов на Python

Это дополнение появилось спустя примерно погода после публикации статьи. Автор начал осваивать Python и для тренироки я решаю олимпиадные задачи, сделанные ранее на C++. Для задач связанных в точными/длинными вычислениями приходится либо всячески исхитряться (как при расчетах биномиальных коэфиициентов), дабы избежать раннего переполнения, либо смиряться с потерей точности (перейдя к типу double) либо писать(или искать) длинную арифметику. В Python длинная арифметика уже есть, поэтому тут для вычисления биномиальных коэффициентов достаточно реализовать запоминание. Запоминать их будем в списке (передается в функцию как папаметр).

# при вызове функции заполняем все, что выше/левее # в списке биномиальных коэффициентов bcs храним значения, начиная с n=4 и k=2 def Binc(bcs,n,k): if (k>n): return 0 if k>n//2: k=n-k # страшую часть строки не храним - она симметрична if k==0: return 1 if k==1: return n while len(bcs) 

Вот вывод (без таблички)
270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320
0.4200884663301988
Меньше полсекуды для такого коэффициента
C(68,34) (напомню — он не влезает в long long) считается за 0.017 сек и равен 28453041475240576740

  • Биномиальные коэффициенты
  • расчет
  • треугольник Паскаля

Простыми словами: что такое бином Ньютона

Бином Ньютона — это совсем не rocket science. Смотрим в глаза страху и раскладываем по полочкам знаменитую формулу.

Иллюстрация: Катя Павловская для Skillbox Media

Дмитрий Зверев

Дмитрий Зверев

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

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

Поэтому, если видите себя в будущем в data science или криптографии, разобраться с биномом Ньютона будет полезно. А если даже и нет — сможете уверенно отвечать друзьям в духе: «Видал я этот ваш бином, там всё проще пареной репы». Тоже какой-никакой, но профит. А теперь к делу.

Что такое бином Ньютона

Бином Ньютона — это формула, которая помогает возвести сумму двух чисел в любую степень. Особенно она полезна, если степень большая.

Из уроков математики мы помним такую формулу: (a + b) 2 = a 2 + 2ab + b 2 . Это тоже бином Ньютона, а точнее — его частный случай для разложения на множители квадрата суммы.

Выглядит вроде бы просто. Но представьте, сколько нужно совершить операций умножения, чтобы возвести эту же сумму, например, в седьмую степень. В конечной формуле будет аж восемь слагаемых:

Чтобы упростить этот процесс и не тратить столько времени на простые арифметические операции, как раз и придумали бином Ньютона.

Разбираем формулу бинома Ньютона

Сорвём пластырь сразу — вот как выглядит та самая формула бинома Ньютона:

Сразу возникает миллион вопросов: что это за странная большая буква Е? Что такое C? И что вообще здесь происходит? Сейчас во всём разберёмся.

a и b — это два числа, которые мы складываем, а затем хотим возвести в степень n. Числа в скобках могут быть любыми — хоть положительными, хоть дробными, хоть отрицательными. А вот степень обязательно должна быть натуральным числом, то есть целым, положительным, не равным нулю.

Большая буква, похожая на Е, — это на самом деле «сигма», знак алгебраической суммы. Её используют, чтобы сократить длинные операции сложения. Например, такие:

То же самое выражение, записанное с помощью сигмы:

Здесь мы добавляем букву n, которая представляет собой все числа от 1 до 101 по порядку. Под знаком суммы мы указываем, с какого числа начинаем считать, а сверху — на каком заканчиваем. Получается, это выражение просуммирует все числа от 1 до 101 (ответ: 5151).

А вот как выглядит формула бинома Ньютона без знака суммы:

Получили очень много цифр и букв, в которых легко потеряться. Но не забывайте, что это общая формула, а значит, она может быть запутанной.

Теперь переходим к более сложным вещам — биномиальным коэффициентам, которые обозначаются буквой C. Они показывают, на какие числа нужно умножить каждое слагаемое в многочлене. Например, в выражении a 2 + 2ab + b 2 слагаемыми будут a 2 , ab и b 2 , а их коэффициентами: 1, 2 и 1.

Посчитать биномиальные коэффициенты можно с помощью этой формулы:

Здесь n — это степень, в которую мы возводим сумму двух чисел. k — номер слагаемого в многочлене (считается с нуля). Восклицательный знак — это символ факториала. Факториал — это произведение всех чисел от 1 до числа, стоящего под знаком факториала. Например, 4! = 1 × 2 × 3 × 4 = 24.

А покажите, как считать

С определениями закончили, теперь давайте попрактикуемся. Если сейчас что-то непонятно, сначала посмотрите примеры, а затем снова возвращайтесь к формуле.

Попробуем применить формулу бинома Ньютона к сумме a + b, возведённой в квадрат. Подставляем значения:

Теперь раскроем знак суммы и выпишем все слагаемые, но пока не будем считать биномиальные коэффициенты:

Теперь давайте немного упростим выражение. По свойствам степеней, если число возводится в нулевую степень, то оно равно единице. Поэтому b 0 и a 0 мы можем заменить на единицы:

Со степенями разобрались — теперь считаем биномиальные коэффициенты с помощью формулы:

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

Подставляем коэффициенты в нашу формулу:

Получаем наше выражение для квадрата суммы. Всё правильно.

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

Вычислим сразу коэффициенты:

�� Обратите внимание

Значения биномиальных коэффициентов повторяются. Первый равен последнему, а второй — четвёртому. Поэтому можно считать не все коэффициенты, а только половину (ну и ещё один «посередине», если степень многочлена чётная).

Сразу подставляем коэффициенты в сумму и считаем степени слагаемых:

Получаем нужное нам выражение. Можете проверить это выражение, перемножив все множители друг с другом. Если, конечно, вам хватит терпения ��

Как проще вычислять коэффициенты с помощью треугольника Паскаля

Треугольник Паскаля — это специальный треугольник чисел, который помогает считать биномиальные коэффициенты. Каждое число в нём равно сумме двух чисел, расположенных над ним. На вершине и по рёбрам треугольника расположены единицы.

Первые пять строк треугольника Паскаля выглядят так:

Фишка этого треугольника в том, что нам не нужно много раз считать факториалы, чтобы найти биномиальные коэффициенты. Всё, что необходимо, — это сложить несколько чисел.

Давайте для примера вычислим коэффициенты для суммы чисел, возведённой в пятую степень:

Теперь подставим их в наше выражение — то есть возведём сумму (a + b) в пятую степень. Для этого используем формулу бинома Ньютона:

Раскладываем на слагаемые, но пока не считаем коэффициенты:

Заменяем по очереди биномиальные коэффициенты на числа из треугольника Паскаля:

Получаем нужную формулу. Можете проверить и пересчитать коэффициенты классическим способом — с помощью факториалов.

Где используют бином Ньютона

Стоит ли говорить, что чаще всего бином Ньютона используют в математике — вот в каких её разделах он незаменим:

  • Теория вероятностей — чтобы вычислять вероятности нескольких независимых событий. Например, вероятности выпадения решки при подбрасывании монеты пять раз подряд.
  • Комбинаторика — чтобы вычислять количество возможных комбинаций и перестановок для объектов.
  • Статистика — чтобы оценивать вероятность успеха или неудачи в случайных экспериментах. Например, мы можем заранее просчитать, какое количество товаров на фабрике будет бракованным.

Но одной математикой всё не ограничивается — вот несколько сфер науки и техники, где бином Ньютона тоже активно используется:

  • Физика и механика — для вычисления вероятностей результатов экспериментов с частицами и для описания поведения частиц при столкновениях.
  • Инженерные науки — для оценки вероятности отказа компонентов в системе.
  • Программирование — для создания алгоритмов сжатия данных, криптографии и решения задач, связанных с комбинаторикой и вероятностями.
  • Биология и генетика — для анализа частоты определённых генотипов или фенотипов в популяциях. А ещё бином Ньютона незаменим при моделировании результатов генетических кроссов и передачи наследственных характеристик.

В общем виде принцип такой: бином Ньютона используют везде, где нужно просчитывать вероятности и комбинации различных предметов и событий.

Что дальше

Будем продолжать разбираться с математическими понятиями, которые используют в комбинаторных алгоритмах и программировании. Ранее мы уже успели познакомиться с факториалами — сейчас на подходе большая статья про теорию вероятностей. В общем, оставайтесь на связи 🙂

Читайте также:

  • Стыдные вопросы о логарифмах: всё, что нужно знать программисту
  • Задача про бракованные аймаки
  • Как изучить Python самостоятельно и бесплатно: алгоритм

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *