УказательРазделыОбозначенияАвторО проекте


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

Бином

Задача. Для произвольных вещественных чисел 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_{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) В литературе они иногда называются полиномиальными коэффициентами, но в настоящем ресурсе это выражение может привести к путанице с другим объектом.

2018/12/06 20:53 редактировал au