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

05.02.202403.07.2023 admin 0 Comments

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

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

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

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

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

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

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

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

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

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

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

2.8*10 19 уже не влезает в unsigned long long

Дальнейшее повышение точности и расчет при n>67

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

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

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

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

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

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

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

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

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

Источник

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

Определение свойств чисел и выражение соотношений между подмножествами одного множества. Арифметический треугольник Паскаля. Алгоритм вычисления биномиальных коэффициентов. Рассмотрение комбинаторных тождеств: правила симметрии и свертки Вандермонда.

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

2.3 Алгоритм вычисления биномиальных коэффициентов

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

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

Целью моей работы является проектирование содержания темы «Биномиальные коэффициенты» как элемента стохастической линии в курсе школьной математики.

Задачи при достижении этой цели ставятся следующие:

— разработать содержание темы «Сочетания и число сочетаний»;

Её можно записать после очевидных сокращений следующим образом:

Числа C_n k обладают рядом замечательных свойств. Эти свойства в конечном счёте выражают различные соотношения между подмножествами данного множества X. Их можно доказывать непосредственно, исходя из формулы (1), но более содержательными являются доказательства, опирающиеся на теоретико-множественные рассуждения.

1. Справедлива формула

2. Справедлива формула

Это равенство нетрудно получить с помощью формулы (1). В самом деле,

4. Арифметический треугольник Паскаля.

IV. Решите уравнение:

x = 4; C₈ 4 = 8•7•6•5 = 2•7•5 = 70.

Искомое значение x = 4.

Ответ: а) 8; b) 6; c) 7 d) 4.

Из школьного курса читателю известны формулы:

Обобщением этих формул является следующая формула, называемая обычно формулой бинома Ньютона:

В этой формуле может быть любым натуральным числом.

Вывод формулы (6) несложен. Прежде всего запишем:

где число перемножаемых скобок равно n. Из обычного правила умножения суммы на сумму вытекает, что выражение (7) равно сумме всевозможных произведений, которые можно составить следующим образом: любое слагаемое первой из сумм а + b умножается на любое слагаемое второй суммы a +b, на любое слагаемое третьей суммы и т.д. Hапример, при n = 3 имеем:

(a +b)(a + b)(a + b) = aaa + aab + aba + abb + baa + bab + bba + bbb.

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

Из формулы (6) можно получить целый ряд свойств этих коэффициентов. Например, полагая а =1, b = 1, получим:

С другой стороны, она равна

При x = 0 получим равенство

При всех k = 1, 2, …, n.

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

Разумеется, можно вычислить все биномиальные коэффициенты для любого n путём непосредственного перемножения n множителей (a + b), раскрытия скобок и приведения подобных членов. Правда, математикам древности и среднековья сделать это мешало отсутствие алгебраической символики. Например, в одном средневековом математическом тексте, имевшем хождение в Западной Европе в XV в. и, по-видимому, восходящем к арабам, биномиальные коэффициенты вычисляются очень наглядно путём возведения в степени числа 10001 и приводятся в виде таблицы.

Таблица 1. степень числа 1001 воспроизводит биномиальные коэффициенты.

Ат-Тутси (XIII в.) располагал таблицей биномиальных коэффициентов до n = 2 и, что важнее, привёл общее правило для их получения, которое в современных обозначениях может быть выражено так:

Таблица 2. Биномиальные коэффициенты.

Таблица 3. Треугольник Паскаля.

Вот ещё несколько свойств таблицы 3, доказанных Паскалем:

Треугольные и пирамидальные числа

