A095236 -id:A095236 - cp's OEIS frontend

A095239 Analog of A095236 when the phones are arranged in a circle.

1, 2, 6, 8, 40, 96, 168, 384, 1728, 15360, 50688, 221184, 299520, 1290240, 3628800, 30965760, 65802240, 743178240, 7060193280, 237817036800, 624269721600, 5231974809600, 28716407193600, 479439146188800

Offset: 1

Neil Fernandez, Jul 03 2004

nonn

Max Alekseyev, Table of n, a(n) for n = 1..100
Max A. Alekseyev, Enumeration of Payphone Permutations, arXiv:2304.04324 [math.CO], 2023.

Cf. A095236, A095240.

Corrected and extended by Don Reble, Jul 04 2004

A095240 Variant of A095236, where first two people choose payphones at the ends.

Original entry on oeis.org

1, 2, 2, 4, 4, 16, 32, 48, 96, 384, 3072, 9216, 36864, 46080, 184320, 483840, 3870720, 7741440, 82575360, 743178240, 23781703680, 59454259200, 475634073600, 2497078886400, 39953262182400, 22473709977600, 85614133248000

Offset: 1

Matthew Vandermast, Jul 03 2004

nonn

A non-monotonic sequence: a(25) > a(26).

a(n) > a(n+1) for n = 25, 33, 49, 57, 65, 81, 97, 98, 113, 129, 130, 131, 145, 161, 162, 177, 193, 194, 195, 197, ... - Max Alekseyev, Mar 14 2019

			For example, in a 6-pay-phone situation, person A must pick either pay-phone 1 or pay-phone 6.

Max Alekseyev, Table of n, a(n) for n = 1..100
Simon Wundling, About a combinatorial problem with n seats and n people, arXiv:2303.18175 [math.CO], 2023. (German)

Cf. A095236, A095239.

For n>1, a(n) = A095239(n-1)/(n-1) * 2. - Max Alekseyev, Mar 14 2019

For n>1, a(n) = 2 * Product_{j=1..n-1} 2^(d(n,j)) * (d(n,j))! * (b(n,j) - d(n,j))! (See A095236 for definition and calculation of b(n,j) and d(n,j)). - Simon Wundling, May 21 2023

Edited by Max Alekseyev, Mar 14 2019

A095912 Variant of the pay-phone sequence A095236. Here a slot at the end of the row is always preferred over a slot sandwiched immediately between two used slots.

Original entry on oeis.org

1, 2, 4, 6, 12, 28, 104, 152, 528, 2208, 9120, 23616, 130944, 278784, 1635840, 14181120, 32186880, 116674560, 1262039040, 2443714560, 58920099840, 161981890560, 1416311930880, 7700720025600, 120779469619200

Offset: 1

Jon Wild, Jul 13 2004

nonn

			Example: there are 5 payphones. First arrival may choose any; he selects phone #2. Next arrival must take the furthest away, #5. Next arrival must take either of #3 or #4 (since both have a neighbor on one side and a vacant slot on the other); he chooses #3. Next arrival must take #1 (because end slots are preferred over "sandwiched" slots), leaving #4 for the last arrival. The permutation (25314) is one of a(5)=10 that satisfy the requirements.

Max Alekseyev, Table of n, a(n) for n = 1..100
Max A. Alekseyev, Enumeration of Payphone Permutations, arXiv:2304.04324 [math.CO], 2023.
Simon Wundling, About a combinatorial problem with n seats and n people, arXiv:2303.18175 [math.CO], 2023. (German)

Cf. A095236, A095239, A095240, A095923.

Corrected and extended by Don Reble, Jul 15 2004

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

Original entry on oeis.org

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

Thomas Scheuerle, Oct 28 2022

nonn

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.

			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.

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)

Cf. A095236, A095698, A166079, A095912, A095239, A361294, A361295, A361296, A362192.

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

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

A095923 Analog of A095236 when definition of 'most distant from those in use' is 'with the highest geometric mean distance from those in use'.

Original entry on oeis.org

1, 2, 4, 6, 10, 12, 28, 20, 42

Offset: 1

Neil Fernandez, Jul 04 2004

Cf. A095236, A095239, A095240.

A037256 a(n) = n!Sum_{i=0..n-1} (n-i)(-2)^i/(i+1)!.

Original entry on oeis.org

0, 1, 2, 10, 48, 296, 2080, 16752, 151424, 1519744, 16766208, 201685760, 2627316736, 36847260672, 553551644672, 8868624615424, 150943592939520, 2719816264613888, 51724646086475776, 1035359388788391936, 21759010038674358272, 479027478333199482880

Offset: 0

N. J. A. Sloane

nonn

Arises from "Unfriendly Seating Arrangement" problem around a circular table.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Cristian F. Coletti, Sandro Gallo, Alejandro Roldán-Correa, and León A. Valencia, Fluctuations of the Occupation Density for a Parking Process, J. Statist. Phys. (2024) Vol. 191, No. 146. See p. 5.
Philippe Flajolet, A seating arrangement problem
Philippe Flajolet, A seating arrangement problem [Cached copy]
Dave Freedman and Larry Shepp, An unfriendly seating arrangement, Problem 62-3, SIAM Review, Vol. 6 (1964), 180-182.

Cf. A095236, A239888, A239889.

f:=n->n!*add((n-i)*(-2)^i/(i+1)!,i=0..n-1);
[seq(f(n),n=0..50)]; # N. J. A. Sloane, Mar 29 2014

m = 19; CoefficientList[ Series[(1 - Exp[-2x])*(1/((1-x)^2*2)), {x, 0, m}], x]*Range[0, m]!
(* Jean-François Alcover, Jun 28 2011 *)
Flatten[{0,Table[n!*Sum[Sum[(-1)^j*2^j/(j+1)!,{j,0,k}],{k,0,n-1}],{n,1,20}]}] (* Vaclav Kotesovec, Oct 27 2012 *)

x='x+O('x^66); concat([0],Vec(serlaplace((1-exp(-2*x))/(2*(1-x)^2)))) \\ Joerg Arndt, May 04 2013

E.g.f.: (1-exp(-2*x))*(1-x)^(-2)/2.
a(n) = 2*(n-1)*a(n-1) - (n-4)*(n-1)*a(n-2) - 2*(n-2)*(n-1)*a(n-3). - Vaclav Kotesovec, Oct 08 2012
a(n) ~ (1-1/e^2)*n!*n/2. - Vaclav Kotesovec, Oct 08 2012
a(n) = (-2)^n + (n+1)!/2 - (3+n)*Gamma(1+n,-2)/(2*e^2). - Benedict W. J. Irwin, Jul 06 2020

Entry revised by N. J. A. Sloane, Mar 29 2014

A361294 A variant of payphone permutations: given a circular booth with n payphones, one of which is already occupied, a(n) is the number ways for n-1 people to choose the payphones in order, where each person chooses an unoccupied payphone such that the closest occupied payphone is as distant as possible, and a payphone adjacent to a single occupied payphone is preferred over a payphone sandwiched between two occupied payphones.

Original entry on oeis.org

1, 1, 2, 2, 8, 16, 24, 48, 192, 1536, 4608, 18432, 23040, 92160, 241920, 1935360, 3870720, 41287680, 371589120, 11890851840, 29727129600, 237817036800, 1248539443200, 19976631091200, 11236854988800, 42807066624000, 176579149824000, 3390319676620800, 6886586843136000

Offset: 1

Max Alekseyev, Apr 10 2023

nonn

Provides the same counts as A095239, but up to a choice for the first payphone.

Max Alekseyev, Table of n, a(n) for n = 1..100
Max A. Alekseyev, Enumeration of Payphone Permutations, arXiv:2304.04324 [math.CO], 2023.

Cf. A095236, A095239, A095240, A095912, A358056, A361295, A361296, A362192.

a(n) = A095239(n) / n = A095240(n+1) / 2.

