Round table#11679

Round table (Editorial)

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)$ (1, 2, 3, 4), the rotations give:

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

(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:

\frac{n !}{n} = (n - 1)!

\frac{n!}{n} = (n - 1)!

Example

For $4$ people, there are $6$ distinct arrangements:

$(1, 2, 3, 4)$ (1, 2, 3, 4)
$(1, 2, 4, 3)$ (1, 2, 4, 3)
$(1, 3, 2, 4)$ (1, 3, 2, 4)
$(1, 3, 4, 2)$ (1, 3, 4, 2)
$(1, 4, 2, 3)$ (1, 4, 2, 3)
$(1, 4, 3, 2)$ (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)$ (4, 2, 1, 3) is equivalent to $(1, 3, 4, 2)$ (1, 3, 4, 2).

Algorithm implementation

Read the input value of $n$ .

scanf("%lld", &n);

The answer is computed in the variable $r es$ .

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

Print the answer.

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