Если обратиться к форме треугольник Паскаля, представленный в таблице 2, и рассмотреть её столбцы и нисходящие диагонали, то это рассмотрение ничего не даст: фактически, столбцы у таблиц 2 и 3 одни и те же, а нисходящие диагонали таблицы 2 совпадают со строками таблицы 3. Строки же таблицы 2 совпадают с восходящими диагоналями таблицы 3. Последовательность (1, 1, 2, 3, 5, 8, …), полученная при разборе восходящих диагоналей: 1; 1; 1+1 = 2; 1+2 = 3; 1+3 = 5, 1+3+1 = 5; 1+4+3 = 8 и т.д., обладает тем свойством, что каждое число в ней равно сумме двух предыдущих. Эти числа носят название чисел Фибоначчи и обладают многими интересными математическими свойствами, возникая в самых неожиданных задачах.

Гораздо проще вопрос о том, чему равны суммы чисел, стоящих на каждой из строк таблицы 2 ( и ли на каждой из восходящих диагоналей таблицы 3).

Приведём одно из свойств, связанных с делимостью биномиальных коэффициентов. Рассмотрим таблицу 2. Легко видеть, что все числа её 5-й строки, кроме крайних единиц, делятся на 5; все числа 7-й строки, кроме крайних единиц, делятся на 7. Очевидно, у 2-й и 3-й строки есть такое же свойство. А у остальных, легко видеть, такого свойства нет. Что объединяет числа 2, 3, 5 и 7 и отличает их от других чисел первого десятка? Верно, все они простые. Можно доказать, что, действительно, все числа n-ой строки треугольника Паскаля (в форме таблицы 2), кроме крайних единиц, делятся на n тогда и только тогда, когда n простое.

И наконец приведём сравнительно недавно, в общем, то, случайно обнаруженное свойство треугольника Паскаля, связывающее его с простыми числами (Г.В. Манн, Д. Шенкс, 1972г.). запишем строки треугольника Паскаля (в форме таблицы 2), каждый раз сдвигая строки в право на две позиции.

Таблица 4. Связь ряда простых чисел и треугольника Паскаля.

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

2.3 Алгоритмы вычисления биномиальных коэффициентов

c) Используя равенство (а + b) 4 = (a + b) 3 ·(a + b), выведите формулу сокращённого умножения для суммы двух чисел в четвёртой степени.

Решённые примеры являются частными случаями бинома Ньютона.

b) При каком значении числа k получится наибольшее значение числа C k ₅?

c) Найдите сумму чисел во второй строке составленной таблицы.

d) Отметьтье на координатной плоскости точки (k, C k ₅).

а) Вторая строка в таблице будет пятой строкой в треугольнике Паскаля:

Источник

Лекция на тему «Бином Ньютона. Биномиальные коэффициенты и треугольник Паскаля»

Раздел 1. Комбинаторика.

Тема: Бином Ньютона. Биномиальные коэффициенты и треугольник Паскаля.

дать понятие «Бином Ньютона»;

вывести формулу бинома Ньютона, рассмотреть свойства его разложения;

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

Прикладная комбинаторная математика

Энциклопедический словарь юного математика/Сост. А.П. Савин. – М.: Педагогика, 1985г.

Формулу для квадрата двучлена

знали, еще математики Древнего Вавилона, а древнегреческие математики знали ее геометрическое истолкование .

Если умножить обе части этой формулы на ( а + b ) и раскрыть скобки, то получим:

Аналогичный шаг может привести к следующей формуле:

Легко заметить закон образования коэффициентов: коэффициент 4 при a 3 b есть сумма коэффициентов 3 и 1 при a 2 b и а 3 . Аналогично, коэффициент 6 при a 2 b 2 является суммой (3 + 3) коэффициентов при ab 2 и a 2 b . По тому же закону получаем и коэффициент 4 при ab 3 .

Отсюда следует, что коэффициенты С k _n в равенстве:

являются членами ( n +1)-й строки треугольника Паскаля .

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

Первое дошедшее до нас описание формулы бинома Ньютона содержится в появившейся в 1265 г. книге среднеазиатского математика ат-Туси, где дана таблица чисел С k _n ( биномиальных коэффициентов ) до п = 12 включительно.

