Laudator Temporis Acti

Leroy Quet posted the following query to the seqfan (fans of integer sequences) mailing list and also to sci.math:

Assume that the men in a men's-room wanting to relieve themselves are all rather modest about using the urinals.

They will, when other men are already using some of the urinals, each tend to use the urinal farthest from any other occupied urinal (or use one of these most-lonely urinals if there is a tie for loneliest urinal).

So, assuming we have a row of m urinals, which begin all unoccupied, how many ways are there for the men to line up at the urinals, assuming they WILL always follow the rule of using (one of) the most distant urinal(s)?

For simplicity, assume that each of the m men continues to occupy his urinal until all m urinals are occupied.

Now, mathematically, what we want is a permutation based on one of the 2 following rules:

1) Each urinal is chosen so that its closest occupied neighbor is at maximum distance.

2) Each urinal is chosen so that the product of (the distance to its left closest neighbor) and (the distance to its right closest neighbor) {or (the distance to its closest neighbor)^2
if the urinal is on the end of the row} is maximized.

Quet's post has generated much lively interest and discussion, and I'm glad that this fascinating topic is at last receiving from mathematicians the attention it deserves. Every man knows immediately what Quet is talking about. The behavior he describes is an unwritten law in men's rooms, rarely if ever violated.

Update: A correspondent draws my attention to an interactive game that tests your practical knowledge of this law. Thanks, Raymond.