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

Используем мощь комбинаторики для изучения самой математики: упростим умножение многочленов и выведем известную и очень полезную формулу!
Продвинутый уровень
Продвинутый уровень
Материал в этой теме предназначен для тех, кто полностью разобрался с базой и хочет «копнуть глубже».
Зависимости
Зависимости
Царского пути в эту тему нет! Вы сможете разобраться только если знаете следующие темы:
Добавить плашку "Продвинутая тема!"
Добавить, что пройти тему можно только освоив правило умножения, сочетания и факториал!

Умножение многочленов

Давайте умножим друг на друга два многочлена! Что может быть проще?!

(a+b)(c+d+e)= ?(a + b)(c + d + e) = \ ?

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

(a+b)(c+d+e)=ac+ad+ae+bc+bd+be(a+b)(c+d+e) = ac + ad + ae + bc + bd + be

Обратите внимание, что в правой части равенства находятся пары букв. Каждая такая пара букв это комбинация из двух элементов. Первый элемент это какая-то буква из первого многочлена (a или b), а второй — буква второго многочлена (c, d или e).

Развивая эту идею, вместо умножения этих многочленов друг на друга достаточно найти и сложить все возможные двух-буквенные комбинации из членов многочленов:

(a+b)(c+d+e)ac=acad=adae=aebc=bcbd=bdbe=be \def\arraystretch{1.25} \begin{array}{} (a+b) & (c+d+e) & \\ \hline a & c & = ac \\ a & d & = ad \\ a & e & = ae \\ \hline b & c & = bc \\ b & d & = bd \\ b & e & = be \end{array}
(a+b)(c+d+e)=ac+ad+ae+bc+bd+be(a+b)(c+d+e) = ac + ad + ae + bc + bd + be

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

Комбинаторное умножение

Умножьте друг на друга многочлены «комбинаторным» способом:

(n+m)(j+k)(l+e)= ?(n + m)(j + k)(l + e) = \ ?
Решение

Три многочлена, значит нам надо составить все возможные комбинации из 3-х элементов, причем на каждое «вакантное место» в комбинации претендуют по 2 буквы. По правилу умножения у нас должно получиться 222=82 \cdot 2 \cdot 2 = 8 комбинаций.

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

(n+m)(j+k)(l+e)njl=njlnje=njenkl=nklnke=nkemjl=mjlmje=mjemkl=mklmke=mke \def\arraystretch{1.25} \begin{array}{} (n + m) & (j + k) & (l + e) \\ \hline n & j & l & = njl \\ n & j & e & = nje \\ \hdashline n & k & l & = nkl \\ n & k & e & = nke \\ \hline m & j & l & = mjl \\ m & j & e & = mje \\ \hdashline m & k & l & = mkl \\ m & k & e & = mke \end{array}

Прямым перебором нашли все предсказанные 8 комбинаций. Теперь складываем их все вместе и получаем ответ!

(n+m)(j+k)(l+e)==njl+nje+nkl+nke+mjl+mje+mkl+mke(n + m)(j + k)(l + e) = \\ = njl + nje + nkl + nke + mjl + mje + mkl + mke

Способ хорош, но чем больше многочленов — тем больше комбинаций перебирать и тем проще запутаться. Умножать четыре или более многочленов это вообще ад. К счастью, в некоторых ситуациях вручную проводить умножение вовсе не обязательно!

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

Хитрым математикам было лень умножать многочлены «напрямую», поэтому они вывели очень знаменитую и полезную в базовой и особенно в высшей математике формулу:

Бином Ньютона — формула, позволяющая напрямую получать результат возведения любого двучлена в любую натуральную степень:

(a+b)n=Cn0an0b0+Cn1an1b1+Cn2an2b2++Cnnannbn(a+b)^n = C_n^0 a^{n-0}b^0 + C_n^1 a^{n-1}b^1 + C_n^2 a^{n-2}b^2 + \ldots + C_n^n a^{n-n}b^n

В компактном виде:

(a+b)n=k=0nCnkankbk(a+b)^n = \sum\limits_{k=0}^n C_n^k a^{n-k}b^k

В формулах выше записи вида CnkC_n^k это количества сочетаний из n по k.

Примеры построения слагаемых

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

(a+b)n=(a+b)(a+b)(a+b)(a+b)^n = (a+b) (a+b) (a+b) \ldots

Мы уже знаем, как легко работать с произведением многочленов. Каждая из скобок «превращается» либо в a, либо в b, тем самым образуя n-буквенную комбинацию. Потом все возможные комбинации складываются:

