Номер 9.47, страница 107, часть 2 - гдз по алгебре 11 класс учебник Шыныбеков, Шыныбеков

9.47. Докажите, что:

1) число всех размещений с повторениями из $\text{n}$ элементов по $\text{k}$ находят по формуле $\tilde{A}_n^k = n^k$;

2) число всех размещений без повторений из $\text{n}$ элементов по $\text{k}$ находят по формуле $A_n^k = n(n-1)...(n-k+1)$ или $A_n^k = \frac{n!}{(n-k)!}$;

3) число всех перестановок из $\text{n}$ элементов находят по формуле $P_n = n!$;

4) число всех сочетаний из $\text{n}$ элементов по $\text{k}$ находят по формуле $C_n^k = \frac{n!}{k!(n-k)!}$

1) число всех размещений с повторениями из n элементов по k находят по формуле $\tilde{A}_n^k = n^k$

Размещение с повторениями из $\text{n}$ элементов по $\text{k}$ — это упорядоченный набор (кортеж) длины $\text{k}$, элементы которого выбираются из множества, содержащего $\text{n}$ элементов, причем элементы в наборе могут повторяться.

Для доказательства формулы воспользуемся комбинаторным правилом произведения. Нам нужно составить кортеж $(a_1, a_2, \dots, a_k)$ длины $\text{k}$.

На первое место ($a_1$) мы можем выбрать любой из $\text{n}$ данных элементов. Таким образом, у нас есть $\text{n}$ способов выбора.

Поскольку повторения разрешены, то на второе место ($a_2$) мы также можем выбрать любой из $\text{n}$ элементов, независимо от того, какой элемент был выбран на первое место. Снова имеем $\text{n}$ способов выбора.

Продолжая этот процесс, для каждого из $\text{k}$ мест в кортеже (от первого до $\text{k}$-го) у нас будет по $\text{n}$ возможных вариантов выбора.

Согласно правилу произведения, общее число способов составить такой кортеж равно произведению числа способов выбора для каждого места:

$\tilde{A}_n^k = \underbrace{n \cdot n \cdot \ldots \cdot n}_{k \text{ раз}} = n^k$.

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

Ответ: Доказательство приведено выше.

2) число всех размещений без повторений из n элементов по k находят по формуле $A_n^k = n(n-1)...(n-k+1)$ или $A_n^k = \frac{n!}{(n-k)!}$

Размещение без повторений из $\text{n}$ элементов по $\text{k}$ — это упорядоченный набор (кортеж) длины $\text{k}$, элементы которого выбираются из множества, содержащего $\text{n}$ различных элементов, причем элементы в наборе не могут повторяться. Очевидно, что $k \le n$.

Для доказательства первой формулы $A_n^k = n(n-1)...(n-k+1)$ воспользуемся правилом произведения. Мы формируем кортеж $(a_1, a_2, \dots, a_k)$.

На первое место ($a_1$) можно выбрать любой из $\text{n}$ элементов. Есть $\text{n}$ способов.

Так как повторения запрещены, на второе место ($a_2$) можно выбрать любой из оставшихся $n-1$ элементов. Есть $n-1$ способ.

На третье место ($a_3$) можно выбрать любой из оставшихся $n-2$ элементов. Есть $n-2$ способа.

Продолжая так далее, на $\text{k}$-е место ($a_k$), можно выбрать любой из оставшихся $n-(k-1) = n-k+1$ элементов. Есть $n-k+1$ способ.

По правилу произведения, общее число таких размещений равно:

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

Первая часть формулы доказана.

Теперь докажем вторую формулу $A_n^k = \frac{n!}{(n-k)!}$. Преобразуем полученное выражение, умножив и разделив его на $(n-k)! = (n-k)(n-k-1)\ldots \cdot 1$:

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

В числителе получилось произведение всех целых чисел от $\text{n}$ до 1, что по определению является факториалом числа $\text{n}$, то есть $n!$. В знаменателе стоит факториал числа $(n-k)$, то есть $(n-k)!$.

Следовательно, $A_n^k = \frac{n!}{(n-k)!}$.

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

Ответ: Доказательство приведено выше.

3) число всех перестановок из n элементов находят по формуле $P_n = n!$

Перестановка из $\text{n}$ элементов — это упорядоченный набор, в который входят все $\text{n}$ элементов данного множества по одному разу. Иными словами, перестановка — это размещение без повторений из $\text{n}$ элементов по $\text{n}$.

Таким образом, число перестановок $P_n$ является частным случаем числа размещений без повторений $A_n^k$ при $k=n$.

Воспользуемся формулой для числа размещений, подставив в неё $k=n$:

$P_n = A_n^n = n(n-1)\ldots(n-n+1) = n(n-1)\ldots \cdot 1$.

Произведение всех натуральных чисел от 1 до $\text{n}$ по определению есть факториал числа $\text{n}$, то есть $n!$.

$P_n = n!$.

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

$P_n = A_n^n = \frac{n!}{(n-n)!} = \frac{n!}{0!}$.

По определению, $0! = 1$, поэтому $P_n = \frac{n!}{1} = n!$.

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

Ответ: Доказательство приведено выше.

4) число всех сочетаний из n элементов по k находят по формуле $C_n^k = \frac{n!}{k!(n-k)!}$

Сочетание из $\text{n}$ элементов по $\text{k}$ — это неупорядоченный набор (подмножество) из $\text{k}$ различных элементов, выбранных из данного множества, содержащего $\text{n}$ элементов. В отличие от размещений, порядок элементов в сочетании не важен.

Для вывода формулы установим связь между числом сочетаний $C_n^k$ и числом размещений без повторений $A_n^k$. Процесс формирования размещения без повторений из $\text{n}$ по $\text{k}$ можно разбить на два последовательных этапа:

1. Выбрать неупорядоченное подмножество из $\text{k}$ элементов из исходного множества в $\text{n}$ элементов. Число способов сделать это равно $C_n^k$.

2. Взять выбранное подмножество из $\text{k}$ элементов и упорядочить его всеми возможными способами. Число способов упорядочить $\text{k}$ различных элементов равно числу перестановок из $\text{k}$ элементов, то есть $P_k = k!$.

Согласно правилу произведения, общее число размещений равно произведению числа способов на каждом этапе:

$A_n^k = C_n^k \cdot P_k$.

Из этого соотношения выразим искомое число сочетаний $C_n^k$:

$C_n^k = \frac{A_n^k}{P_k}$.

Используя доказанные ранее формулы $A_n^k = \frac{n!}{(n-k)!}$ и $P_k = k!$, получаем:

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

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

Ответ: Доказательство приведено выше.