Европейские ученые познакомились с формулой бинома Ньютона, по-видимому, через восточных математиков. Детальное изучение свойств биномиальных коэффициентов провел французский математик и философ Блез Паскаль в 1654 г. Еще до этого было известно, что числа

являются в то же время числами «сочетаний без повторений» из n элементов по k .

В 1664-1665 гг. И. Ньютон установил, что формула (1) обобщается на случай произвольных (дробных и отрицательных) показателей, но при этом получается сумма из бесконечного множества слагаемых. Именно он показал, что при | х |

(2)

При п = — 1 формула (2) превращается в известную формулу для суммы бесконечной геометрической прогрессии:

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

По этому правилу легко выписывать одну за другой новые строки этого треугольника. Именно в такой форме он приведен в «Трактате об арифметическом треугольнике» французского математика Б. Паскаля (1623-1662), опубликованном в 1665 г., уже после смерти автора.

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

Сколько различных k -элементных множеств (сочетаний) можно образовать из данных п элементов?

Каковы коэффициенты многочлена (1 +х) n ?

Сколько существует строчек из п единиц и нулей, в которых ровно k единиц?

Сколькими разными путями можно спуститься из верхней точки А на рис 2. в k -й перекресток n -го ряда?

На все эти вопросы ответ дают числа С k _n , треугольника Паскаля. Обозначение С k _n предполагает, что верхняя строка треугольника Паскаля состоит из одного числа С 0 ₀ = 1, следующая (первая)-из двух чисел С 0 ₁ = С 1 ₁ =1, и вообще п-я строка состоит из п+1 чисел:

В «равнобедренной» форме треугольника Паскаля на рис. 1 очевидно свойство симметрии каждой строки С k _n = С n — k _n ; при этом посередине строки стоит самое большое число (если п четно) или два самых больших числа (если п нечетно), а к краям числа монотонно убывают.

Если записать тот же треугольник в «прямоугольной» форме (рис.3), то целый ряд свойств треугольника Паскаля, связанный с суммами его чисел, будет удобнее наблюдать. В частности, сумма нескольких первых чисел каждого столбца равна идущему за ними числу следующего столбца:

Суммы чисел по «восходящим» (зеленым) диагоналям на рисунке 3 равны последовательным числам Фибоначчи.

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

Источник

Бином Ньютона — математическая формула с примером решения и объяснением

Рассматривая эти произведения, замечаем, что все они составлены по одному и тому же закону, а именно:

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

Показатель первого члена равен числу перемножаемых биномов; показатели при х в следующих членах убывают на 1; последний член не содержит х (содержит его в нулевой степени).

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

Итак, допустим, что верно следующее равенство:
(x+α) (x+b) (х+с)… (x+k) =
где для краткости мы положим:

Умножим обе части допущенного равенства на бином x+l:

Рассматривая это новое произведение, убеждаемся, что оно подчиняется такому же закону, какой мы предположили верным для m биномов. Действительно, во-первых, этому закону следуют показатели буквы х; во-вторых, ему же следуют и коэффициенты, так как коэффициент второго члена S+l есть сумма всех вторых членов перемножаемых биномов, включая сюда и l; коэффициент третьего члена S₂+lS₁ есть сумма парных произведений всех вторых членов, включая сюда и l, и т. д.; наконец, есть произведение всех вторых членов: abc… kl.

Мы видели, что закон этот верен для произведения двух, трёх и четырёх биномов; следовательно, по доказанному теперь, он должен быть верен и для произведения 4+1, т. е. для произведения пяти биномов, если же он верен для произведения пяти биномов, то он верен и для произведения 5+1, т. е. для произведения шести биномов, и т. д.

Формула бинома Ньютона

Предположим, что в доказанном нами равенстве

все вторые члены биномов одинаковы, т. е. что a=b=c= … =k. Тогда левая часть будет степень бинома . Посмотрим, во что обратятся коэффициенты S₁, S₂, …, .