aaaaa+babab+bbaab+aaaaa\ldots + babab \ldots + bbaab\ldots + \ldots

Каждая такая комбинация является слагаемым в большой сумме, поэтому далее мы так и будем их называть.

Например, если каждая скобка превратится в a, то мы получим слагаемое ana^n:

(a+b)(a+b)(a+b)aaa=an \def\arraystretch{1.5} \begin{array}{} (a+b) & (a+b) & (a+b) & \ldots & \\ \hline a & a & a & \ldots & = a^n \end{array}

Если в a превратить только одну скобку, а остальные (n1)(n-1) скобок в b, то получим слагаемое вида abn1ab^{n-1}. Причем таких слагаемых будет аж n штук, потому что в a можно превратить любую из n скобок (первую, вторую, n-ую):

(a+b)(a+b)(a+b)abb=abn1bab=abn1bba=abn1 \def\arraystretch{1.5} \begin{array}{} (a+b) & (a+b) & (a+b) & \ldots & \\ \hline a & b & b & \ldots & = ab^{n-1} \\ \hline b & a & b & \ldots & = ab^{n-1} \\ \hline b & b & a & \ldots & = ab^{n-1} \\ \hline \vdots \end{array}

Складываем вместе эти n одинаковых слагаемых и получаем nabn1n \cdot ab^{n-1}.

Вывод формулы

Превратим ровно k скобок в b. Остальные nkn-k скобок автоматически превращаются в a. Тогда слагаемое будет иметь вид ankbka^{n-k}b^k.

Слагаемых такого вида будет столько, сколькими способами можно выбрать k скобок для превращения в b. Порядок, в котором выбраются скобки значения не имеет, поэтому каждый выбор скобок это сочетание из n всех скобок по k скобкам для превращения. Всего CnkC_n^k способов эти скобки выбрать.

Итак, превратив k скобок в b мы получаем CnkC_n^k одинаковых слагаемых вида ankbka^{n-k}b^k. Складываем их вместе и получаем общий вид слагаемого в разложении бинома Ньютона:

Cnkankbk\boxed{C_n^k a^{n-k}b^k}

Переменная k по очереди принимает все значения от 0 (ни одна скобка не станет b) до n (все скобки стали b). И каждое новое значение k порождает очередное слагаемое в разложении бинома Ньютона:

(a+b)n=Cn0an0b0+Cn1an1b1++Cnnannbn(a+b)^n = C_n^0 a^{n-0}b^0 + C_n^1 a^{n-1}b^1 + \ldots + C_n^n a^{n-n}b^n

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

(a+b)n=k=0nCnkankbk(a+b)^n = \sum\limits_{k=0}^n C_n^k a^{n-k}b^k

\blacksquare

В русскоязычной среде устоялось название «бином Ньютона».
В англоязычной среде формулу называют «биномиальной теоремой».

Что еще за «биномы»?! Дело в том, что многочлены по-умному называются полиномами, а двучлены — биномами («би» — 2). Отсюда и названия: «бином», «биномиальная».

Бином Ньютона выглядит страшно замороченно, но стоит познакомиться с ним поближе, попрактиковаться в его применении, и он станет незаменимым и очень полезным инструментом в арсенале любителя математики!

«Тоже мне бином Ньютона!»

Ироническое восклицание о простой задаче, которую кто-либо не может решить, думая, что она сложная. Восклицание распространилось благодаря роману Михаила Булгакова «Мастер и Маргарита»:

«— Ну да, неизвестно, — послышался все тот же дрянной голос из кабинета, — подумаешь, бином Ньютона! ...»

Так зачем же нужна эта формула? А затем, что она избавляет нас от необходимости долго и нудно вручную умножать друг на друга двучлены! Проверим ее в деле!

Формулы сокращенного умножения

С помощью формулы бинома Ньютона найдите, чему равны следующие степени биномов:

