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

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?

• Why are the orders of the complementary elements fixed? Commented Jul 28 at 8:39
• You are going to have to clearly indicate what the rules are for merging the sequences. Commented Jul 28 at 8:42
• The lowest $n/2$ of the $a_i$ and the lowest $n/2$ of the $1-a_i$ may be in any order because they are independent, so that gives another factor of $n\choose n/2$ Commented Jul 28 at 9:00
• @QthePlatypus I edited the question to clarify that. Commented Jul 28 at 9:07
• The intended question is: how many permutations of $\{1,\dots,2n\}$ can arise from sorting the elements of a tuple of the form $(a_1,\dots,a_n,1-a_1,\dots,1-a_n)$ from smallest to largest?
– Karl
Commented Jul 28 at 18:49

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$$.