Номер 6.25, страница 42, часть 2 - гдз по алгебре 10 класс учебник Мордкович, Семенов

6.25. a) Докажите, что количество разных непустых наборов, которые можно сделать из $n$ различных предметов, равно $2^n - 1$.

б) Докажите, что $n$ различных предметов можно расставить в ряд $n!$ способами.

а) Докажем это утверждение с помощью комбинаторных рассуждений.
Пусть у нас есть множество, состоящее из $n$ различных предметов. При формировании любого набора (подмножества) для каждого из $n$ предметов существует ровно два варианта: либо этот предмет входит в набор, либо не входит.
Поскольку выбор для каждого предмета независим от выбора для других предметов, общее количество возможных наборов можно найти, перемножив количество вариантов для каждого предмета. Так как предметов $n$, а для каждого есть 2 варианта, общее число всех возможных наборов (включая пустой) равно:
$2 \cdot 2 \cdot \dots \cdot 2$ ($n$ раз) = $2^n$.
Эта формула включает в себя один случай, когда мы не выбираем ни одного предмета, то есть получаем пустой набор. В условии задачи сказано, что нужно найти количество непустых наборов. Следовательно, из общего числа всех возможных наборов нужно вычесть один случай, соответствующий пустому набору.
Таким образом, количество разных непустых наборов равно $2^n - 1$.

Альтернативное доказательство через биномиальные коэффициенты:
Количество способов выбрать $k$ предметов из $n$ равно биномиальному коэффициенту $\binom{n}{k}$. Чтобы найти общее количество непустых наборов, нужно сложить количество наборов всех возможных размеров от 1 до $n$:
Сумма = $\binom{n}{1} + \binom{n}{2} + \dots + \binom{n}{n}$.
Известна формула бинома Ньютона: $\sum_{k=0}^{n} \binom{n}{k} = \binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n} = 2^n$.
Поскольку $\binom{n}{0} = 1$ (это и есть пустой набор), то искомая сумма равна:
$(\binom{n}{0} + \binom{n}{1} + \dots + \binom{n}{n}) - \binom{n}{0} = 2^n - 1$.
Оба способа приводят к одному и тому же результату.
Ответ: Количество разных непустых наборов, которые можно составить из $n$ различных предметов, действительно равно $2^n - 1$.

б) Докажем это утверждение, используя основное правило комбинаторики (правило умножения).
Задача состоит в том, чтобы разместить $n$ различных предметов на $n$ позициях в ряду. Такое упорядоченное расположение называется перестановкой.
Рассмотрим процесс заполнения позиций поочередно:

• На первую позицию в ряду мы можем поставить любой из $n$ предметов. Таким образом, у нас есть $n$ вариантов выбора.
• После того как мы поставили один предмет на первую позицию, у нас осталось $n-1$ предметов. На вторую позицию мы можем поставить любой из оставшихся $n-1$ предметов. Значит, для второй позиции есть $n-1$ вариант.
• Для третьей позиции, соответственно, останется $n-2$ предмета, то есть $n-2$ варианта.
• ...
• Этот процесс продолжается до последней, $n$-ой позиции. К этому моменту останется только один предмет, поэтому для последней позиции существует всего 1 вариант.

Согласно правилу умножения, общее количество способов расставить все предметы равно произведению числа вариантов для каждой позиции:
$N = n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 2 \cdot 1$.
Это произведение по определению является факториалом числа $n$ и обозначается как $n!$.
Таким образом, существует $n!$ различных способов расставить $n$ различных предметов в ряд.
Ответ: $n$ различных предметов можно расставить в ряд $n!$ способами.