(a+b)0(a+b)1(a+b)2(a+b)3(a+b)4(a+b)^0 \quad (a+b)^1 \quad (a+b)^2 \quad (a+b)^3 \quad (a+b)^4
Решение
(a+b)0=C00a0b0=C00=1(a+b)1=C10a1+C11b1=a+b(a+b)2=C20a2+C21ab+C22b2=a2+2ab+b2(a+b)3=C30a3+C31a2b+C32ab2+C33b3==a3+3a2b+3ab2+b3 (a+b)^0 = C_0^0 a^{0}b^{0} = C_0^0 = \boxed{1} \\ (a+b)^1 = C_1^0 a^1 + C_1^1 b^1 = \boxed{a + b} \\ (a+b)^2 = C_2^0 a^2 + C_2^1 ab + C_2^2 b^2 = \boxed{a^2 + 2ab + b^2} \\ (a+b)^3 = C_3^0 a^3 + C_3^1 a^2b + C_3^2 ab^2 + C_3^3 b^3 = \\ = \boxed{a^3 + 3a^2b + 3ab^2 + b^3}

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

(a+b)4=C40a4+C41a3b+C42a2b2+C43ab3+C44b4==a4+4a3b+6a2b2+4ab3+b4(a+b)^4 = C_4^0a^4 + C_4^1a^3b + C_4^2a^2b^2 + C_4^3ab^3 + C_4^4b^4 = \\ = \boxed{a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4}

Длинную цепочку из слагаемых после применения формулы бинома Ньютона называют разложением степени бинома:

(a+b)2Степень бинома=  a2+2ab+b2Разложение\underbrace{(a+b)^2}_{\text{Степень бинома}} = \ \ \underbrace{a^2 + 2ab + b^2}_{\text{Разложение}}
Пример разложения

Чему будет равен двучлен x2yx^2 - y, если его возвести в шестую степень?

(x2y)6= ?(x^2 - y)^6 = \ ?
Решение

Будем считать, что x2x^2 выполняет роль a, а y-y роль b:

a=x2b=ya = x^2 \qquad b = -y

Применяем формулу бинома Ньютона:

(x2y)6==C60(x2)6+C61(x2)5(y)+C62(x2)4(y)2+C63(x2)3(y)3+C64(x2)2(y)4+C65(x2)(y)5+C66(y)6 (x^2 - y)^6 = \\ = C_6^0 (x^2)^6 + C_6^1 (x^2)^5(-y) + C_6^2 (x^2)^4(-y)^2 + C_6^3 (x^2)^3(-y)^3 + C_6^4 (x^2)^2(-y)^4 + C_6^5 (x^2)(-y)^5 + C_6^6(-y)^6

Аккуратно считаем сочетания, работаем со степенями, не путаемся в знаках и получаем финальный вид разложения:

(x2y)6==x126x10y+15x8y220x6y3+15x4y46x2y5+y6(x^2 - y)^6 = \\ = x^{12} - 6 x^{10}y + 15x^8y^2 - 20x^6y^3 + 15x^4y^4 - 6x^2y^5 + y^6

Иногда бывает полезно точечно изучить конкретное слагаемое, полученное после применения формулы бинома Ньютона, без необходимости выписывать все разложение целиком. Такие слагаемые обозначают TkT_k, где k — номер слагаемого в разложении:

(a+b)n=Cn0anT0+Cn1an1bT1++CnnbnTn=k=0nCnkankbkTk(a+b)^n = \underbrace{C_n^0 a^n}_{\small T_0} + \underbrace{C_n^1 a^{n-1}b}_{\small T_1} + \ldots + \underbrace{C_n^n b^n}_{\small T_n} = \sum\limits_{k=0}^n \underbrace{C_n^k a^{n-k} b^k}_{\small T_k}
Формула члена разложения

k-ый член в разложении по формуле бинома Ньютона имеет следующий вид:

Tk=CnkankbkT_k = C_n^k a^{n-k}b^k
Найти и выписать!

Чему равен нулевой член разложения степени бинома (a+b)n(a+b)^n?
А 58-ой член разложения (2+m)100(2 + m)^{100}?

Решение

Для ответа на первый вопрос применяем формулу члена разложения при k=0k=0:

T0=Cn0an0b0=Cn0an=anT_0 = C_n^0 a^{n-0} b^0 = C_n^0 a^n = a^n

А во втором случае k=58k=58, а n=100n=100:

T58=C10058210058m58=C10058242m58T_{58} = C_{100}^{58} 2^{100 - 58} m^{58} = C_{100}^{58} 2^{42} m^{58}

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

Взглянем еще раз на формулу бинома Ньютона:

(a+b)n=Cn0an0b0+Cn1an1b1++Cnnannbn(a+b)^n = C_n^0 a^{n-0}b^0 + C_n^1 a^{n-1}b^1 + \ldots + C_n^n a^{n-n}b^n

