# Counting Orderings of Sums

Author: Antti Laaksonen

Let $$x_1,x_2,\dots,x_n$$ be a sequence of positive numbers and $$S(a,b) = \sum_{i=a}^b x_i$$ for $$1 \le a \le b \le n$$. How many possible orderings are there such that each $$S(a,b)$$ is distinct?

If $$n=1$$, the only ordering is $$S(1,1)$$.

If $$n=2$$, there are two possible orderings: $$S(1,1) < S(2,2) < S(1,2)$$ and $$S(2,2) < S(1,1) < S(1,2)$$.

If $$n=3$$, there are ten possible orderings:

• $$S(1,1) < S(2,2) < S(3,3) < S(1,2) < S(2,3) < S(1,3)$$
• $$S(1,1) < S(3,3) < S(2,2) < S(1,2) < S(2,3) < S(1,3)$$
• $$S(2,2) < S(1,1) < S(3,3) < S(1,2) < S(2,3) < S(1,3)$$
• $$S(2,2) < S(3,3) < S(1,1) < S(2,3) < S(1,2) < S(1,3)$$
• $$S(3,3) < S(1,1) < S(2,2) < S(2,3) < S(1,2) < S(1,3)$$
• $$S(3,3) < S(2,2) < S(1,1) < S(2,3) < S(1,2) < S(1,3)$$
• $$S(1,1) < S(2,2) < S(1,2) < S(3,3) < S(2,3) < S(1,3)$$
• $$S(2,2) < S(1,1) < S(1,2) < S(3,3) < S(2,3) < S(1,3)$$
• $$S(2,2) < S(3,3) < S(2,3) < S(1,1) < S(1,2) < S(1,3)$$
• $$S(3,3) < S(2,2) < S(2,3) < S(1,1) < S(1,2) < S(1,3)$$

Let $$N(n)$$ denote the number of orderings for a sequence of $$n$$ numbers. The following table contains the first values of the function:

$$n$$$$N(n)$$
11
22
310
4114
52608
6107498
77325650
8771505180

This is the sequence A237749 in the OEIS. The values for $$n \le 6$$ were calculated by Tu Pham in the context of Golomb rulers. We calculated the values for $$n=7$$ and $$n=8$$ as follows:

Consider a graph whose each node corresponds to a value $$S(a,b)$$ and there are directed edges from $$S(a,b)$$ to $$S(a+1,b)$$ and $$S(a,b-1)$$ whenever $$a < b$$. We calculate the number of valid orderings using a backtracking algorithm that goes through topological sorts in that graph. To prune the search and make sure that we only count valid orderings, we use linear programming. We maintain a set of inequalities that must hold, and always add new inequalities when there are more than one node that we could choose. More precisely, when the chosen node is $$X$$ and the other possible nodes are $$A_1,A_2,\dots,A_k$$, we add the inequalities $$A_1+d \le X, A_2+d \le X, \dots, A_k+d \le X$$. Then, on each step, we use the simplex algorithm to check if the set of inequalities is feasible, and only continue the search in that case.

Page created: 9 Jan 2019