Men's-Room Permutations

Matthew Vandermast ghodges14 at
Sat Jun 26 21:33:18 CEST 2004

>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.

Let's further suppose that each man, knowing fully that all men arriving 
subsequently will also follow rules A and B, chooses his urinal so that 
after the next man arrives, the distances referred to in A and B will be the 
maximum possible.  Hence, for example, in a 6-urinal situation, man A must 
pick either urinal 1 or urinal 6.

For this sequence of "restricted men's room permutations," I get:  
1,2,2,4,4,16,...  This also may be in error.

Neither sequence turned up when I looked in the EIS.


More information about the SeqFan mailing list