Буквы a и b могут быть как фиксированными числами (постоянными), так и какими-то переменными, например если мы работаем с уравнением. Да и в целом, они меняются в зависимости от того, как мы используем бином:

(a+20)300(8+y)t(π+e)10(a + 20)^{300} \qquad (8 + y)^t \qquad (\pi + e)^{10}

Но как бы мы не использовали бином, что бы не ставили вместо a и b, в его разложении всегда будут присутствовать сочетания:

Cn0, Cn1, Cn2, , CnnC_n^0, \ C_n^1 , \ C_n^2, \ \ldots, \ C_n^n

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

Биномиальный коэффициент — числовой коэффициент перед каждым членом разложения бинома Ньютона.

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

Cnkили(nk)C_n^k \quad \text{или} \quad \binom{n}{k}

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

Одно и то же!

На сегодняшний день нет никакой разницы, какое обозначение использовать. Вас везде поймут вне зависимости от того, пишете ли вы (nk)\binom{n}{k} или CnkC_n^k в формуле бинома Ньютона или в каких-нибудь комбинаторных задачах. Это одно и то же!

Cnk=(nk)=n!(nk)! k!C_n^k = \binom{n}{k} = \frac{n!}{(n-k)! \ k!}

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

(a+b)n=(n0)an0b0+(n1)an1b1+(n2)an2b2++(nn)annbn(a+b)^n = \binom{n}{0} a^{n-0}b^0 + \binom{n}{1} a^{n-1}b^1 + \binom{n}{2} a^{n-2}b^2 + \ldots + \binom{n}{n} a^{n-n}b^n

В компактном виде:

(a+b)n=k=0n(nk)ankbk(a+b)^n = \sum\limits_{k=0}^n \binom{n}{k} a^{n-k}b^k

Повторение коэффициентов

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

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

Подобное поведение наблюдается и в разложениях других степеней биномов (знаки плюса и a, b для наглядности записывать не будем):

(a+b)01(a+b)111(a+b)2121(a+b)31331(a+b)414641 \def\arraystretch{1.2} \begin{array}{} \textcolor{gray}{(a+b)^0} \quad & 1 \\ \textcolor{gray}{(a+b)^1} \quad & 1 \quad 1 \\ \textcolor{gray}{(a+b)^2} \quad & 1 \quad 2 \quad 1 \\ \textcolor{gray}{(a+b)^3} \quad & 1 \quad 3 \quad 3 \quad 1 \\ \textcolor{gray}{(a+b)^4} \quad & 1 \quad 4 \quad 6 \quad 4 \quad 1 \end{array}

Обобщим это интересное поведение коэффициентов теоремой. Заодно разберемся, из-за чего это происходит:

Повторение биномиальных коэффициентов

В разложении бинома Ньютона k-ый биномиальный коэффициент CnkC_n^k равен k-му с конца, то есть CnnkC_n^{n-k}:

Cnk=CnnkC_n^k = C_n^{n-k}
Алгебраическое доказательство

Докажем равенство чисто алгебраически, используя формулу количества сочетаний:

Cnk=Cnnkn!(nk)! k!=n!(nn+k)! (nk)!n!(nk)! k!=n!k! (nk)! C_n^k = C_n^{n-k} \\ \frac{n!}{(n-k)! \ k!} = \frac{n!}{(n - n + k)! \ (n-k)!} \\ \frac{n!}{(n-k)! \ k!} = \frac{n!}{k! \ (n-k)!}

Выражения слева и справа одинаковые.

\blacksquare

Комбинаторное доказательство

Пускай у нас есть n одинаковых белых шаров. Мы хотим покрасить k из них в красный цвет. Выбрать из n шаров k шаров для покраски можно CnkC_n^k способами.

Но можно решить задачу и наоборот. После покраски останется nkn-k непокрашенных шаров. Тогда выбрать из n шаров nkn-k шаров, которые не будут покрашены можно CnnkC_n^{n-k} способами.

Количество способов выбрать шары для покраски ровно столько же, что и количество способов выбрать шары, которые останутся нетронутыми:

Cnk=CnnkC_n^k = C_n^{n-k}

\blacksquare

Доказательство через бином Нюьтона

От перемены мест слагаемых сумма не меняется, поэтому:

(a+b)n=(b+a)n(a+b)^n = (b+a)^n

Распишем левое выражение по формуле бинома Ньютона:

(a+b)n==Cn0an+Cn1an1b++Cnn1abn1+Cnnbn(a+b)^n = \\ = C_n^0 a^n + C_n^1 a^{n-1}b + \ldots + C_n^{n-1} ab^{n-1} + C_n^n b^n

