Бином Ньютона - История изменений

СВ в 13:23, 24 октября 2026

2026-10-24T13:23:37Z

← Предыдущая		Версия 13:23, 24 октября 2026
Строка 44:		Строка 44:
	(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}		(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}
	</math>		</math>

			[[Файл:p18-01-binomial-expansion.svg\|frame\|none\|900px\|alt=Разложение (a+b) в четвёртой степени и выбор двух скобок из четырёх для коэффициента 6\|Рис. 1. В разложении <math>(a+b)^4</math> коэффициенты <math>1, 4, 6, 4, 1</math> — это <math>C(4,k)</math>. Коэффициент <math>6</math> при <math>a^2b^2</math> считает, сколькими способами из четырёх скобок можно выбрать две, чтобы взять из них <math>b</math>.]]

	Можно показать, что эта формула является следствием формулы [[Бином Ньютона\|бинома Ньютона]].		Можно показать, что эта формула является следствием формулы [[Бином Ньютона\|бинома Ньютона]].

СВ: /* Формула обращения */

2026-10-09T19:34:08Z

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

← Предыдущая		Версия 19:34, 9 октября 2026
Строка 161:		Строка 161:
	Для подстановки правильных биномиальных коэффициентов в эту формулу будет удобно воспользоваться треугольником Паскаля.		Для подстановки правильных биномиальных коэффициентов в эту формулу будет удобно воспользоваться треугольником Паскаля.
	В каждой строке для данного $n$ там выписаны все необходимые нам коэффициенты.		В каждой строке для данного $n$ там выписаны все необходимые нам коэффициенты.
	~~<math>a_0 = \binom{0}{0} b_0 = 2,</math>~~
	~~<math>a_1 = -\binom{1}{0} b_0 + \binom{1}{1} b_1 = -2+1 = -1,</math>~~
	~~<math>a_2 = \binom{2}{0} b_0 - \binom{2}{1} b_1 + \binom{2}{2} b_2 = 2 - 2\cdot 1 + 5 = 5,</math>~~
	~~$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>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>a_0 = \binom{0}{0} b_0 = 2</math>,<br />
	</math>b_0 = \binom{0}{0} a_0 = 2,<~~math~~>		<math>a_1 = -\binom{1}{0} b_0 + \binom{1}{1} b_1 = -2+1 = -1</math>,<br />
	</math>b_1 = \binom{1}{0} a_0 + \binom{1}{1} a_1 = 2 + (-1) = 1,<~~math~~>		<math>a_2 = \binom{2}{0} b_0 - \binom{2}{1} b_1 + \binom{2}{2} b_2 = 2 - 2\cdot 1 + 5 = 5</math>,<br />
	</math>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>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>,<br />
	</math>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>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>.
	</math>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.$$
			Теперь проверим правильность нахождения значений $a_n$ с помощью первой формулы<br />
			<math>b_0 = \binom{0}{0} a_0 = 2</math>,<br />
			<math>b_1 = \binom{1}{0} a_0 + \binom{1}{1} a_1 = 2 + (-1) = 1</math>,<br />
			<math>b_2 = \binom{2}{0} a_0 + \binom{2}{1} a_1 + \binom{2}{2} a_2 = 2 + 2\cdot(-1) + 5 = 5</math>,<br />
			<math>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>,<br />
			<math>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$ получены правильно.		Как видно, значения $b_n$ получены правильно.

СВ: Новая страница: «Положим $\prod_{x\in \varnothing} x = 1$. Пусть $x_1$, $x_2$, ..., $x_n$ {{---}} независимые переменные. Обозначим $X...»

2026-10-09T19:31:10Z

Новая страница: «Положим $\prod_{x\in \varnothing} x = 1$. Пусть $x_1$, $x_2$, ..., $x_n$ {{---}} независимые переменные. Обозначим $X...»

Новая страница

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

Пусть $x_1$, $x_2$, ..., $x_n$ {{---}} независимые переменные. Обозначим $X = \{x_1, x_2, ..., x_n\}$. Тогда
<math>
(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>
\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>
\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>

{{Следствие
|statement='''(формула бинома Ньютона)'''

<math> \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>
(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>
(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>
(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>
что и требовалось доказать.

{{Следствие
|statement=$\sum_{k=0}^{n} \binom{n}{k} = (1+1)^n = 2^n$
Что словесно можно сформулировать как "число всех подмножеств $n$-элементного множества равно $2^n$". Этот факт нам уже знаком.
}}
{{Следствие
|statement=Пусть $n > 0$. Тогда $\sum_{k=0}^{n} (-1)^k \binom{n}{k} = (1-1)^n = 0$.
Это равенство можно прочитать, например, как "суммарная мощность множества всех нечетных подмножеств множества
равна суммарной мощности всех его четных подмножеств".
Другими словами, число подмножеств четной и нечетной мощности совпадает.
}}
{{Замечание
|content='''(Дельта-функция).'''
Отметим, что если рассматривать выражение $\sum_{k=0}^{n} (-1)^k \binom{n}{k}$ как функцию от $n$ на множестве целых
чисел, мы получим дельта-функцию {{---}} функцию, которая принимает значение 1 только в одной точке и 0 во всех остальных:
<math> \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> \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>
\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) Доказательство, что из второй формулы следует первая, проводится аналогично.

{{Пример
|content=Пусть даны значения $b_0 = 2$, $b_1 = 1$, $b_2 = 5$, $b_3 = -2$, $b_4 = 3$
и верна первая формула. Воспользуемся второй формулой для вычисления значений $a_n$:
<math>
a_n = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} b_k, \quad n = 0,1,2,3,4.
</math>

Для подстановки правильных биномиальных коэффициентов в эту формулу будет удобно воспользоваться треугольником Паскаля.
В каждой строке для данного $n$ там выписаны все необходимые нам коэффициенты.
<math>a_0 = \binom{0}{0} b_0 = 2,</math>
<math>a_1 = -\binom{1}{0} b_0 + \binom{1}{1} b_1 = -2+1 = -1,</math>
<math>a_2 = \binom{2}{0} b_0 - \binom{2}{1} b_1 + \binom{2}{2} b_2 = 2 - 2\cdot 1 + 5 = 5,</math>
$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>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>b_0 = \binom{0}{0} a_0 = 2,<math>
</math>b_1 = \binom{1}{0} a_0 + \binom{1}{1} a_1 = 2 + (-1) = 1,<math>
</math>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>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>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.$$

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

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