Two Round Dances#11602

Two Round Dances (Editorial)

First, we should select $n /2$ people for the first circle dance. This can be done in $C_{n}^{n /2}$ C^{n/2}_n ways. Let's count the number of ways to arrange people within one circle dance. Fix the person who will be first, after which the remaining $n /2 - 1$ n / 2 - 1 people can be arranged in any order, namely $(n /2 - 1)!$ (n / 2 - 1)! ways. The number of ways to form two circle dances is:

C_{n}^{n /2} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2

C^{n/2}_n \cdot (n / 2 - 1)! \cdot (n / 2 - 1)!~/~2

The division by $2$ is necessary so that we do not distinguish between pairs of circle dances $(x, y)$ and $(y, x)$ . For example, for $n = 4$ n = 4, the divisions into circle dances $([1, 2], [3, 4])$ ([1, 2], [3, 4]) and $([3, 4], [1, 2])$ ([3, 4], [1, 2]) are considered the same.

Simplifying the given formula, we get the answer:

\frac{n !}{( n /2 )! \cdot ( n /2 )!} \cdot (n /2 - 1)! \cdot (n /2 - 1)! / 2 = \frac{1}{2} \cdot \frac{n !}{( n /2 ) \cdot ( n /2 )} = \frac{2 \cdot n !}{n \cdot n} = \frac{2 \cdot ( n - 1 )!}{n}

\frac{n!}{(n/2)! \cdot (n/2)!} \cdot (n / 2 - 1)! \cdot (n / 2 - 1)!~/~2 = \\ \frac{1}{2} \cdot \frac{n!}{(n/2) \cdot (n/2)} = \frac{2 \cdot n!}{n \cdot n} = \frac{2 \cdot (n - 1)!}{n}

Example

For example, for $n = 4$ n = 4 the number of ways is $3$ :

One round dance — $[1, 2]$ , another — $[3, 4]$ ;
One round dance — $[2, 4]$ , another — $[3, 1]$ ;
One round dance — $[4, 1]$ , another — $[3, 2]$ .

According to the formula for $n = 4$ n = 4, the answer is

\frac{2 \cdot ( 4 - 1 )!}{4} = \frac{12}{4} = 3

\frac{2 \cdot (4 - 1)!}{4} = \frac{12}{4} = 3

Let's construct all distinguishable circle dances for $n = 4$ n = 4. We place participant $1$ in the first position. In the remaining three positions, any permutation of the other three participants can be placed.

By rotating any of these arrangements in a circle, we can obtain indistinguishable circle dances. For example, the following arrangements are indistinguishable (consider the cyclic shifts of the last permutation):

[1, 4, 3, 2], [2, 1, 4, 3], [3, 2, 1, 4], [4, 3, 2, 1]

[1, 4, 3, 2],~[2, 1, 4, 3],~[3, 2, 1, 4],~[4, 3, 2, 1]

There are $4! = 24$ 4! = 24 circle dances with $4$ participants. However, the number of distinguishable circle dances for $n = 4$ n = 4 is $3! = 6$ 3! = 6.

Algorithm implementation

The fact function computes the factorial of the number $n$ .

long long fact(int n)
{
  long long res = 1;
  for (int i = 2; i <= n; i++)
    res *= i;
  return res;
}

C++

The main part of the program. Read the input value of $n$ .

scanf("%d", &n);

Compute and print the result.

res = 2 * fact(n - 1) / n;
printf("%lld\n", res);

Python implementation

The fact function computes the factorial of the number $n$ .

def fact(n):
  res = 1
  for i in range(2, n + 1):
    res *= i
  return res

The main part of the program. Read the input value of $n$ .

n = int(input())

Compute and print the result.

res = 2 * fact(n - 1) // n
print(res)