Теперь распишем правое выражение тоже по формуле бинома Ньютона, но задом на перед:

(b+a)n==Cnnan+Cnn1ban1++Cn1bn1a+Cn0bn(b+a)^n = \\ = C_n^n a^n + C_n^{n-1}ba^{n-1} + \ldots + C_n^1 b^{n-1}a + C_n^0 b^n

Для наглядности запишем члены разложения обеих сумм друг под другом:

Cn0anCn1an1bCnn1abn1CnnbnCnnanCnn1an1bCn1abn1Cn0bn \def\arraystretch{1.3} \begin{array}{r|r|r|r|r} C_n^0 a^n & C_n^1 a^{n-1}b & \ldots & C_n^{n-1}ab^{n-1} & C_n^n b^n \\ C_n^n a^n & C_n^{n-1}a^{n-1}b & \ldots & C_n^1 ab^{n-1} & C_n^0 b^n \end{array}

Так как суммы равны, то обязаны быть равны и их слагаемые:

Cn0an=CnnanCn1an1b=Cnn1an1bC_n^0 a^n = C_n^n a^n \\ C_n^1 a^{n-1}b = C_n^{n-1}a^{n-1}b \\ \cdots

А слагаемые могут быть равны только если равны биномиальные коэффициенты:

Cn0=CnnCn1=Cnn1Cnk=CnnkC_n^0 = C_n^n \quad C_n^1 = C_n^{n-1} \quad \ldots \\ C_n^k = C_n^{n-k}

\blacksquare

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

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

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

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

Полученные числа и есть искомые биномиальные коэффиенты. В первой строчке треугольника это единственный коэффициент для (a+b)0(a+b)^0, во второй для (a+b)1(a+b)^1 и так далее..

Такой треугольник называют арифметическим или треугольником Паскаля.
Опробуем его в деле!

Ссылка на статью про треугольник Паскаля!
Треугольные вычисления

С помощью треугольника Паскаля найти разложение степени бинома (a+b)5(a+b)^5, а потом разложение (a+b)6(a+b)^6.

Решение

Ранее мы уже построили треугольник Паскаля для четвертой степени бинома. Добавляем к нему еще одну строчку. Числа в ней и будут биномиальными коэффициентами для разложения пятой степени бинома:

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

(a+b)5==1a5+5a4b+10a3b2+10a2b3+5ab4+1b5(a+b)^5 = \\ = \blue{1}a^5 + \blue{5}a^4b + \blue{10}a^3b^2 + \blue{10}a^2b^3 + \blue{5}ab^4 + \blue{1}b^5

Для шестой степени бинома берем последнюю строчку треугольника и дописываем под ней еще одну:

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

(a+b)6==1a6+6a5b+15a4b2+20a3b3+15a2b4+6ab5+1b6(a+b)^6 = \\ = \blue{1}a^6 + \blue{6}a^5b + \blue{15}a^4b^2 + \blue{20}a^3b^3 + \blue{15}a^2b^4 + \blue{6}ab^5 + \blue{1}b^6

Применение бинома Ньютона

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

Он выступает своего рода «мостиком» по которому можно переходить от длинных сумм к их короткой записи и наоборот. Поэтому его очень часто можно встретить в самых разных разделах математики: в теории множеств, логике, теории вероятностей и особенно в высшей математике.

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

Математическая знаменитость

Популярность Бинома Ньютона вышла за пределы математики.
Встречается он и в художественной литературе, где часто фигурирует как синоним чего-то очень сложного (нередко иронически).

В повести «Последнее дело Холмса» Шерлок Холмс рассказывает о профессоре Мориарти, в частности, следующее:

«…когда ему исполнился 21 год, он написал трактат о биноме Ньютона, завоевавший ему европейскую известность…»

Дать ссылки на указанные здесь применения!

Как пример «мостика» между суммами и точными формулами, с помощью бинома Ньютона можно найти общие формулы для решения очень красивой задачи о суммах степеней натуральных чисел (и не только чисел):

1+2+3++n= ?12+22+32++n2= ?1k+2k+3k++nk= ?1+2+3+\ldots + n = \ ? \\ 1^2 + 2^2 + 3^2 + \ldots + n^2 = \ ? \\ \cdots \\ 1^k + 2^k + 3^k + \ldots + n^k = \ ?
Дать ссылку на статью про сумму степеней!
Превью