Номер 506, страница 191 - гдз по алгебре 11 класс учебник Колягин, Ткачева

Упражнения к главе V. Глава 5. Комбинаторика - номер 506, страница 191.

506. Доказать, что число круговых перестановок (важен порядок следования расположенных на окружности элементов, а начальный элемент безразличен) из $n$ элементов равно $(n - 1)!$.

Для доказательства того, что число круговых перестановок из $n$ различных элементов равно $(n-1)!$, рассмотрим два подхода.

Подход 1: Связь с линейными перестановками

1. Сначала рассмотрим все возможные линейные перестановки, то есть расположения $n$ различных элементов в ряд. Количество таких перестановок равно $P_n = n!$.

2. Круговая перестановка отличается тем, что у нее нет начала и конца. Расположения, которые можно совместить поворотом, считаются одинаковыми. Возьмем одну любую круговую перестановку. Если мы будем последовательно выбирать каждый из $n$ элементов в качестве начального, мы получим $n$ различных линейных перестановок.

Например, для $n=4$ элементов $\{A, B, C, D\}$, расположенных по кругу в порядке A-B-C-D, мы можем получить 4 разные линейные перестановки: $(A, B, C, D)$, $(B, C, D, A)$, $(C, D, A, B)$ и $(D, A, B, C)$. Все они соответствуют одной и той же круговой перестановке.

3. Таким образом, общее число всех линейных перестановок ($n!$) можно разбить на группы, где каждая группа состоит из $n$ перестановок, соответствующих одной уникальной круговой перестановке.

4. Чтобы найти число круговых перестановок, которое обозначим $Q_n$, нужно общее число линейных перестановок разделить на $n$:

$Q_n = \frac{P_n}{n} = \frac{n!}{n}$

Используя свойство факториала $n! = n \times (n-1)!$, получаем:

$Q_n = \frac{n \times (n-1)!}{n} = (n-1)!$

Подход 2: Метод фиксации одного элемента

1. Этот подход более интуитивен. Поскольку в круговой перестановке не важно, какой элемент стоит на "первом" месте (так как такого места нет), мы можем произвольно выбрать один элемент и зафиксировать его положение. Например, мысленно посадим элемент $e_1$ на определенное место за круглым столом. Этот шаг устраняет симметрию вращения.

2. После того, как один элемент зафиксирован, у нас остается $n-1$ свободных мест и $n-1$ различных элементов, которые нужно по этим местам распределить.

3. Задача свелась к нахождению числа способов расставить оставшиеся $n-1$ элементов на $n-1$ упорядоченных местах. Места теперь упорядочены, так как они имеют определенное положение относительно первого, зафиксированного элемента (например, "место слева от $e_1$", "второе место слева от $e_1$" и т.д.).

4. Это эквивалентно нахождению числа линейных перестановок для $n-1$ элементов. Число таких перестановок равно:

$P_{n-1} = (n-1)!$

Оба метода доказывают, что искомое число равно $(n-1)!$.

Ответ:
Утверждение доказано. Число круговых перестановок из $n$ элементов равно $(n-1)!$. Это следует из того, что, зафиксировав положение одного элемента для устранения симметрии вращения, задача сводится к нахождению числа линейных перестановок для оставшихся $n-1$ элементов, что составляет $(n-1)!$. Альтернативно, это можно получить, разделив общее число линейных перестановок $n!$ на $n$, поскольку каждая круговая перестановка соответствует $n$ линейным.