Men's-Room Permutations

[Edwin Clark]

Neil Fernandez wrote:

>Leroy Quet wrote: 
> 
> For an arrangement in a circle, I get:
> 
> 1,2,6,8,60,72,...
> 
> Not sure what happens on an Archimedean spiral with equation r = theta,
> with urinals spaced at multiples of constant angle phi.
> 


One could generalize further. Let (X_n,d) be any sequence of 
metric spaces.  For example X_n could be an n-cube and
d could be the Hamming metric. Or X_n could be an n-cycle
and d could be the path metric.

Determine the number a(n) of labelings of the elements of X_n 
with the integers 1,...,|X_n| such that the minimum distance between the 
vertices labeled 1,...,i is as large as possible for all i. Clearly
this is a graph theoretic invariant. Perhaps it has been studied? 

Also stated in this way it has a code-theoretic flavor. Could it have 
arisen in coding theory? X_n need not have n vertices, it could be for 
example an n-cube or n x n grid graph.

--Edwin