Let be an integer. Determine, as a function of , the number of circular arrangements of the numbers such that
where the indices and are to be interpreted modulo . Note that any rotation of a circular arrangement is considered to be the same circular arrangement, i.e., the circular arrangements and are considered to be the same.
Solutions — 2
Solution 1
Solution 1.
First consider the case when is odd. It is easy to see that
for another circular arrangement . So we can consider
instead. Now, the numbers and must appear somewhere on the circle. Suppose that the numbers between and clockwise are and the numbers between and anticlockwise are , where . Then
and
Adding these two inequalities yields
(for later in the proof, we note that equality occurs if and only if the sequences and are in increasing order). Thus we can never have for odd values of .
Next consider the case when is even. Let the set of numbers appearing in the odd-indexed positions be and let the set of numbers appearing in the even-indexed positions be . Here .
Denote by and the minimum and maximum of , and denote by and the minimum and maximum of . Then, using a similar argument to the case of odd above, but replacing the numbers and by and , we have
and doing the same but this time for the numbers and , we have
Adding these two inequalities yields
It is easy to see that for some and for some . So
To obtain equality, without loss of generality the numbers in odd-indexed positions must be placed in increasing order from to (both clockwise and anticlockwise). We count the arrangements as follows. First we place and somewhere on a circle. Then, we choose any subset of to be the values placed in increasing order clockwise from to . After this, there is only one way to place the remaining values from in increasing order anticlockwise from to . We now have a circular arrangement of the odd-indexed numbers on the circle. This can be done in ways. Second, we follow the same procedure for the even-indexed numbers on the circle (this can also be done in ways). Finally, the (odd) circular offset between the values and can be chosen in ways, giving a total of circular arrangements.
Thus the answer to the question is if is odd, and if is even.
Solution 2
Solution 2.
For all integers , we let . We define a new circular arrangement by setting , , and more generally, . If is odd, say , we find that , , etc. and we obtain a new circular arrangement of the numbers . If is even, say , we find , and the circular arrangement (we may call it the a-cycle) contains only half of the numbers . We then define a second circular arrangement (the b-cycle) by for . The circular arrangement contains those numbers from which are not in the a-cycle. With this new notation, we find that
To facilitate the counting required for the problem, we prove the following lemma.
Lemma. If and is a circular arrangement of distinct positive integers, where we let for , then
with equality only possible when consists of consecutive numbers (not necessarily in their natural order) and the largest two numbers are direct neighbours in the cycle.
Proof. We use induction on . If , we have
with equality only if . If , after 'rotating' the cycle we can assume that is the largest number in the cycle. Let the cycle be obtained from the cycle by removing , i.e. for but . We then have
which implies, because and ,
We have as well as , and by inductive hypothesis, , hence with equality only if and either or is equal to . In particular, in case of equality, the cycle consists of consecutive numbers and its largest number is . The lemma follows.
A direct consequence of the Lemma is that for odd we have
and so for odd , where is the number of circular arrangements that satisfy the conditions of the problem.
Let now be even. From the Lemma we now obtain . To achieve equality, both cycles, and , need to consist of consecutive numbers. One of these two cycles contains the numbers , the other the numbers .
The Lemma allows us to count the number of cycles that consist of the numbers (or any other consecutive numbers) for which . Let be this number. Then as there is only one cycle of length two. For , the lemma implies that after removing the number from , we are left with a cycle that consists of the numbers and which satisfies . Moreover, there are exactly two cycles which lead to the same , namely the two that are obtained by fitting in immediately before or after in . Hence for and it follows by induction that .
To determine for even, we may assume that so that we don't have to deal with rotational symmetry any more. From the above it then follows that the a-cycle consists of and the b-cycle of . As seen above, there are possibilities for the a-cycle. There are the same number of possible b-cycles, but when we merge the two to the full cycle , a rotated b-cycle gives a different result. Therefore, we need to multiply by , which is the number of possibilities to choose which element of the b-cycle will become . This gives
Thus the answer to the question is if is odd, and if is even.