Инструменты сайта


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

Бином

Задача. Для произвольных вещественных чисел $ a,b_{} $ и натурального $ n_{} $ выписать разложение выражения $ (a+b)^{n} $ по степеням $ a_{} $ и $ b_{} $.

Из школьного курса алгебры известны эти разложения для малых $ n_{} $: $$ \begin{array}{lccccccccc} (a+b)= & &&& a&+&b \, , \\ (a+b)^2= & & &a^2 &+&2ab &+&b^2 \, , \\ (a+b)^3= & &a^3 &+&3a^2b &+& 3ab^2 &+& b^3 \, , \\ (a+b)^4= &a^4 &+& 4a^3b &+&6a^2b^2 &+&4ab^3 &+& b^4 \, . \end{array} $$

Выражение $$ C_n^m = \frac{n!}{m!\, (n-m)!}= \frac{n(n-1)\times \dots \times (n-m+1)} {1\cdot 2 \times \dots \times m} $$ при $ m\in\{0,\dots,n\} $ и $ 0! = 1 $ называется биномиальным коэффициентом. В западной литературе принято обозначение $ {n \choose m} $.

П

Пример.

$$ C_n^0=C_n^n=1,\ C_n^{1}=C_n^{n-1}=n,\ C_n^2=C_n^{n-2}= \frac{n(n-1)}{2},\ C_{17}^5=\frac{17\cdot 16\cdot 15 \cdot 14 \cdot 13}{2\cdot 3 \cdot 4 \cdot 5} =6188 \ . $$

Т

Теорема 1. Для любых натуральных $ n_{} $ и $ m_{} $ справедливы следующие формулы: $$ {\mathbf a})\ C_n^m=C_n^{n-m} \ , \quad {\mathbf b})\ C_n^m + C_n^{m+1}=C_{n+1}^{m+1} \ . $$

Т

Теорема 2. Имеет место формула бинома Ньютона

$$ (a+b)^n=\sum_{m=0}^n C_n^m a^{n-m}b^m = $$ $$=C_n^0a^{n}+C_n^1a^{n-1}b+C_n^2a^{n-2}b^2+\dots+ C_n^m a^{n-m}b^m+\dots+C_n^nb^{n} . $$

Доказательство ведется индукцией по $ n_{} $. Для $ n=1,2_{} $ формула справедлива. Предположим, что она справедлива для степени $ n_{} $, докажем ее справедивость для степени $ n_{}+1 $, т.е. докажем, что в разложении $ (a+b)^{n+1} $ по степеням $ a_{} $ и $ b_{} $ коэффициент при $ a^{n-m}b^{m+1} $ равен $ C_{n+1}^{m+1} $. $$(a+b)^{n+1}=(a+b)^{n}(a+b)=$$ $$ \begin{array}{rrrrrrrr} =&a^{n+1}+&C_n^1a^{n}b+&C_n^2a^{n-1}b^2+&\dots+ &C_n^m a^{n-m+1}b^m+&C_n^{m+1} a^{n-m}b^{m+1}+&\dots + \\ &+&a^{n}b+&C_n^1a^{n-1}b^2+&\dots &+ &C_n^{m} a^{n-m}b^{m+1}+&\dots =\\ =&a^{n+1}+&C_{n+1}^1a^{n}b+ &C_{n+1}^2a^{n-1}b^2+&\dots &+&C_{n+1}^{m+1} a^{n-m}b^{m+1}+&\dots \end{array} $$ Последнее равенство следует из пункта $ {\mathbf b}) $ теоремы 1.

Для малых значений показателя $ n_{} $ вычисления биномиальных коэффициентов удобно производить по следующей схеме.


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

$$ \begin{array}{l|cccccccccccccccc} &&&&&&&&1 \\ n=1&&&&&&& 1 && 1 \\ n=2&&&&&& 1 && 2 && 1 \\ n=3&&&&&1 && 3 && 3 && 1 \\ n=4&&&&1 && 4 && 6 && 4 && 1 \\ n=5&&&1 && 5 && 10 && 10 && 5 && 1 \\ n=6&&1 && 6 && 15 && 20 && 15 && 6 && 1 \\ n=7&1 && 7 && 21 && 35 && 35 && 21 && 7 && 1 \\ \dots& \dots && && && \dots && && && \end{array} $$ Правила формирования его просты: на сторонах треугольника ставится $ 1_{} $, а элемент каждой строки получается суммированием двух стоящих над ним в предыдущей строке. Обоснование этой схемы, очевидно, следует из формул теоремы 1.

Обобщение

Т

Теорема. Выражение $ (a_1+a_2+\dots+a_K)^n $ при $ K\ge 3 $ раскладывается по степеням чисел $ a_1,a_2,\dots,a_K $ с помощью обобщения биномиальных коэффициентов — так называемых мультиномиальных коэффициентов1):