Коэффициент S₁, равный a+b+c+ … +k, обратится в та. Коэффициент S₂, равный ab+ac+ad+ …. обратится в число α², повторённое столько раз, сколько можно составить сочетаний из m элементов по 2, т. е. обратится в . Коэффициент S₃, равный abc+abd+…, обратится в число а³, повторённое столько раз, сколько можно составить сочетаний из т элементов по 3, т. е. и т. д. Наконец, коэффициент , равный abc...k, обратится в . Таким образом, мы получим:

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

Свойства формулы бинома Ньютона

Из этих свойств мы укажем следующие 10:

1) Показатели буквы х уменьшаются на 1 от первого члена к последнему, причём в первом члене показатель х равен показателю степени бинома, а в последнем он есть 0; наоборот, показатели буквы а увеличиваются на 1 от первого члена к последнему, причём в первом члене показатель при а есть 0; а в последнем он равен показателю степени бинома. Вследствие этого сумма показателей при х и а в каждом члене одна и та же, а именно: она равна показателю степени бинома.

2) Число всех членов разложения есть m+1, так как разложение содержит все степени а от 0 до m включительно.

3) Коэффициенты равны: у первого члена — единице, у второго члена — показателю степени бинома, у третьего члена — числу сочетаний из m элементов по 2, у четвёртого члена — числу сочетаний из m элементов по 3; вообще коэффициент (n+1)-ro члена есть число сочетаний из m элементов по n. Наконец, коэффициент последнего члена равен числу сочетаний из т элементов по m, т. е. 1.

Заметим, что эти коэффициенты называются биномиальными.

4) Обозначая каждый член разложения буквой T с цифрой внизу, указывающей номер места этого члена в разложении, т. е. первый член T₁, второй член T₂ и т. д., мы можем написать:

Эта формула выражает общий член разложения, так как из неё мы можем получить все члены (кроме первого), подставляя на место n числа: 1, 2, 3,…. m.

5) Коэффициент первого члена от начала разложения равен единице, коэффициент первого члена от конца тоже равен единице. Коэффициент второго члена от начала есть m, т. е. ; коэффициент второго члена от конца есть ; но так как , то эти коэффициенты одинаковы. Коэффициент третьего члена от начала есть , а третьего члена от конца есть ; но , поэтому и эти коэффициенты одинаковы и т. д. Значит:

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

6) Рассматривая биномиальные коэффициенты:

мы замечаем, что при переходе от одного коэффициента к следующему числители умножаются на числа, всё меньшие и меньшие (на m—1, на m — 2, на m — 3 и т. д.), а знаменатели умножаются на числа, всё большие и большие (на 2, на 3, на 4 и т. д.). Вследствие этого коэффициенты сначала возрастают (пока множители в числителе остаются большими соответственных множителей в знаменателе), а затем убывают. Так как коэффициенты членов, равно отстоящих от концов разложения, одинаковы, то наибольший коэффициент должен находиться посередине разложения. При этом, если число всех членов разложения нечётное (что бывает при чётном показателе бинома), то посередине будет один член с наибольшим коэффициентом; если же число всех членов чётное (что бывает при нечётном показателе бинома), то посередине должны быть два члена с одинаковыми наибольшими коэффициентами. Например:
(х+α)⁴=x⁴+4αx³+6α²x²+4α³x+α⁴;
(x+α)⁵=x⁵+5αx⁴+10α²x3+10α³x²+5α⁴x+α⁵∙

7) Из сравнения двух рядом стоящих членов:

заключаем, что:

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

Пользуясь этим свойством, можно сразу писать, например, (x+a)⁷=x⁷+7ax⁶+…

Теперь уже выписаны члены до середины ряда, остальные получим, основываясь на свойстве пятом:
(х+а)⁷ =х⁷-7αx⁶+21α²x⁵+35α³x⁴+35α⁴x³+21α⁵x²+7α⁶x+α⁷.

