Номер 771, страница 231 - гдз по алгебре 9 класс учебник Никольский, Потапов

Доказываем (771-772).

771. Докажите формулу: $C_n^k = \frac{n!}{k!(n - k)!}$

771.

Для доказательства формулы числа сочетаний $C_n^k = \frac{n!}{k!(n-k)!}$ воспользуемся комбинаторными рассуждениями и установим связь между сочетаниями и размещениями.

По определению, числом сочетаний из $n$ элементов по $k$, обозначаемым $C_n^k$, является количество способов выбрать $k$ элементов из множества, содержащего $n$ различных элементов, без учёта порядка выбора.

С другой стороны, число размещений из $n$ элементов по $k$, обозначаемое $A_n^k$, — это количество способов выбрать $k$ элементов из $n$ и расположить их в определённом порядке. Вычислим $A_n^k$. Первый элемент можно выбрать $n$ способами, второй — $(n-1)$ способами (так как один элемент уже выбран), и так далее, до $k$-го элемента, который можно выбрать $(n-k+1)$ способами. По правилу произведения, общее число размещений равно:

$A_n^k = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)$

Эту формулу можно записать с использованием факториалов. Для этого умножим и разделим правую часть на $(n-k)!$:

$A_n^k = \frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+1) \cdot (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!}$

Теперь установим связь между размещениями и сочетаниями. Процесс создания одного размещения (упорядоченного набора из $k$ элементов) можно представить как выполнение двух последовательных шагов:

1. Сначала мы выбираем $k$ элементов из $n$ без учёта их порядка. По определению, количество способов это сделать равно $C_n^k$.

2. Затем мы упорядочиваем эти $k$ выбранных элементов. Число способов упорядочить (переставить) $k$ различных элементов равно числу перестановок из $k$ элементов, то есть $k!$.

По правилу произведения, общее число размещений $A_n^k$ равно произведению числа способов совершить первый шаг на число способов совершить второй шаг:

$A_n^k = C_n^k \cdot k!$

Из этого равенства выразим $C_n^k$:

$C_n^k = \frac{A_n^k}{k!}$

Теперь подставим в эту формулу ранее полученное выражение для $A_n^k$ через факториалы:

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

Упростив это выражение, получаем искомую формулу:

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

Таким образом, формула доказана.

Ответ: Формула $C_n^k = \frac{n!}{k!(n-k)!}$ доказана путём установления связи между числом сочетаний и числом размещений ($A_n^k = C_n^k \cdot k!$) и последующей подстановкой формулы для числа размещений $A_n^k = \frac{n!}{(n-k)!}$.