11679. Round table

In how many ways can n distinct people be seated around a round table? Two seatings are considered the same if one can be obtained from the other by rotating the table.

Input. One positive integer n (n ≤ 20).

Output. Print the number of distinct ways to seat n different people around a round table.

Sample input	Sample output
4	6

SOLUTION

combinatorics

Algorithm analysis

Unlike seating in a row, a round table has no fixed starting point. Therefore, all arrangements that differ only by a cyclic shift are considered the same.

If the people were seated in a row, the number of possible arrangements would be n!, since n distinct people can be permuted arbitrarily.

For a round table, each specific seating can be rotated in n different ways, producing n equivalent linear permutations.

For example, for the seating (1, 2, 3, 4), the rotations give:

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

All these seatings are considered the same.

Therefore, each unique circular arrangement corresponds to exactly n linear permutations.

To obtain the number of distinct seatings around a round table, the total number of permutations must be divided by the number of equivalent rotations:

= (n – 1)!

Example

For 4 people, there are 6 distinct arrangements:

· (1, 2, 3, 4)

· (1, 2, 4, 3)

· (1, 3, 2, 4)

· (1, 3, 4, 2)

· (1, 4, 2, 3)

· (1, 4, 3, 2)

All other arrangements can be reduced to one of the listed ones by rotation. For example, the arrangement (4, 2, 1, 3) is equivalent to (1, 3, 4, 2).

Algorithm implementation

Read the input value of n.

scanf("%lld", &n);

The answer is computed in the variable res.

res = 1;

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

res = res * i;

Print the answer.

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