$$(a_1+a_2+\dots+a_K)^n=\sum_{n_{_1}+n_{_2}+\dots+n_{_K}=n}\frac{n!}{n_1!\, n_2! \times \dots \times n_K!} a_1^{n_1}a_2^{n_2}\times \dots \times a_K^{n_K} \ ,$$ где суммирование идет по всем различным наборам $ (n_{1},n_2,\dots,n_K) $ неотрицательных целых индексов, удовлетворяющих ограничению $$n_1+n_2+\dots+n_K=n \ .$$

Доказательство приведем для случая $ K=3 $. Выражение $ (a_1+a_2+a_3)^n $ можно представить в виде бинома $$ (a_1+a_2+a_3)^n=\left( (a_1+a_2)+a_3 \right)^n= $$ $$ C_n^0 (a_1+a_2)^n+ C_n^1 (a_1+a_2)^{n-1}a_3+\dots+ C_n^{n_{_3}} (a_1+a_2)^{n-n_3}a_3^{n_3}+\dots+C_n^na_3^n \ . $$ Все возможные слагаемые (мономы) полного разложения, содержащие сомножителем $ a_3^{n_3} $, присутствуют в слагаемом $ C_n^{n_{_3}} (a_1+a_2)^{n-n_{_3}}a_3^{n_{_3}} $. Если нас интересует конкретное слагаемое, содержащее $ a_1^{n-n_{_2}}a_2^{n_{_2}}a_3^{n_3} $, то коэффициент при этом слагаемом вычислится с помощью биномиального разложения, т.е. он равен $$ C_n^{n_{_3}}C_{n-n_{_3}}^{n_2}=\frac{n!}{n_3!(n-n_3)!}\frac{(n-n_3)!}{n_2!(n-n_3-n_2)!}=\frac{n!}{(n-n_3-n_2)! n_2! n_3!} \ . $$

П

Пример.

$$ (a+b+c)^3=a^3+3\,a^2b+3\,a^2c+3\,ab^2+6\,abc+3\,ac^2+b^3+3\,b^2c+3\,bc^2+c^3 \ . $$

Непосредственное доказательство того, что мультиномиальные коэффициенты — числа целые (т.е. что число $ n_{}! $ делится нацело на $ n_1!\, n_2! \times \dots \times n_K! $ при $ n_1+ n_2+ \dots + n_K = n $) ЗДЕСЬ.

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

$$ \sum_{j=0}^n C_n^j =C_n^0+C_n^1+C_n^2+\dots+C_n^n = 2^n \ . $$ $$ \sum_{j=0}^n (-1)^jC_n^j = C_n^0-C_n^1+C_n^2-\dots+(-1)^nC_n^n = 0 \ . $$ $$ \sum_{j=2}^n C_j^2= C_2^2+C_3^2+\dots+C_n^2= \frac{(n-1)n(n+1)}{6}=C_{n+1}^3 \ . $$ $$ \sum_{m=0}^n C_{\ell+m-1}^{\ell-1}=C_{\ell-1}^{\ell-1}+C_{\ell}^{\ell-1}+C_{\ell+1}^{\ell-1}+\dots+C_{n+\ell-1}^{\ell-1} = C_{n+\ell}^{\ell} \, . $$ Формулы Вандермонда: $$ \sum_{j=0}^n (C_n^j)^2 = (C_n^0)^2+(C_n^1)^2+(C_n^2)^2+\dots+(C_n^n)^2 = C_{2n}^n \ ; $$ $$ \sum_{j=0}^k C_n^jC_m^{k-j}=C_n^0C_m^k+C_n^1C_m^{k-1}+\dots+C_n^{k-1}C_m^1+C_n^kC_m^0=C_{m+n}^k \ .$$ Связь с числами Фибоначчи: $$ \sum_{j=0}^{\lfloor n/2 \rfloor} C_{n-j}^j = C_n^0+C_{n-1}^1+C_{n-2}^2+\dots = F_n \ . $$ Здесь $ \lfloor \ \ \ \rfloor $ — целая часть числа. Идея доказательства ЗДЕСЬ.

П

Пример. $$C_8^0+C_7^1+C_6^2+C_5^3+C_4^4=34=F_8 \ . $$

Связь с числами Каталана: $$ C_{2n-2}^{n-1}-C_{2n-2}^{n}=C_{n-1} \, . $$

Задачи

1)
В литературе они иногда называются полиномиальными коэффициентами, но в настоящем ресурсе это выражение может привести к путанице с другим объектом.
binomial.txt · Последние изменения: 2020/10/20 01:00 — au