What is the number of possible orders for this list of real numbers?

Question

Let $a_1,\ldots,a_n$ be some distinct positive real numbers. What is the number of orders of the set $S = \{a_1,\ldots,a_n, 1-a_1, \ldots, 1-a_n\}$?

For simplicity, assume that all $2n$ numbers in $S$ are distinct. If we had just arbitrary $2n$ numbers, then there were $(2n)!$ different orders. However, the numbers are related: for any fixed order of $\{a_1,\ldots,a_n\}$, the order of the complementary elements $\{1-a_1,\ldots,1-a_n\}$ is fixed. For example, if $a_1 < \cdots < a_n$, then $1 - a_n < \cdots < 1-a_1$. So the number of possible orders on $S$ is definitely less than $(2n)!$.

On the other hand, for any fixed order of $\{a_1,\ldots,a_n\}$, there are many different ways to "merge" the numbers $\{a_1,\ldots,a_n\}$ with their complements. For example, if $a_1 < a_2$, then we know that $1-a_2 < 1-a_1$, but it is possible that $a_1 < a_2 < 1-a_2 < 1-a_1$, or $a_1 < 1-a_1 < 1- a_2 < 1-a_1$, etc. So the answer is definitely more than $n!$.

Note that not all "merges" of the two sequences are possible. This is because $a_i < 1-a_i$ if and only if $a_i < 0.5$. Therefore, if $a_i < 1-a_i$ and $a_j < a_i$, then $a_j < 1-a_j$ too. So the order $a_1 < 1-a_1 < a_2 < 1-a_2$ is not possible.

How can I count the number of possible orders?

Answer 1

There are $n!\times 2^n$ possible orders. The $n!$ comes from ordering the $a_i$, and the $2^n$ comes from choosing, for each of the first $n$ positions in the order (corresponding to the values $<0.5$), whether that position is occupied by an $a_i$ or a $1-a_i$.