11679. Круглый стол

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

Вход. Одно положительное целое число n (n ≤ 20).

Выход. Выведите количество различных способов рассадить n разных людей вокруг круглого стола.

Пример входа	Пример выхода
4	6

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

В отличие от рассадки в ряд, у круглого стола нет фиксированного начала. Поэтому все расстановки, которые отличаются только циклическим сдвигом, считаются одинаковыми.

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

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

Например, для размещения (1, 2, 3, 4) повороты дают:

(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)

Все эти расположения считаются одинаковыми.

Следовательно, каждое уникальное круговое расположение соответствует ровно n линейным перестановкам.

Чтобы получить число различных рассадок вокруг круглого стола, нужно общее число перестановок разделить на число эквивалентных поворотов:

= (n – 1)!

Пример

Для 4 людей существует 6 различных расположений:

· (1, 2, 3, 4)

· (1, 2, 4, 3)

· (1, 3, 2, 4)

· (1, 3, 4, 2)

· (1, 4, 2, 3)

· (1, 4, 3, 2)

Все остальные расположения с помощью поворота можно свести к одному из перечисленных. Например, расположение (4, 2, 1, 3) эквивалентно расположению (1, 3, 4, 2).

Реализация алгоритма

Читаем входное значение n.

scanf("%lld", &n);

В переменной res вычисляем ответ.

res = 1;

for (i = 1; i < n; i++)

res = res * i;

Выводим ответ.

printf("%lld\n", res);