Упр.6.25 ГДЗ Мордковича 10 класс профильный уровень (Алгебра)

Задача

Рассмотрим вариант решения задания из учебника Мордкович, Семенов 10 класс, Мнемозина: а) Докажите, что количество разных непустых наборов, которые можно сделать из n различных предметов, равно 2^n — 1. б) Докажите, что n различных предметов можно расставить в ряд п! способами (см. № 1.36).

Подробный ответ

а) Обозначим через $$Q_n$$ число всех различных непустых наборов из $$n$$ различных предметов.

Для одного предмета есть только один непустой набор, значит $$Q_1=1$$.

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

$$Q_{n+1}=2Q_n+1.$$

Проверим формулу $$Q_n=2^n-1$$:

$$Q_1=2^1-1=1.$$

Если для некоторого $$n$$ верно $$Q_n=2^n-1$$, то

$$ Q_{n+1}=2Q_n+1=2(2^n-1)+1=2^{n+1}-1. $$

Следовательно, для любого $$n$$

$$Q_n=2^n-1.$$

б) Обозначим через $$P_n$$ число способов расставить в ряд $$n$$ различных предметов.

Для одного предмета имеем $$P_1=1$$.

Пусть уже известно, что $$n-1$$ предмет можно расставить $$P_{n-1}$$ способами. Тогда при добавлении $$n$$-го предмета его можно поставить на любое из $$n$$ мест в каждом из этих рядов, значит

$$P_n=nP_{n-1}.$$

Проверим формулу $$P_n=n!$$:

$$P_1=1!=1.$$

Если для некоторого $$n$$ верно $$P_n=n!$$, то

$$ P_{n+1}=(n+1)P_n=(n+1)n!=(n+1)!. $$

Значит, для любого $$n$$

$$P_n=n!.$$