Биномиальная теорема с комбинаторной точки зрения

Биномиальная теорема описывает, как раскрывать выражение вида $(x + y)^n$. Ниже мы рассмотрим её с комбинаторной точки зрения, превратив абстрактное алгебраическое раскрытие в конкретную задачу подсчёта, и подробно докажем теорему.

Формулировка биномиальной теоремы

Для любого неотрицательного целого числа $n$:

$$(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$$

где $\binom{n}{k}$ — число сочетаний (количество способов выбрать $k$ из $n$), определяемое как:

$$\binom{n}{k} = \frac{n!}{k! (n-k)!}$$

Основная идея комбинаторного доказательства

Ключевая мысль: рассматривать процесс раскрытия $(x + y)^n$ как выбор $x$ или $y$ из каждого из $n$ множителей $(x + y)$ и последующее перемножение, а затем объяснить коэффициенты через подсчёт числа способов выбора.

Конкретный процесс раскрытия

1. Структура произведения:
   Представим $(x + y)^n$ как произведение $n$ множителей $(x + y)$:
   $(x + y)^n = (x + y)(x + y)\cdots(x + y) \quad (\text{всего } n \text{ множителей})$

2. Способ получения слагаемых:
   После раскрытия каждое слагаемое имеет вид $x^{n-k} y^k$, и оно получается путём выбора $k$ множителей, из которых берётся $y$, а из остальных $n-k$ — $x$. Например:

   • При $n=3$ слагаемое $x^2 y$ возникает, если из 3 множителей выбрать 1, из которого берётся $y$, а из остальных — $x$. Существует $\binom{3}{1}=3$ способа такого выбора.

3. Соответствие коэффициентов и чисел сочетаний:
   Коэффициент при слагаемом $x^{n-k} y^k$ равен количеству способов выбрать $k$ множителей, дающих $y$, то есть $\binom{n}{k}$. Например:

   • В $(x + y)^3$ коэффициент при $x y^2$ равен $\binom{3}{2}=3$, что соответствует трём способам выбора двух множителей для $y$: $(y,y,x)$, $(y,x,y)$, $(x,y,y)$.

Формальное математическое доказательство

1. Анализ получения слагаемых:
   Все возможные слагаемые в сумме порождаются следующим процессом выбора:

   • Из каждого множителя $(x + y)$ выбирается $x$ или $y$.
   • Результаты выбора перемножаются, получая слагаемое вида $x^{n-k} y^k$.

2. Роль чисел сочетаний:
   Количество способов выбрать $k$ множителей, дающих $y$, равно $\binom{n}{k}$, поэтому коэффициент при $x^{n-k} y^k$ равен $\binom{n}{k}$. Суммируя по всем возможным $k$ (от $0$ до $n$), получаем полное разложение.

Проверка на примере

Для $n=4$:

$$(x + y)^4 = \binom{4}{0}x^4 + \binom{4}{1}x^3 y + \binom{4}{2}x^2 y^2 + \binom{4}{3}x y^3 + \binom{4}{4}y^4$$

После раскрытия:

$$x^4 + 4x^3 y + 6x^2 y^2 + 4x y^3 + y^4$$

Коэффициенты $\{1,4,6,4,1\}$ в точности соответствуют числам сочетаний $\binom{4}{k}$, что подтверждает верность теоремы.