Упр.304 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Задача

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 304. Докажите приведённую в этом разделе формулу для числа беспорядков. Указание. Найдите число перестановок, где хотя бы одно из чисел стоит на своём месте; используйте для этого формулу включений-исключений.

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

Обозначим через $$D_n$$ число беспорядков, то есть перестановок из $$n$$ элементов, в которых ни один элемент не стоит на своём месте.

Рассмотрим все перестановки из $$n$$ элементов. Их число равно $$n!$$.

Пусть $$A_i$$ — множество перестановок, в которых $$i$$-й элемент стоит на своём месте. Тогда число перестановок, где хотя бы один элемент стоит на своём месте, равно числу элементов объединения $$A_1 \cup A_2 \cup \dots \cup A_n$$.

По формуле включений-исключений:

$$ |A_1 \cup \dots \cup A_n| = \sum_{k=1}^{n}(-1)^{k-1}\sum |A_{i_1}\cap \dots \cap A_{i_k}|. $$

Если фиксированы $$k$$ элементов, стоящих на своих местах, то остальные $$n-k$$ элементов можно переставить $$ (n-k)! $$ способами. Таких наборов из $$k$$ фиксированных элементов $$\binom{n}{k}$$.

Значит, число перестановок, где хотя бы один элемент стоит на своём месте, равно

$$ \binom{n}{1}(n-1)!-\binom{n}{2}(n-2)!+\binom{n}{3}(n-3)!-\dots+(-1)^{n-1}\binom{n}{n}(n-n)!. $$

Тогда число беспорядков:

$$ D_n=n!-\left[\binom{n}{1}(n-1)!-\binom{n}{2}(n-2)!+\dots+(-1)^{n-1}\binom{n}{n}(n-n)!\right]. $$

Преобразуем каждый член:

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

Тогда

$$ D_n = n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\dots+(-1)^n\frac{1}{n!}\right). $$

Итак, получаем формулу для числа беспорядков:

$$ D_n=n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}. $$