Men's-Room Permutations
Matthew Vandermast
ghodges14 at msn.com
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.
Matt
More information about the SeqFan
mailing list