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

Положим $\prod_{x\in \varnothing} x = 1$.

Пусть $x_1$, $x_2$, ..., $x_n$ — независимые переменные. Обозначим $X = \{x_1, x_2, ..., x_n\}$. Тогда [math]\displaystyle{ (1+x_1)(1+x_2)...(1+x_n)= \sum_{Y\subseteq X}\prod_{x\in Y}x. }[/math]

Проведем индукцию по $n$. Пусть $n=1$. Тогда $X = \{x_1\}$. [math]\displaystyle{ \sum_{Y\subseteq X}\prod_{x\in Y}x = \prod_{x\in \varnothing} x + \prod_{x\in\{x_1\}} x = 1+x_1. }[/math] База индукции доказана.

Пусть формула верна для всех $n\leq \widehat{n}$.

Положим $n=\widehat{n}+1$. $X = \{x_1, x_2, ..., x_{\widehat n}, x_{\widehat n+1}\}$. Тогда можно разбить сумму справа в формуле \ref{equation:04_pre_NewtonBinom} на слагаемые, которые содержат $x_{\widehat n+1}$ в качестве сомножителя, и те, которые не содержат: [math]\displaystyle{ \sum_{Y\subseteq X}\prod_{x\in Y}x = x_{\widehat n+1}\cdot\sum_{Y\subseteq X\setminus\{x_{\widehat n+1}\}}\prod_{x\in Y}x + \sum_{Y\subseteq X\setminus\{x_{\widehat n+1}\}}\prod_{x\in Y}x = = x_{\widehat n+1}(1+x_1)(1+x_2)...(1+x_{\widehat n}) + (1+x_1)(1+x_2)...(1+x_{\widehat n}) = =(1+x_{\widehat n+1})\cdot(1+x_1)(1+x_2)...(1+x_{\widehat n}). }[/math]

Следствие:

(формула бинома Ньютона) [math]\displaystyle{ \label{equation:04_binomNewton} (1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k }[/math]

Если в формулу $(1+x_1)(1+x_2)...(1+x_n)= \sum_{Y\subseteq X}\prod_{x\in Y}x$ подставить $x_1 = x_2 = ... = x_n = x$, то получим [math]\displaystyle{ (1+x)^n = \sum_{Y\subseteq X}\prod_{x\in Y}x = \sum_{Y\subseteq X} x^{|Y|}= = \sum_{k=0}^n \sum_{\substack{Y\subseteq X, |Y|=k}} x^k = \sum_{k=0}^n x^k \sum_{\substack{Y\subseteq X,\\ |Y|=k}} 1 = \sum_{k=0}^n \binom{n}{k} x^k }[/math]

Значения $\binom{n}{k}$ получили благодаря этой формуле название биномиальных коэффициентов.

Более часто используемой формой формулы бинома Ньютона является следующее уравнение: [math]\displaystyle{ (a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} }[/math]

Можно показать, что эта формула является следствием формулы бинома Ньютона. Если $b=0$, то формула $(a+0)^n = \sum_{k=0}^{n} \binom{n}{k} a^k$ очевидна.

Пусть $b\neq 0$. Тогда обозначим за $x$ значение $\frac{a}{b}$. Тогда [math]\displaystyle{ (a+b)^n = (b(\tfrac{a}{b}+1))^n = b^n(x+1)^n = b^n\sum_{k=0}^{n} \binom{n}{k} x^k = = \sum_{k=0}^{n} \binom{n}{k} b^n\cdot x^k = \sum_{k=0}^{n} \binom{n}{k} b^n\cdot (\tfrac{a}{b})^k = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} }[/math] что и требовалось доказать.

Следствие:

$\sum_{k=0}^{n} \binom{n}{k} = (1+1)^n = 2^n$ Что словесно можно сформулировать как "число всех подмножеств $n$-элементного множества равно $2^n$". Этот факт нам уже знаком.

Следствие:

Пусть $n > 0$. Тогда $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = (1-1)^n = 0$.

Это равенство можно прочитать, например, как "суммарная мощность множества всех нечетных подмножеств множества равна суммарной мощности всех его четных подмножеств".

Другими словами, число подмножеств четной и нечетной мощности совпадает.

Замечание

(Дельта-функция).

