cp's OEIS Frontend

A237749 The number of possible orderings of the real numbers xi*xj (i <= j), subject to the constraint that x1 > x2 > ... > xn > 0.

%I A237749 #72 Dec 25 2022 14:59:03
%S A237749 1,1,1,2,10,114,2608,107498,7325650,771505180
%N A237749 The number of possible orderings of the real numbers xi*xj (i <= j), subject to the constraint that x1 > x2 > ... > xn > 0.
%C A237749 Also, the number of possible orderings of sums xi + xj (i <= j), subject to the constraint that x1 > x2 > ... > xn. Cf. A231085.
%C A237749 Also, the minimum number of linear matrix inequalities needed to characterize the eigenvalues of quantum states that are "PPT from spectrum" when the local dimension is n (see Hildebrand link).
%C A237749 A003121 is an upper bound on this sequence.
%C A237749 Alternately, the number of combinatorially different Golomb rulers with n markings (Beck-Bogart-Pham). - _Charles R Greathouse IV_, Feb 18 2014
%C A237749 From _Jon E. Schoenfield_, Jul 03 2015: (Start)
%C A237749 The terms of this sequence would remain unchanged if it were required that each value of xi (and hence each pairwise product xi*xj) be an integer, and the addition of such a constraint suggests a systematic (albeit impractical for larger values of n) way to search through sets of n values of x to find a set that yields each of the a(n) possible orderings of the pairwise products: for x1 = n, n+1, n+2, ..., test every combination of n distinct positive integers of which x1 is the largest. Let M(n) be the smallest integer such that each of the a(n) possible orderings results from at least one combination of integers x1, x2, ..., xn where M(n) >= x1 > x2 > ... > xn; then values of M(n) for n = 2..6 are 2, 5, 13, 29, and 68, respectively.
%C A237749 For any given value of x1, the number of distinct orderings of pairwise products resulting from the binomial(x1-1, n-1) possible combinations of the remaining integers x2..xn provides a lower bound L(x1) for a(n). In general, L(x1) is not monotonically nondecreasing; e.g., for n=6, the (weak) lower bound on a(6)=2608 provided by L(33) is 2428, and L(34)=2423 is weaker still. However -- at least up through n=6 -- each of the a(n) possible orderings results from at least one combination where x1 is exactly M(n); e.g., at n=6, one of the 2608 orderings is missing among all binomial(67,6) = 99,795,696 combinations where x1 < 68, but all 2608 are present among the binomial(67,5) = 9,657,648 combinations where x1=68.
%C A237749 For all n up to at least 6, the number of orderings found among all combinations where x1 < M(n) is a(n)-1, and the one missing ordering of the pairwise products is the one in which xj*xn > (x(j+1))^2 for j=1..n-1. (End)
%C A237749 Number of paths towards synchronization in the transition diagram associated with the Laplacian system over the complete graph K_N, corresponding to ordered initial conditions x_1 < x_2 < ... < x_N. - _Andrea Arlette España_, Nov 14 2022
%H A237749 S. Arunachalam, N. Johnston, and V. Russo, <a href="http://arxiv.org/abs/1405.5853">Is separability from spectrum determined by the partial transpose?</a>, arXiv preprint arXiv:1405.5853 [quant-ph], 2014-2015.
%H A237749 Matthias Beck, Tristram Bogart, and Tu Pham, <a href="http://arxiv.org/abs/1110.6154">Enumeration of Golomb Rulers and Acyclic Orientations of Mixed Graphs</a>, arXiv:1110.6154 [math.CO], 2011, Section 5.
%H A237749 A. España, X. Leoncini, and E. Ugalde, <a href="https://arxiv.org/abs/2205.05948">Combinatorics of the paths towards synchronization</a>, arXiv:2205.05948 [math.DS], 2022.
%H A237749 R. Hildebrand, <a href="http://dx.doi.org/10.1103/PhysRevA.76.052325">Positive partial transpose from spectra</a>. Phys. Rev. A, 76 (5) (2007) 052325, <a href="http://arxiv.org/abs/quant-ph/0502170">[arXiv]</a>, arXiv:quant-ph/0502170, 2005.
%H A237749 Nathaniel Johnston, <a href="http://www.njohnston.ca/2014/02/counting-the-possible-orderings-of-pairwise-multiplication/">Counting the possible orderings of pairwise multiplication</a>
%H A237749 Nathaniel Johnston and Olivia MacLean, <a href="https://arxiv.org/abs/1807.06897">Pairwise Completely Positive Matrices and Conjugate Local Diagonal Unitary Invariant Quantum States</a>, arXiv:1807.06897 [quant-ph], 2018.
%H A237749 Antti Laaksonen, <a href="https://www.cs.helsinki.fi/u/ahslaaks/orderings.html">Counting Orderings of Sums</a>
%H A237749 Steven J. Miller and Carsten Peterson, <a href="https://arxiv.org/abs/1709.00520">A geometric perspective on the MSTD question</a>, arXiv:1709.00606 [math.CO], 2017.
%H A237749 Tu Pham, <a href="http://math.sfsu.edu/beck/teach/masters/tu.pdf">Enumeration of Golomb Rulers</a>, Master's Thesis (2011) Table 3.1.
%e A237749 a(3) = 2 because there are 2 possible orderings of the 6 products a1^2, a2^2, a3^2, a1*a2, a1*a3, a2*a3. Specifically, these orderings are:
%e A237749 a1^2 > a1a2 > a2^2 > a1a3 > a2a3 > a3^2 and
%e A237749 a1^2 > a1a2 > a1a3 > a2^2 > a2a3 > a3^2.
%Y A237749 Cf. A003121, A231074, A231085, A259762.
%K A237749 nonn,hard,more,nice
%O A237749 0,4
%A A237749 _Nathaniel Johnston_, Feb 12 2014
%E A237749 a(7) copied from Tu Pham by _Charles R Greathouse IV_, Feb 18 2014
%E A237749 a(8)-a(9) from _Antti Laaksonen_, Jan 10 2019