8) Сумма всех биномиальных коэффициентов равна . Действительно, положив в формуле бинома x=a=1, получим:

Например, сумма коэффициентов в разложении (х+a)⁷ равна
1+7+21+35+35 +21+7+1 = 128=2⁷.

9) Заменив в формуле бинома а на — а, получим:

т. е.

следовательно, знаки + и — чередуются.

10) Если в последнем равенстве положим x=α =1, то найдём:

Сумма биномиальных коэффициентов, стоящих на нечётных местах, равна сумме биномиальных коэффициентов, стоящих на чётных местах.

Применение формулы бинома к многочлену

Формула бинома Ньютона позволяет возвышать в степень многочлен. Так:
(α+ b+c)⁴ = [(а+b)+с]⁴= (a+b)⁴+4c (а+b)³+6c² (а+b)²+4c³ (a+b)+c⁴.

Вывод формулы бинома ньютона

Возникает вопрос, будет ли закономерность, наблюдаемая в этих формулах, обладать общностью, т. е. будет ли справедливой формула

при всяком натуральном значении n?

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

Умножим обе части этого предполагаемого равенства на

и приняв во внимание, что

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

Теперь легко получить разложение и для

Последняя формула и называется формулой бинома Ньютона. Ее правая часть называется разложением степени бинома.

Числа называются биномиальными коэффициентами.

Свойства разложения бинома

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

Все члены разложения имеют относительно букв а и b одно и то же измерение, равное показателю степени бинома. (Измерением одночлена относительно букв а и b называется сумма показателей степеней этих букв, входящих в этот одночлен.)

Поскольку все члены разложения имеют одинаковое измерение относительно букв а и b, то это разложение является однородным многочленом относительно букв а и b (см. стр. 450).

В разложении показатель степени буквы а последовательно понижается на единицу, начиная с показателя n, а показатель степени буквы b последовательно повышается на единицу, начиная с показателя, равного нулю.

Член разложения является членом разложения и обозначается символом

называется формулой общего члена разложения, так как, давая букве k целые значения от 0 до n, мы можем получить из нее любой член разложения.

Теперь напишем разложение для выражения

Свойства биномиальных коэффициентов

1. Биномиальные коэффициенты, равноудаленные от начала и конца разложения, равны между собой. Действительно, по первому свойству числа сочетаний имеем:

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

Доказательство:

Положим, в формуле бинома

3. Сумма биномиальных коэффициентов, стоящих на четных местах, равна сумме, биномиальных коэффициентов, стоящих на нечетных местах.

Доказательство:

Полагая в тождестве

Перенеся все отрицательные члены в левую часть, получим:

что и требовалось доказать.

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

Формулу бинома Ньютона принято записывать ради краткости в следующем символическом виде:

Читателю может показаться непонятным, почему столь элементарная формула

где n — целое положительное число, носит имя великого ученого Ньютона, тем более что эта формула была известна до Ньютона. Например, ее знал Аль-Каши (XV век) и она встречается в трудах Паскаля. Объясняется это тем, что именно Ньютоном была обобщена эта формула для любого действительного показателя.

Ньютон впервые показал, что выражение

где и — любое действительное число, равняется сумме следующего сходящегося, ряда:

Например, если то

Арифметический треугольник, или треугольник паскаля

Написанная ниже таблица

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

По боковым сторонам этой таблицы стоят единицы, внутри же стоят числа, получающиеся сложением двух соответствующих чисел предыдущей строки. Например, число 21 в 8-й строке получается сложением стоящих над ним чисел 6 и 15.

строка этой таблицы дает биномиальные коэффициенты разложения n-й степени бинома. Например:

Треугольник Паскаля получается из следующей таблицы:

Треугольник Паскаля приведен в книге Паскаля «Трактат об арифметическом треугольнике», изданной после его смерти в 1665 году.

Примеры с решением на Бином Ньютона

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