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:
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)\) |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 10 |
| 4 | 114 |
| 5 | 2608 |
| 6 | 107498 |
| 7 | 7325650 |
| 8 | 771505180 |
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