A361388 Number of orders of distances to vertices of n-dimensional cube.

1, 2, 8, 96, 5376, 1981440, 5722536960, 138430238607360

Offset: 0

Author

Pierre Abbat, Mar 10 2023

Keywords

• nonn
• hard
• more

Comments

Let C be an n-dimensional cube and p be a point in R^n such that the distances from p to the 2^n vertices of C are all different. List the vertices in order of their distance from p. The number of different orders of vertices is given by a(n).

Equality of any two distances defines a hyperplane in R^n, although different pairs of distances may define the same hyperplane. All these hyperplanes partition the space into cells, and the interior of each (n-dimensional) cell corresponds to a particular strong order of the differences. Hence, a(n) equals the number of cells in the partition of R^n by the hyperplanes. The given SageMath code implements this approach. - Max Alekseyev, Mar 10 2023

Computing the sequence is slow. The Sage program took 20 minutes to compute a(5) on Lucas Brown's box; the C++ program took 3.5 seconds to compute a(5) on Pierre Abbat's box, a 12-thread Ryzen. The C++ program took 6 hours to compute a(6). Neither of us has computed a(7) with the program; that's from A009997.

For n >= 4 the frequencies of the orders appear to vary widely.

Examples

			For n=3, a 3-dimensional cube has 8 corners, numbered 0 to 7. A point can be closest to any of the 8 corners. A point closest to 0 can have distances to corners 1, 2, and 4 in any of 6 orders. A point whose distances to corners 0, 1, 2, and 4 are in increasing order can be closer to 3 than to 4, or closer to 4 than to 3. So the total number of orders is 8*6*2=96.
		

Links

• Pierre Abbat, Cubeorders

Crossrefs

Cf. A009997.

Programs

PARI

A361388(n) = A009997(n)*n!<M. F. Hasler, Mar 10 2023

Sage

def a(n):
    x = polygens(QQ,n,'x')
    dist2 = [sum((xi - ti)^2 for xi,ti in zip(x,t)) for t in Tuples(range(2),n)]    # squared distances
    diffs = {p[0]-p[1] for p in Combinations(dist2,2)}     # set of pairwise differences of squared distances
    H = HyperplaneArrangements(QQ, tuple(map(str,x)))
    A = H([[[d.coefficient({xi:1}) for xi in x], d.constant_coefficient()] for d in diffs])
    return A.n_regions()
print( [a(n) for n in (1..4)] ) # Max Alekseyev, Mar 10 2023
(C++) // See Cubeorders link.

Formula

a(n) = 2^n*n!*A009997(n).