|
%I #34 May 27 2023 02:13:05
%S 1,2,4,8,16,36,136,216,672,2592,10656,35904,167808,426240,1866240,
%T 15287040,35573760,147640320,1323970560,3104317440,64865525760,
%U 352235520000,1891946004480,11505792614400
%N Given a row of n payphones (or phone booths), all initially unused, sequence gives number of ways for n people to choose the payphones assuming each always chooses one of the most distant payphones from those in use already.
%C More precisely: The first person chooses any payphone. Thereafter, each person chooses the middle of a largest span of unused phones, but a span of length L at the end of the row is taken to have length 2L-1 and its "middle" is the outermost phone. If a span has even length, either middle may be chosen.
%C Each person continues to use his payphone until all are in use.
%C The problem was originally stated in terms of urinals in a men's room.
%H Max Alekseyev, <a href="/A095236/b095236.txt">Table of n, a(n) for n = 1..100</a>
%H Max A. Alekseyev, <a href="https://arxiv.org/abs/2304.04324">Enumeration of Payphone Permutations</a>, arXiv:2304.04324 [math.CO], 2023.
%H Simon Wundling, <a href="https://arxiv.org/abs/2303.18175">About a combinatorial problem with n seats and n people</a>, arXiv:2303.18175 [math.CO], 2023. (German)
%F From _Simon Wundling_, Apr 12 2023: (Start)
%F Let adjacent payphones have the distance 1. We now look at the situation with p payphones and the first person choosing the payphone at the left end. Then let b(p,k) be the number of people who choose a payphone with distance k and let d(p,k) be the number of different sets of two adjacent payphones which both have at one time the distance k.
%F 1) Calculation of b(p,k) for k >= 2 and all p (m = floor(log_2((p-1)/2k)) for p >= 5):
%F For p < k + 1: 0.
%F For p = k + 1: 1.
%F For k + 1 < p < 1 + 2k: 0.
%F For 1 + 2^m*2k <= p <= 1 + 2^m*(2k+1): 2^m.
%F For 1 + 2^m*(2k+1) < p <= 1 + 2^m*(2k+2): 1 + 2^m*(2k+2) - p.
%F For 1 + 2^m*(2k+2) < p <= 1 + 2^m*(4k-2): 0.
%F For 1 + 2^m*(4k-2) < p < 1 + 2^(m+1)*2k: p - 1 - 2^m*(4k-2).
%F 2) Calculation of b(p,k) for k = 1 and all p (m = floor(log_2((p-1)/3)) for p >= 4):
%F For p = 1: 0.
%F For p = 2 or p = 3: 1.
%F For 1 + 2^m*3 <= p <= 1 + 2^m*4: 2^(m+1).
%F For 1 + 2^m*4 < p < 1 + 2^(m+1)*3: p - 1 - 2^(m+1).
%F 3) Calculation of d(p,k) for k >= 2 and all p (m = floor(log_2((p-1)/2k)) for p >= 5):
%F For p < 1 + 2k: 0.
%F For 1 + 2^m*2k <= p <= 1 + 2^m*(2k+1): p - 1 - 2^m*2k.
%F For 1 + 2^m*(2k+1) < p <= 1 + 2^m*(2k+2): 1 + 2^m*(2k+2) - p.
%F For 1 + 2^m*(2k+2) < p < 1 + 2^(m+1)*2k: 0.
%F 4) Calculation of d(p,k) for k = 1 and all p (m = floor(log_2((p-1)/3)) for p >= 4):
%F For p < 4: 0.
%F For 1 + 2^m*3 <= p <= 1 + 2^m*4: 1 + 2^m*4 - p.
%F For 1 + 2^m*4 < p < 1 + 2^(m+1)*3: p - 1 - 2^m*4.
%F Now you can give a formula for a(n):
%F a(n) = Sum_{i=1..n} Product_{j=1..n-1} 2^(d(i,j) + d(n+1-i,j)) * (d(i,j) + d(n+1-i,j))! * (b(i,j) + b(n+1-i,j) - d(i,j) - d(n+1-i,j))!. (End)
%e From 6 payphones: A may pick any of the 6; he picks #4. B must pick #1. C must pick #6, since the others all are adjacent to A or B. D may pick #2 or #3; he picks #2. E may pick #3 or #5; he picks #5. F must pick #3. That gives the permutation (4,1,6,2,5,3), one of 36 possible permutations.
%Y Cf. A095239, A095240, A095923, A037256.
%K nonn
%O 1,2
%A _Leroy Quet_, Jul 03 2004
%E Edited by _Don Reble_, Jul 04 2004
| 