A095240 -id:A095240 - cp's OEIS frontend

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

1, 2, 4, 8, 16, 36, 136, 216, 672, 2592, 10656, 35904, 167808, 426240, 1866240, 15287040, 35573760, 147640320, 1323970560, 3104317440, 64865525760, 352235520000, 1891946004480, 11505792614400

Offset: 1

Leroy Quet, Jul 03 2004

nonn

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.
Each person continues to use his payphone until all are in use.
The problem was originally stated in terms of urinals in a men's room.

			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.

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. A095239, A095240, A095923, A037256.

From Simon Wundling, Apr 12 2023: (Start)
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.
1) Calculation of b(p,k) for k >= 2 and all p (m = floor(log_2((p-1)/2k)) for p >= 5):
For p < k + 1: 0.
For p = k + 1: 1.
For k + 1 < p < 1 + 2k: 0.
For 1 + 2^m*2k <= p <= 1 + 2^m*(2k+1): 2^m.
For 1 + 2^m*(2k+1) < p <= 1 + 2^m*(2k+2): 1 + 2^m*(2k+2) - p.
For 1 + 2^m*(2k+2) < p <= 1 + 2^m*(4k-2): 0.
For 1 + 2^m*(4k-2) < p < 1 + 2^(m+1)*2k: p - 1 - 2^m*(4k-2).
2) Calculation of b(p,k) for k = 1 and all p (m = floor(log_2((p-1)/3)) for p >= 4):
For p = 1: 0.
For p = 2 or p = 3: 1.
For 1 + 2^m*3 <= p <= 1 + 2^m*4: 2^(m+1).
For 1 + 2^m*4 < p < 1 + 2^(m+1)*3: p - 1 - 2^(m+1).
3) Calculation of d(p,k) for k >= 2 and all p (m = floor(log_2((p-1)/2k)) for p >= 5):
For p < 1 + 2k: 0.
For 1 + 2^m*2k <= p <= 1 + 2^m*(2k+1): p - 1 - 2^m*2k.
For 1 + 2^m*(2k+1) < p <= 1 + 2^m*(2k+2): 1 + 2^m*(2k+2) - p.
For 1 + 2^m*(2k+2) < p < 1 + 2^(m+1)*2k: 0.
4) Calculation of d(p,k) for k = 1 and all p (m = floor(log_2((p-1)/3)) for p >= 4):
For p < 4: 0.
For 1 + 2^m*3 <= p <= 1 + 2^m*4: 1 + 2^m*4 - p.
For 1 + 2^m*4 < p < 1 + 2^(m+1)*3: p - 1 - 2^m*4.
Now you can give a formula for a(n):
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)

Edited by Don Reble, Jul 04 2004

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

Original entry on oeis.org

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

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

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.

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.

A166079 Given a row of n payphones, all initially unused, how many people can use the payphones, assuming (1) each always chooses one of the most distant payphones from those in use already, (2) the first person takes a phone at the end, and (3) no people use adjacent phones?

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 11, 12, 13, 14, 15, 16, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33

Offset: 1

Charles R Greathouse IV, Oct 06 2009

			From _Julian Zbigniew Kuryllowicz-Kazmierczak_, Feb 20 2024: (Start)
a(8)=4:
1st person takes payphone at the end:           .......1
2nd person takes most distant, the 1st:         2......1
3rd person takes 4th or 5th payphone:           2..3...1  or  2...3..1
4th person must take 6th or 3rd, respectively:  2..3.4.1  or  2.4.3..1
Now each payphone is in use or adjacent to one in use, so a(8)=4.
(End)

Julian Zbigniew Kuryllowicz-Kazmierczak, Table of n, a(n) for n = 1..20000
H.-K. Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications. Preprint, 2016.
H.-K. Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications. ACM Transactions on Algorithms, 13:4 (2017), #47. DOI:10.1145/3127585
Randall Munroe, Urinal protocol vulnerability
Simon Wundling, About a combinatorial problem with n seats and n people, arXiv:2303.18175 [math.CO], 2023. (German)

Cf. A095236, A095912, A095240.

a[n_]:= If[n<3,1,1 + 2^Floor[Log2[n-2] - 1] + Max[0, n - (3/2) * 2^Floor[Log2[n-2]]- 1]]; Array[a,78] (* Stefano Spezia, Oct 05 2024 *)

A000523(n)=my(t=floor(sizedigit(n)*3.32192809)-5); n>>=t; while(n>3,n>>=2;t+=2); if(n==1,t,t+1);
a(n)=my(t=1<<(A000523(n-2)-1)); max(t+1,n-t-t)

a(n) = if(n<3, return(1)); my(L=logint(n-2,2)-1); 1 + 2^L + max(0, n - 3*2^L - 1) \\ Charles R Greathouse IV, Jan 27 2016

a(n) = 1 + 2^floor(log_2(n-2) - 1) + max(0, n - (3/2) * 2^floor(log_2(n-2)) - 1).
A recurrence is: a(n) = a(m) + a(n-m+1) - 1, with a(1) = a(2) = 1 and a(3)=2, where m = ceiling(n/2). - John W. Layman, Feb 05 2011
a(n) = n - b(n,1) (see A095236 for definition and calculation of b(n,1)). - 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.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

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

Links

Crossrefs

Formula

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A166079 Given a row of n payphones, all initially unused, how many people can use the payphones, assuming (1) each always chooses one of the most distant payphones from those in use already, (2) the first person takes a phone at the end, and (3) no people use adjacent phones?

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

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