A037256 -id:A037256 - 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

A088127 E.g.f. exp(-x)*cosh(x)/(1-x)^2.

Original entry on oeis.org

1, 1, 4, 14, 72, 424, 2960, 23568, 211456, 2109056, 23150592, 277315840, 3599704064, 50331030528, 754122723328, 12054165272576, 204743835156480, 3682557441114112, 69920454322356224, 1397542619388248064, 29331932133035081728, 644973249444408197120

Offset: 0

Paul Barry, Sep 19 2003

A088127(n)+A037256(n)=(n+1)! Binomial transform is A088128.

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Table[n!*SeriesCoefficient[E^(-x)*Cosh[x]/(1-x)^2,{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 14 2012 *)
With[{nn=30},CoefficientList[Series[Exp[-x] Cosh[x]/(1-x)^2,{x,0,nn}],x] Range[0,nn]!] (* Harvey P. Dale, Mar 24 2020 *)

x='x+O('x^66); Vec(serlaplace(exp(-x)*cosh(x)/(1-x)^2)) \\ Joerg Arndt, May 10 2013

Recurrence: 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 14 2012

a(n) ~ n!*n*(1+1/e^2)/2. - Vaclav Kotesovec, Oct 14 2012

A239888 From second moments of unfriendly seating arrangement problem around a circular table with n seats.

Original entry on oeis.org

0, 0, 0, 8, 48, 464, 4000, 40032, 424704, 4927232, 61553664, 827632640, 11914946560, 183014995968, 2988450177024, 51709354532864, 945292051415040, 18207952013164544, 368620245155184640, 7825923453008609280, 173870718374040305664, 4034781267785209610240, 97622280693411826630656, 2458689656873584082026496, 64361542182239808476151808

Offset: 0

N. J. A. Sloane, Mar 29 2014

nonn

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. A037256, A095236, A239889.

g:=proc(n) local k; option remember;
if n<=0 then 1 elif n=1 then u else
expand(u/n*convert([seq(g(k-2)*g(n-k-1),k=1..n)],`+`));
fi
end:
l2:=subs(u=1,diff([seq(g(j),j=0..25)],u,u));
[seq(l2[i]*(i-1)!,i=1..26)];

g[n_] := g[n] = Switch[n, -1|0, 1, 1, u, _, u/n Sum[g[k-2] g[n-k-1], {k, 1, n}]];
D[Table[g[j] j!, {j, 0, 25}], {u, 2}] /. u -> 1 (* Jean-François Alcover, Jul 29 2018, from Maple *)

A239889 From unfriendly seating arrangement problem for fat men at a circular table with n seats.

Original entry on oeis.org

0, 1, 2, 6, 36, 216, 1440, 11520, 103824, 1032192, 11311488, 135432000, 1756751040, 24546246912, 367583014656, 5872797874944, 99709066195200, 1792707696046080, 34026520304848896, 679901687704470528, 14265989230889290752, 313612842057647616000, 7208078043054064619520, 172883491724308733964288, 4319548522560325245210624

Offset: 0

N. J. A. Sloane, Mar 29 2014

nonn

Philippe Flajolet, A seating arrangement problem. See page 11.
Philippe Flajolet, A seating arrangement problem [Cached copy]. See page 11.
Dave Freedman and Larry Shepp, An unfriendly seating arrangement, Problem 62-3, SIAM Review, Vol. 6 (1964), 180-182.

Cf. A037256, A239888, A095236.

gb:=proc(n,b) local k; option remember;
if n<=0 then 1 elif n<=b then u else expand(u/n*convert([seq(gb(k-b-1,b)*gb(n-k-b,b),k=1..n)],`+`))
fi
end:
l3:=subs(u=1,diff([seq(gb(j,2),j=0..25)],u));
[seq(l3[i]*(i-1)!,i=1..26)];

g[n_, b_] := g[n, b] = Which[n <= 0, 1, n <= b, u, True, u/n Sum[g[k-b-1, b] g[n-k-b, b], {k, 1, n}]];
D[Table[g[j, 2] j!, {j, 0, 25}], u] /. u -> 1 (* Jean-François Alcover, Jul 29 2018, from Maple *)

A088129 Expansion of e.g.f. sinh(x)/(1-x)^2.

Original entry on oeis.org

0, 1, 4, 19, 104, 661, 4812, 39607, 364240, 3704617, 41310740, 501328411, 6578864184, 92843236669, 1402257345244, 22570640656831, 385718738160032, 6975222838783057, 133078088319220260, 2671441145266564387, 56287972249358876680, 1242089553461115778021

Offset: 0

Paul Barry, Sep 19 2003

Binomial transform of A037256.

Cf. A001339, A037256, A088128.

nmax=21; CoefficientList[Series[Sinh[x]/(1-x)^2, {x,0,nmax}], x]Range[0,nmax]! (* Stefano Spezia, Jan 15 2024 *)

a(n) = A001339(n) - A088128(n).

a(n) = Sum_{k=0..floor((n-1)/2)} binomial(n,2*k+1) * (n-2*k)!. - Ilya Gutkovskiy, Apr 10 2022

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

A088127 E.g.f. exp(-x)*cosh(x)/(1-x)^2.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

Formula

A239888 From second moments of unfriendly seating arrangement problem around a circular table with n seats.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A239889 From unfriendly seating arrangement problem for fat men at a circular table with n seats.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A088129 Expansion of e.g.f. sinh(x)/(1-x)^2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula