OFFSET
0,3
COMMENTS
More precisely: The first person chooses any payphone. Thereafter, we assign each unused place a distance metric. All places with one or two direct neighbors get the metric 1, all places where the closest neighbor is one place away get 2 and so forth. Each person chooses a place from the set of places with the greatest metric assigned.
Each person continues to use his payphone until all are in use.
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)
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
EXAMPLE
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.
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Scheuerle, Oct 28 2022
STATUS
approved