The numbers are randomly arranged in a circle. Let be the probability that for every positive integer , there exists an integer such that there is at most one number between and in the circle. If can be expressed as for relatively prime positive integers and , compute .
Solution
Let and call two numbers close if there is at most one number between them and an circular permutation focused if only is greater than all numbers close to it. Let be the number of focused circular permutations of . If , then there are 2 cases: is either one or two positions from . If is one position from , it is either on its left or right. In this case, one can check a permutation is focused if and only if removing yields a focused permutation, so there are permutations in this case. If is two positions from , there are choices for , the element that lies between and . One can show that this permutation is focused if and only if removing both and and relabeling the numbers yields a focused permutation, so there are permutations in this case. Thus, we have . If we let ! the probability that a random circular permutation is focused, then this becomes Since , we may now use this recursion to calculate