Отметим, что если рассматривать выражение $\sum_{k=0}^{n} (-1)^k \binom{n}{k}$ как функцию от $n$ на множестве целых чисел, мы получим дельта-функцию — функцию, которая принимает значение 1 только в одной точке и 0 во всех остальных: [math]\displaystyle{ \label{equation:04_delta-function_0} \delta_o(n) = \sum_{k=0}^{n} (-1)^k \binom{n}{k} = \left\{ \begin{array}{l} 1, n=0, \\ 0, n\neq 0. \end{array} \right. }[/math]

Пользуясь $\delta_o(n)$, можно получить и другие $\delta$-функции. Для любого целого числа $a$ можно определить $\delta_a(n)$ на множестве целых чисел следующим образом:

[math]\displaystyle{ \label{equation:04_delta-function} \delta_a(n) = \delta_o(n-a) = \sum_{k=0}^{n-a} (-1)^k \binom{n-a}{k} = \left\{ \begin{array}{l} 1, n=a, \\ 0, n\neq a. \end{array} \right. }[/math]

Формула обращения

Пусть даны две числовых последовательности $a_0$, $a_1$, $a_2$, ... и $b_0$, $b_1$, $b_2$, ... . Тогда следующие два утверждения эквивалентны:

• $b_n = \sum_{k=0}^n \binom{n}{k} a_k,\quad n=0,1,2...$
• $a_n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} b_k,\quad n=0,1,2...$

1) Для начала докажем, что из первой формулы следует вторая.

Пусть верно $b_n = \sum_{k=0}^n \binom{n}{k} a_k,$ $n=0,1,2...$. Тогда $\sum_{k=0}^n (-1)^{n-k} \binom{n}{k} b_k = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} \sum_{j=0}^k \binom{k}{j} a_j = \sum_{k=0}^n \sum_{j=0}^k (-1)^{n-k} \binom{n}{k} \binom{k}{j} a_j$

Прервем последовательность равенств, чтобы разъяснить следующее действие. Рассмотрим сумму $\sum_{k=0}^n \sum_{j=0}^k A(j,k)$. Сложение членов $A(j,k)$ идет по всем таким индексам $j$ и $k$, что $0\leq k\leq n$ и $0\leq j\leq k$. Иначе это условие можно записать как $0\leq j\leq k\leq n$.

Теперь рассмотрим условие $0\leq j\leq n$ и $j\leq k\leq n$, которое описывает ограничение на индексы $j$ и $k$ для суммы $\sum_{j=0}^n \sum_{k=j}^n A(j,k)$. Можно видеть, что это условие тоже эквивалентно записи $0\leq j\leq k\leq n$.

Таким образом, мы показали, что суммы $\sum_{k=0}^n \sum_{j=0}^k A(j,k)$ и $\sum_{j=0}^n \sum_{k=j}^n A(j,k)$ отличаются только порядком суммирования и, значит, $\sum_{k=0}^n \sum_{j=0}^k A(j,k) = \sum_{j=0}^n \sum_{k=j}^n A(j,k)$.

Теперь продолжим наши выкладки. $\sum_{k=0}^n \sum_{j=0}^k (-1)^{n-k} \binom{n}{k} \binom{k}{j} a_j = \sum_{j=0}^n \sum_{k=j}^n (-1)^{n-k} \binom{n}{k} \binom{k}{j} a_j =$ $ =\sum_{j=0}^n a_j\sum_{k=j}^n (-1)^{n-k} \binom{n}{k} \binom{k}{j} = \sum_{j=0}^n a_j\sum_{k=j}^n (-1)^{n-k} \binom{n}{j}\binom{n-j}{k-j} =$ $ =\sum_{j=0}^n \binom{n}{j} a_j\sum_{k=j}^n (-1)^{n-k} \binom{n-j}{k-j}$