A361295 A variant of payphone permutations: given a row of n payphones, a(n) is the number ways for n people to choose the payphones in order, where each person chooses an unoccupied payphone such that the closest occupied payphone is as distant as possible, and among the available payphones adjacent to a single occupied payphone the most preferred are payphones at open ends.

Original entry on oeis.org

1, 2, 4, 6, 12, 40, 144, 384, 1008, 6816, 33600, 115200, 783360, 3024000, 16450560, 140636160, 558351360, 2262435840, 29599395840, 180278784000, 2124328550400, 13664957644800, 127667338444800, 852837440716800, 11377123378790400, 116737211695104000, 816490952589312000

Offset: 1

Max Alekseyev, Apr 08 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 1..100
Max A. Alekseyev, Enumeration of Payphone Permutations, arXiv:2304.04324 [math.CO], 2023.

Cf. A358056, A095236, A095239, A095912, A361294, A361296, A362192, A363785.

Definition corrected by Max Alekseyev, Jun 21 2023

A361296 A variant of payphone permutations: given a circular booth with n payphones, a(n) is the number ways for n people to choose the payphones in order, where each person chooses an unoccupied payphone such that the closest occupied payphone is as distant as possible.

Original entry on oeis.org

1, 2, 6, 8, 60, 144, 336, 384, 8640, 57600, 221760, 967680, 4193280, 9031680, 14515200, 30965760, 2368880640, 50164531200, 582465945600, 7357464576000, 50214695731200, 245494068019200, 1443672502272000, 24103053950976000, 200858782924800000, 835572536967168000

Offset: 1

Max Alekseyev, Apr 08 2023

nonn

Max Alekseyev, Table of n, a(n) for n = 1..100
Max A. Alekseyev, Enumeration of Payphone Permutations, arXiv:2304.04324 [math.CO], 2023.

Cf. A095236, A095239, A095912, A358056, A361294, A361295, A362192.

A362192 A variant of payphone permutations: given a circular booth with n payphones, one of which is already occupied, a(n) is the number ways for n-1 people to choose the payphones in order, where each person chooses an unoccupied payphone such that the closest occupied payphone is as distant as possible.

Original entry on oeis.org

1, 1, 2, 2, 12, 24, 48, 48, 960, 5760, 20160, 80640, 322560, 645120, 967680, 1935360, 139345920, 2786918400, 30656102400, 367873228800, 2391175987200, 11158821273600, 62768369664000, 1004293914624000, 8034351316992000, 32137405267968000, 96412215803904000, 385648863215616000, 964122158039040000, 1928244316078080000

Offset: 1

Max Alekseyev, Apr 10 2023

nonn

Provides the same counts as A361296, but up to a choice for the first payphone.

Max Alekseyev, Table of n, a(n) for n = 1..100
Max A. Alekseyev, Enumeration of Payphone Permutations, arXiv:2304.04324 [math.CO], 2023.

Cf. A095236, A095239, A095240, A095912, A358056, A361294, A361295, A361296.

a(n) = A361296(n) / n.

cp's OEIS Frontend

A095239 Analog of A095236 when the phones are arranged in a circle.

Views

Author

Keywords

Links

Crossrefs

Extensions

A095240 Variant of A095236, where first two people choose payphones at the ends.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A095912 Variant of the pay-phone sequence A095236. Here a slot at the end of the row is always preferred over a slot sandwiched immediately between two used slots.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Formula

A095923 Analog of A095236 when definition of 'most distant from those in use' is 'with the highest geometric mean distance from those in use'.

Views

Author

Keywords

Crossrefs

A037256 a(n) = n!*Sum_{i=0..n-1} (n-i)*(-2)^i/(i+1)!.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Views

Author

Keywords

Links

Crossrefs

Extensions

A361296 A variant of payphone permutations: given a circular booth with n payphones, a(n) is the number ways for n people to choose the payphones in order, where each person chooses an unoccupied payphone such that the closest occupied payphone is as distant as possible.

Views

Author

Keywords

Links

Crossrefs

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A037256 a(n) = n!Sum_{i=0..n-1} (n-i)(-2)^i/(i+1)!.