A358056 Given a row of n payphones (or phone booths), all initially unused, how many ways are there for n people to choose the payphones, assuming each always chooses one of the most distant payphones from those in use already? We consider here only the distance to the closest neighbor (in contrast to A095236).
1, 1, 2, 4, 8, 20, 48, 216, 576, 1392, 7200, 43200, 184320, 1065600, 4314240, 21611520, 150958080, 573834240, 2293401600, 32107622400, 236017152000, 2798762803200, 22493915136000, 189837914112000, 1165284436377600, 13260174468710400, 148874616963072000
Offset: 0
Keywords
Examples
a(5) = 20 because: (x = free, o = occupied).
We start with 5 free places:
xxxxx
Each position may be occupied in the next step:
xxxxx-+--oxxxx
|
+--xoxxx
|
+--xxoxx
|
+--xxxox
|
+--xxxxo
In the next step we do not have any choice for four out of five cases, but for the case where the central position was occupied first we have two possibilities for the next step:
xxxxx-+--oxxxx----oxxxo
|
+--xoxxx----xoxxo
|
+--xxoxx-+--oxoxx
| |
| ---xxoxo
|
+--xxxox----oxxox
|
+--xxxxo----oxxxo
In the next step we have only one choice in the cases where only the outer positions are occupied, we also have only one choice in the two central cases, and in all other cases each free position is a direct neighbor to an already occupied position and therefore equally possible.
xxxxx-+--oxxxx----oxxxo----oxoxo- two possibilities ( 2! )
|
+--xoxxx----xoxxo- six possibilities ( 3! )
|
+--xxoxx-+--oxoxx----oxoxo- two possibilities ( 2! )
| |
| ---xxoxo----oxoxo- two possibilities ( 2! )
|
+--xxxox----oxxox- six possibilities ( 3! )
|
+--xxxxo----oxxxo----oxoxo- two possibilities ( 2! )
Thus a(5) = 4*2! + 2*3! = 20.
Links
- Max Alekseyev, Table of n, a(n) for n = 0..100
- Max A. Alekseyev, Enumeration of Payphone Permutations, arXiv:2304.04324 [math.CO], 2023.
- Johann Beurich, Das Pissoir-Problem, YouTube video, 2022 (in German).
- Simon Wundling, About a combinatorial problem with n seats and n people, arXiv:2303.18175 [math.CO], 2023. See p. 15. (German)
Programs
-
MATLAB
function a = A358056( max_n ) a = 1; for n = 2:max_n k = 0; for m = 1:floor(n/2) % results are symmetrical calculate once *2 k = k + 2*calcinitialchoice(n,m); end if mod(n,2) == 1 % case for central phone k = k + calcinitialchoice(n,m+1); end a(n) = k; end end function k = calcinitialchoice(len,pos) k = 1; s = abs([1:len]-pos); % init vector with metrics while max(s) > 1 % run until each unused phone has one used neighbor j = find(s == max(s)); d = find(diff(j)==1); k = k*2^length(d); % special case two neighbors with same metric j(d) = []; l = length(j); k = k*factorial(l); % permutation over cases with highest metric % update metrics s = min([s;abs(repmat([1:len],l,1)-repmat(j',1,len))],[],1); end k = k*factorial(length(find(s == 1))); % permutation over last unused places end
Formula
For convenience will we use here some special symbols in this formula section. We will use operations from the tropical semiring:
(+) -> min(b, c), (*) -> b+c, (/) -> b-c, (^) -> b*c.
Let's define the tropical polynomials P(x, m, k, n):
For k = 0: P(x, m, 0, n) = (x(^)2(/)m (+) m)(/)x.
For k > 0: We find M = min_{x = 1..n} P(x,m,k-1,n), then we find the set x = {X_1, ..., X_n} such that P(x,m,k-1,n) = M. If our set contains any pairs such that X_b = 1 + X_c then eliminate X_b from our set. Now we are ready to define the polynomial for k > 0:
P(x, m, k, n) = 1(/)( 1(/)P(x, m, k-1, n) (+) x(/)(x(^)2(/)X_1 (+) X_1) (+) .. (+) x(/)(x(^)2(/)X_n (+) X_n) ).
StartCase(m, n) = EqM(P(x ,m, 0, n))!*2^EqdM(P(x, m, 0, n))*EqM(P(x, m, 1, n))!*2^EqdM(P(x, m, 1, n))* ... *EqM(P(x, m, kmax, n))!*2^EqdM(P(x, m, kmax, n)), kmax is the greatest k where P(x,m,k,n) may evaluate to nonzero values for x in the range 1 to n.
EqM counts all x in the range 1 to n where P(x, m, k, n) evaluates to the overall minimum in this range of x, but we exclude from our count all solutions x where x-1 is a solution too.
EqdM counts all x in the range 1 to n where P(x, m, k, n) evaluates to the overall minimum in this range of x and P(x+1, m, k, n) evaluates to the same value.
a(n) = Sum_{m = 1..n} StartCase(m, n), m is the selection of the first phone in usage.
StartCase(m+b, n) = StartCase(n-b, n), for b = 0..floor(n/2).
StartCase(n, 2*n) = (1/2)*StartCase(1, 2*n), for n > 2.
StartCase(n, 2*n+1) = 2*StartCase(1, 2*n), for n > 1.
a(n) = floor(n/2)! * Combinations if only floor((n+1)/2) phone users arrive.
a(n) = Sum_{i=1..n} (b(i,1) + b(n+1-i,1))! * Product_{j=2..n-1} 2^(d(i,j) + d(n+1-i,j)) * (b(i,j) + b(n+1-i,j))! (See A095236 for definition and calculation of b(p,k) and d(p,k)). - Simon Wundling, May 21 2023
Comments