Для следующего перехода сделаем замену переменной индексирования во второй сумме. Положим $l = n-k$. Тогда $k=n-l$, $k-j = n-j-l$. В то время как индекс $k$ пробегал все значения от $j$ до $n$, индекс $l$ будет пробегать значения от $n-j$ до нуля. Поскольку операция сложения на множестве вещественных чисел коммутативна (неважен порядок суммирования), будем считать, что переменная $l$ проходит значения от нуля до $n-j$. Тогда получим: $\sum_{j=0}^n \binom{n}{j} a_j\sum_{k=j}^n (-1)^{n-k} \binom{n-j}{k-j} = \sum_{j=0}^n \binom{n}{j} a_j\sum_{l=0}^{n-j} (-1)^{l} \binom{n-j}{n-j-l} =$ $= \sum_{j=0}^n \binom{n}{j} a_j\sum_{l=0}^{n-j} (-1)^{l} \binom{n-j}{l}$.

Из формулы для дельта функции следует, что $\sum_{l=0}^{n-j} (-1)^{l} \binom{n-j}{l} = \delta_j(n)$ и, значит, [math]\displaystyle{ \binom{n}{j} a_j\sum_{l=0}^{n-j} (-1)^{l} \binom{n-j}{l} = \left\{ \begin{array}{ll} \binom{j}{j} a_j = a_j, & n=j, \\ 0, & n\neq j. \end{array} \right. }[/math]

Таким образом, из всей последней суммы останется только одно слагаемое $\sum_{j=0}^n \binom{n}{j} a_j\sum_{l=0}^{n-j} (-1)^{l} \binom{n-j}{l} = \sum_{j=0}^n \binom{n}{j} a_j \delta_j(n) = a_n,$ что и требовалось доказать.

2) Доказательство, что из второй формулы следует первая, проводится аналогично.

Пример

Пусть даны значения $b_0 = 2$, $b_1 = 1$, $b_2 = 5$, $b_3 = -2$, $b_4 = 3$

и верна первая формула. Воспользуемся второй формулой для вычисления значений $a_n$: [math]\displaystyle{ a_n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} b_k, \quad n = 0,1,2,3,4. }[/math]

Для подстановки правильных биномиальных коэффициентов в эту формулу будет удобно воспользоваться треугольником Паскаля. В каждой строке для данного $n$ там выписаны все необходимые нам коэффициенты.

[math]\displaystyle{ a_0 = \binom{0}{0} b_0 = 2 }[/math],
[math]\displaystyle{ a_1 = -\binom{1}{0} b_0 + \binom{1}{1} b_1 = -2+1 = -1 }[/math],
[math]\displaystyle{ a_2 = \binom{2}{0} b_0 - \binom{2}{1} b_1 + \binom{2}{2} b_2 = 2 - 2\cdot 1 + 5 = 5 }[/math],
[math]\displaystyle{ a_3 = - \binom{3}{0} b_0 + \binom{3}{1} b_1 - \binom{3}{2} b_2 + \binom{3}{3} b_3 = -2 + 3\cdot 1 - 3\cdot 5 + (- 2) = -16 }[/math],
[math]\displaystyle{ a_4 = \binom{4}{0} b_0 - \binom{4}{1} b_1 + \binom{4}{2} b_2 - \binom{4}{3} b_3 + \binom{4}{4} b_4 = 2 - 4\cdot 1 + 6\cdot 5 - 4\cdot (-2) + 3 = 39 }[/math].

Теперь проверим правильность нахождения значений $a_n$ с помощью первой формулы
[math]\displaystyle{ b_0 = \binom{0}{0} a_0 = 2 }[/math],
[math]\displaystyle{ b_1 = \binom{1}{0} a_0 + \binom{1}{1} a_1 = 2 + (-1) = 1 }[/math],
[math]\displaystyle{ b_2 = \binom{2}{0} a_0 + \binom{2}{1} a_1 + \binom{2}{2} a_2 = 2 + 2\cdot(-1) + 5 = 5 }[/math],
[math]\displaystyle{ b_3 = \binom{3}{0} a_0 + \binom{3}{1} a_1 + \binom{3}{2} a_2 + \binom{3}{3} a_3 = 2 + 3\cdot(-1) + 3\cdot 5 + (-16) = -2 }[/math],
[math]\displaystyle{ b_4 = \binom{4}{0} a_0 + \binom{4}{1} a_1 + \binom{4}{2} a_2 + \binom{4}{3} a_3 + \binom{4}{4} a_4 = 2 + 4\cdot(-1) + 6\cdot 5 + 4\cdot(-16) + 39 = 3 }[/math].

Как видно, значения $b_n$ получены правильно.

Конспект: Дискретная математика