Men's-Room Permutations

[Leroy Quet]

[posted also to sci.math]

I was, seriously, inspired by a line of urinals in a men's-room
to come up with this sequence.

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.

(I thought about how exactly to formulate #2 a bit before
settling on this description. I use 'product' instead of 'sum'
so as to have the men tend to use urinals equidistant from the 2
flanking neighboring occupied urinals.)

And if there is a tie among acceptible urinals, the men choose of
their own free will.

Now, for example, if we have 6 urinals, we can have this permutation:

Man A can pick any of the 6 urinals. He picks 4.
Man B must pick urinal 1.
Man C must use urinal 6, since the others all are adjacent
to A or B.
Man D, using rule 1, can use any of the 3 remaining urinals.
Using rule 2, however, he can only chose between 2 or 3.
He picks 2.
Man E can chose between 3 or 5. He picks 5.
Man F must use 3.

So we have the permutation of {1,2,3,4,5,6}:
{4,1,6,2,5,3}.

I get, by hand (so I may have erred), the number of such permutations
(using rule 2), for m =1,2,3,...:
1, 2, 4, 8, 24, 36,...


Is this in the EIS? (Certainly, it would be called something else besides 
"Men's-Room Sequence"...)
:)

thanks,
Leroy Quet