==Бином Ньютона==
~~TOC~~
===Бином==
**Задача.** Для произвольных вещественных чисел $ 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} .
$$
**Доказательство** ведется ((:basics:induction индукцией)) по $ 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 $ //с помощью
обобщения биномиальных коэффициентов --- так называемых// **мультиномиальных
коэффициентов**[[В литературе они иногда называются //полиномиальными коэффициентами//, но в настоящем ресурсе это выражение может привести к путанице с
☞
((:polynomial#общая_информация другим объектом)).]]:
$$(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 $)
☞
((:numtheory:vspom1 ЗДЕСЬ)).
=== Суммы биномиальных коэффициентов ==
$$ \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 \ .$$
Связь с ((recurr#линейное_уравнение числами Фибоначчи)):
$$ \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 $ --- ((:algebra2:notations#целая_часть_числа целая часть числа)). Идея доказательства
☞
((:algebra2:skewsym ЗДЕСЬ)).
!!П!! **Пример.**
$$C_8^0+C_7^1+C_6^2+C_5^3+C_4^4=34=F_8 \ . $$
Связь с ((:gruppe:vspom1#числа_каталана числами Каталана)):
$$ C_{2n-2}^{n-1}-C_{2n-2}^{n}=C_{n-1} \, . $$
===Задачи==
☞
((:binomial:problems ЗДЕСЬ))