==Бином Ньютона==
~~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_{} $ //справедливы следующие
равенства//:
$$ C_n^m=C_n^{n-m} \qquad \qquad \qquad \qquad {\color{Red}{ (1)} } \, , $$
$$C_n^m + C_n^{m+1}=C_{n+1}^{m+1} \qquad \qquad \qquad {\color{Red}{ (2)} } \, . $$
!!Т!! **Теорема 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}
$$
Последнее равенство следует из формулы $ {\color{Red}{ (2)} } $.
♦
Для малых значений показателя $ 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} \, . $$
===Бином и число π==
Как оценить скорость роста биномиальных коэффициентов $ C_n^m$ при возрастании $n$? Очевидно, что максимальное из чисел
$$
C_n^0, C_n^1, \dots, C_n^n
$$
достигается на $C_n^{\lfloor n/2 \rfloor} $.
!!Т!! **Теорема.** //Имеет место равенство//
$$
\lim_{n\to +\infty} \frac{C_n^{\lfloor n/2 \rfloor}}{\left[ 2^{n+1} /\sqrt{2\pi n} \right]} =1 \, .
$$
Этот результат является следствием ((:interpolation#drugie_ehksponenty теоремы Муавра-Лапласа)).
!!П!! **Пример.**
$$
C_{20}^{10} = 184756, \ 2^{21} /\sqrt{40\pi} \approx 1.870789 \times 10^5 \, ,
$$
$$
C_{55}^{27} = 3824345300380220 , \ 2^{56} /\sqrt{110\pi} \approx 3.876220 \times 10^{15} \, .
$$
===Бином и число e==
Положим в формуле бинома $ a=1, b=1/n $:
$$
\left(1+\frac{1}{n} \right)^n = 1 + C_n^1 \frac{1}{n}+ C_n^2 \frac{1}{n^2}+ C_n^3 \frac{1}{n^3} + \dots + C_n^n \frac{1}{n^n}=
$$
$$
=1+1+\frac{1}{2!} \cdot \frac{n(n-1)}{n^2} + \frac{1}{3!} \cdot \frac{n(n-1)(n-2)}{n^3}+ \dots +
\frac{1}{n!} \cdot \frac{n(n-1)(n-2)\times \dots \times 1}{n^n} =
$$
$$
=1+1+ \frac{1}{2!} \left(1-\frac{1}{n} \right) + \frac{1}{3!} \left(1-\frac{1}{n} \right)
\left(1-\frac{2}{n} \right) + \dots +
\frac{1}{n!} \left(1-\frac{1}{n} \right)\left(1-\frac{2}{n} \right)\times \dots \times \left(1-\frac{n-1}{n} \right)
$$
Теперь перейдем к пределу при $ n \to + \infty $. С первыми слагаемыми проблем не возникает:
$$
\lim_{n\to +\infty} \left(1-\frac{1}{n} \right) = 1, \ \lim_{n\to +\infty} \left(1-\frac{1}{n} \right)\left(1-\frac{2}{n} \right) = 1, \dots
$$
Но со множителем при $ 1/n^n $ в последнем слагаемом ситуация оказывается совершенно иной:
$$
\lim_{n\to +\infty} \left(1-\frac{1}{n} \right)\left(1-\frac{2}{n} \right)\times \dots \times \left(1-\frac{n-1}{n} \right) =0 \, .
$$
И можно, разве что, утверждать, что рассматриваемое разложение
$$
\le 1+1+\frac{1}{2!} + \frac{1}{3!}+ \dots + \frac{1}{n!} \, .
$$
Тем не менее, можно доказать, что предел при $ n \to + \infty $ у последнего выражения существует, он совпадает с
$$
\lim_{n\to +\infty} \left(1+\frac{1}{n} \right)^n
$$
и равен числу Эйлера
$$
e \approx 2.718281828459045\dots
$$
===Биномиальное распределение==
с параметрами $ n $ and $ p $ --- это дискретное распределение вероятностей с количеством успехов в $ n $ независимых экспериментах (испытаниях, событиях), каждый из которых дает однозначный результат в стиле "да-нет" на поставленный в эксперименте вопрос. При этом ответ "да" (успех) происходит с вероятностью $p$, а ответ "нет" (неудача) --- с вероятностью $q:=1-p$.
Каждый отдельный эксперимент также называется **испытанием Бернулли**[[Bernoulli trial]], а последовательность (серия) результатов этих экспериментов --- процессом Бернулли.
!!Т!! **Теорема [Бернулли].** //Если вероятность некоторого события равна// $ p $, //то вероятность того, что в серии из// $ n $ //испытаний это событие произойдет ровно в// $ m $ //испытаниях равна//
$$
C_n^mp^m(1-p)^{n-m} \, .
$$
**Доказательство** проводится индукцией по $n$. Пусть утверждение верно для случая $n$ испытаний, т.е. вероятность того, что будет достигнуто ровно $m-1$ успехов равна
$$
C_n^{m-1}p^{m-1}(1-p)^{n-m+1}
$$
а вероятность того, что будет достигнуто ровно $m$ успехов равна
$$
C_n^{m}p^{m}(1-p)^{n-m} \, .
$$
Тогда вероятность того, что в серии из $n+1$ испытания будет достигнуто $ m $ успехов равна ((:probability#slozhenie_sobytij сумме вероятностей)) двух событий:
* в $n$ испытаниях достигнуто $m-1$ успехов, а в следующем за ними испытании достигнут успех; вероятность равна
$$
p C_n^{m-1}p^{m-1}(1-p)^{n-m+1} \ ;
$$
* в $n$ испытаниях достигнуто $m$ успехов, а следующее за ними испытание неудачно; вероятность равна
$$
(1-p)C_n^{m}p^{m}(1-p)^{n-m} \, .
$$
На основании формулы $ {\color{Red}{ (2)} } $ сумма двух вероятностей совпадает с $ C_{n+1}^mp^m(1-p)^{n-m+1} $.
♦
!!П!! **Пример.** В серии из $10$ подбрасываний монеты ($p=1/2$) вероятность того, что в $ 5 $ испытаниях выпадет "орел", а в $ 5 $ --- "решка" равна
$$
C_{10}^5\frac{1}{2^{10}}=\frac{63}{256} \approx 0.246 \, .
$$
Для случая $p=1/2$ иллюстрацией процесса Бернулли служит ((https://en.wikipedia.org/wiki/Galton_board доска Гальтона)).
===Задачи==
☞
((:binomial:problems ЗДЕСЬ))