Вопросы, страница 80 - гдз по алгебре 9 класс учебник Солтан, Солтан

10. Сочетания без повторений. II. Элементы комбинаторики - страница 80.

Условие.

1. Дайте определение понятия сочетаний без повторений из $n$ элементов по $k$ элементов.

2. По какой формуле можно найти число сочетаний из $n$ элементов по $k$?

3. Докажите, что: а) $C_n^k = \frac{n}{k}C_{n-1}^{k-1}$; б) $C_n^k = \frac{n-k+1}{k}C_n^{k-1}$.

Решение.

Решение 2 (rus).

1. Сочетаниями без повторений из $n$ элементов по $k$ (где $k \le n$) называется любое подмножество из $k$ элементов, выбранных из данного множества, состоящего из $n$ различных элементов. В сочетаниях, в отличие от размещений, порядок выбора элементов не имеет значения. Например, выборка {a, b, c} и выборка {c, b, a} представляют собой одно и то же сочетание.

Ответ: Сочетания без повторений из $n$ по $k$ — это неупорядоченные выборки объема $k$ из множества, содержащего $n$ различных элементов.

2. Число сочетаний из $n$ элементов по $k$ обозначается $C_n^k$ и находится по формуле: $C_n^k = \frac{n!}{k!(n-k)!}$, где $n!$ — это факториал числа $n$ (произведение всех натуральных чисел от 1 до $n$).

Ответ: $C_n^k = \frac{n!}{k!(n-k)!}$.

3. а) Докажем тождество $C_n^k = \frac{n}{k}C_{n-1}^{k-1}$. Для этого преобразуем правую часть равенства, используя основную формулу для числа сочетаний. По определению, $C_{n-1}^{k-1} = \frac{(n-1)!}{(k-1)!(n-1-(k-1))!} = \frac{(n-1)!}{(k-1)!(n-k)!}$. Подставим это выражение в правую часть доказываемого тождества: $\frac{n}{k}C_{n-1}^{k-1} = \frac{n}{k} \cdot \frac{(n-1)!}{(k-1)!(n-k)!}$. Сгруппируем множители: $\frac{n \cdot (n-1)!}{k \cdot (k-1)! \cdot (n-k)!}$. Учитывая, что по определению факториала $n \cdot (n-1)! = n!$ и $k \cdot (k-1)! = k!$, получаем $\frac{n!}{k!(n-k)!}$. Это выражение по определению равно $C_n^k$, то есть левой части тождества. Равенство доказано.

Ответ: Тождество доказано путем преобразования его правой части $\frac{n}{k}C_{n-1}^{k-1}$ к виду $\frac{n!}{k!(n-k)!}$, что соответствует левой части $C_n^k$.

3. б) Докажем тождество $C_n^k = \frac{n-k+1}{k}C_{n}^{k-1}$. Преобразуем правую часть. По определению, $C_{n}^{k-1} = \frac{n!}{(k-1)!(n-(k-1))!} = \frac{n!}{(k-1)!(n-k+1)!}$. Подставим это в правую часть тождества: $\frac{n-k+1}{k}C_{n}^{k-1} = \frac{n-k+1}{k} \cdot \frac{n!}{(k-1)!(n-k+1)!}$. Учитывая, что $(n-k+1)! = (n-k+1) \cdot (n-k)!$, можно сократить множитель $(n-k+1)$ в числителе и знаменателе: $\frac{n-k+1}{k} \cdot \frac{n!}{(k-1)!(n-k+1)(n-k)!} = \frac{1}{k} \cdot \frac{n!}{(k-1)!(n-k)!}$. Теперь сгруппируем множители в знаменателе: $\frac{n!}{k \cdot (k-1)! \cdot (n-k)!}$. Так как $k \cdot (k-1)! = k!$, получаем $\frac{n!}{k!(n-k)!}$. Это выражение равно $C_n^k$, то есть левой части тождества. Равенство доказано.

Ответ: Тождество доказано путем преобразования его правой части $\frac{n-k+1}{k}C_{n}^{k-1}$ к виду $\frac{n!}{k!(n-k)!}$, что соответствует левой части $C_n^k$.