A095236 -id:A095236 - cp's OEIS frontend

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?

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

A192008 Modified linear phone booth sequence: number of ways to occupy n phone booths in a row, one by one, each time picking a phone booth adjacent to the smallest number of previously occupied phone booths.

Original entry on oeis.org

1, 2, 4, 8, 32, 96, 456, 2016, 11232, 61632, 419328, 2695680, 21358080, 161049600, 1433894400, 12429158400, 123511910400, 1202903654400, 13229501644800, 143113833676800, 1722282128179200, 20516624400384000, 268083853148160000, 3485314242772992000, 49167975665958912000

Offset: 1

Jens Voß, Jun 21 2011

nonn

			For n=4, the A192008(n) = 8 ways of picking the phones are (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2), (2, 4, 1, 3), (3, 1, 4, 2), (4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3).

Max Alekseyev, Table of n, a(n) for n = 1..100
Project Euler, Comfortable distance (Problem 364).
Jens Voß, Java class for generating A192008

Cf. A095236, A192009, A276657.

{ A192008(n) = my(r,k); r=0; for(v=0,2, forstep(m=lift(Mod(n-1-v,3)/2),(n-1-v)\2,3, k=(n-1-v-2*m)\3; r+=(m+k+1)!*binomial(m+k,m)*2^k*(k+v)!*(m+k)!*(1+(v==1)););); r; } \\ Max Alekseyev, Sep 11 2016

a(n) = Sum (m+k+1)!*binomial(m+k,m)*2^k*(k+v1+v2)!*(m+k)!, where the sum is taken over v1,v2 each from 0 to 1, and over nonnegative m,k such that 2*m+3*k = n-1-v1-v2. - Max Alekseyev, Sep 11 2016

More terms from João Batista Souza de Oliveira, Jul 09 2014

Terms a(20) onward from Max Alekseyev, Sep 11 2016

A192009 Modified cyclic phone booth sequence: number of ways to occupy n labeled phone booths in a circle one by one, each time picking a phone booth adjacent to the smallest number of previously occupied phone booths.

Original entry on oeis.org

1, 2, 6, 8, 40, 168, 504, 3456, 15552, 97920, 620928, 4465152, 31449600, 273369600, 2172096000, 20968243200, 192753561600, 2032260710400, 20942298316800, 243270107136000, 2758764950323200, 34958441123020800, 434690126954496000, 5946571752210432000, 80503989505228800000

Offset: 1

Jens Voß, Jun 21 2011

nonn

			For n=4, the A192009(n) = 6 ways of picking the phone booths are (1, 3, 2, 4), (1, 3, 4, 2), (2, 4, 1, 3), (2, 4, 3, 1), (3, 1, 2, 4), (3, 1, 4, 2), (4, 2, 1, 3), (4, 2, 3, 1).

Max Alekseyev, Table of n, a(n) for n = 1..100

Cf. A095236, A192008, A192009, A276657.

A192009 := proc(n)
    local a,k,m;
    if n = 1 then
        return 1;
    end if;
    a := 0 ;
    for k from 0 to n/3 do
        m := (n-3*k)/2 ;
        if type (m,'integer') then
            a := a+(m+k-1)!*binomial(m+k,m)*2^k*k!*(m+k)! ;
        end if;
    end do:
    a*n ;
end proc:
seq(A192009(n),n=1..20) ; # R. J. Mathar, Sep 17 2016

r[n_] := {ToRules[Reduce[m >= 0 && k >= 0 && 2m+3k == n, {m, k}, Integers] ]}; f[{m_, k_}] := (m+k-1)!*Binomial[m + k, m]*2^k*k!*(m+k)!; a[n_] := n*Total[f /@ ({m, k} /. r[n])]; a[1] = 1; Array[a, 25] (* Jean-François Alcover, Sep 13 2016, after Max Alekseyev *)

{ A192009(n) = my(r,k); if(n==1,return(1)); r=0; forstep(m=lift(Mod(n,3)/2),n\2,3, k=(n-2*m)\3; r+=(m+k-1)!*binomial(m+k,m)*2^k*k!*(m+k)!); r*n; } \\ Max Alekseyev, Sep 11 2016

For n > 1, a(n) = n * Sum (m+k-1)!*binomial(m+k,m)*2^k*k!*(m+k)!, where the sum is taken over nonnegative m,k such that 2*m+3*k = n. - Max Alekseyev, Sep 11 2016

a(n) = n * A276657(n). - Max Alekseyev, Sep 11 2016

Terms a(15) onward from Max Alekseyev, Sep 11 2016

A276657 Number of ways to occupy n unlabeled phone booths in a circle one by one, each time picking a phone booth adjacent to the smallest number of previously occupied phone booths.

Original entry on oeis.org

1, 1, 2, 2, 8, 28, 72, 432, 1728, 9792, 56448, 372096, 2419200, 19526400, 144806400, 1310515200, 11338444800, 112903372800, 1102226227200, 12163505356800, 131369759539200, 1589020051046400, 18899570737152000, 247773823008768000, 3220159580209152000, 45535430530695168000

Offset: 1

Max Alekseyev, Sep 11 2016

nonn

Each phone booth has two adjacent ones, each of which may or may not be occupied. So, available phone booths may have from 0 to 2 adjacent ones that are occupied. Each time we pick a phone booth with the smallest number of those (0 is top priority, then 1, then 2).

Max Alekseyev, Table of n, a(n) for n = 1..100

Cf. A192009 (labeled case).

Cf. A095236, A192008.

r[n_] := {ToRules[Reduce[m >= 0 && k >= 0 && 2 m + 3 k == n, {m, k}, Integers]]}; f[{m_, k_}] := (m + k - 1)!*Binomial[m + k, m]*2^k*k!*(m + k)!; a[n_] := Total[f /@ ({m, k} /. r[n])]; a[1] = 1; Array[a, 26] (* Jean-François Alcover, Sep 13 2016 *)

{ A276657(n) = my(r,k); if(n==1, return(1)); r=0; forstep(m=lift(Mod(n, 3)/2), n\2, 3, k=(n-2*m)\3; r+=(m+k-1)!*binomial(m+k, m)*2^k*k!*(m+k)!); r; }

a(n) = A192009(n) / n.

For n > 1, a(n) = Sum (m+k-1)!*binomial(m+k,m)*2^k*k!*(m+k)!, where the sum is taken over nonnegative m,k such that 2*m+3*k = n.

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

A363785 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 a payphone adjacent to a single occupied payphone is preferred over a payphone sandwiched between two occupied payphones.

Original entry on oeis.org

1, 2, 4, 6, 16, 28, 120, 264, 576, 2784, 11040, 37440, 204672, 679680, 2511360, 15655680, 52945920, 232796160, 2456801280, 11867627520, 97875025920, 576737280000, 4012233523200, 20013325516800, 215802239385600, 1778700504268800, 9687506721177600, 88613303353344000, 448250987623219200

Offset: 1

Max Alekseyev, Jun 21 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, A361295, A361296, A362192, A363785.

A373182 Number of ways that people can sit in n linearly arranged seats such that there are one or two empty seats between any two persons, zero or one empty seats at the start and end, and at least one person gets seated.

Original entry on oeis.org

1, 2, 3, 6, 12, 26, 60, 144, 366, 960, 2640, 7464, 21960, 66240, 206760, 660240, 2172240, 7298640, 25179840, 88583040, 319097520, 1170650880, 4387582080, 16728808320, 65040796800, 256987987200, 1033805566080, 4222598688000, 17536408243200, 73886160096000

Offset: 1

Enrique Navarrete, May 27 2024

nonn

These occupied seats are an independent dominating set in the path graph of n vertices, and here also with an ordering of which person takes which seat.

a(n-2), n>2 counts the case where the first person who sits takes the leftmost seat (since that leaves all ways to fill the remaining n-2 seats).

			a(4)=6 since the seating arrangements in this case (where _ denotes an empty seat) are:
   1 _ 2 _
   1 _ _ 2
   _ 1 _ 2
   2 _ 1 _
   _ 2 _ 1
   2 _ _ 1.
a(3)=3 by the following seating arrangements (notice the number of people seated is not the same in each case),
   1 _ 2
   _ 1 _
   2 _ 1.
For n=7, the following are not valid seating arrangements since a fourth person can be seated in both cases:
   1 _ 2 _ _ _ 3
   _ _ 1 _ 3 _ 2.

Cf. A095236, A245963.

a(n) = Sum_{k>=1} A245963(n,k)*k!.

a(n) = ((n-1)*a(n-4) + 2*n*a(n-3) + (n+1)*a(n-2) - 3*a(n-1))/2, n>4.

a(11)-a(24) from Sean A. Irvine, Jun 17 2024

A095237 a(1)=1; then for n even, a(n)=(sum of previous terms times n) plus 1, for n odd, a(n)=(sum of previous terms times n) minus 1.

Original entry on oeis.org

1, 3, 11, 61, 379, 2731, 22301, 203897, 2064455, 22938391, 277554529, 3633441109, 51170962283, 771500662115, 12399117783989, 211611610180081, 3822234708877711, 72847296804492847, 1460993008134550985

Offset: 1

Amarnath Murthy, Jun 13 2004

nonn

Conjecture: There are infinitely many primes in this sequence.
The sequence would have been a little nicer if the even terms had a minus one and the odd a plus one, so the first term would not have to be an exception.
Except for the first two terms, it appears that a(n) are the first differences of A002467. - Carl Najafi, Sep 27 2018

Muniru A Asiru, Table of n, a(n) for n = 1..100

Cf. A095236.

Digits:=100: a:=n->factorial(n+1)-floor((factorial(n+1)+1)/exp(1))-factorial(n)+floor((factorial(n)+1)/exp(1)): 1,seq(a(n),n=2..20); # Muniru A Asiru, Sep 28 2018

a=vector(100); s=1; for(i=2,100,if(Mod(i,2)==0,a[i]=s*i+1,a[i]=s*i-1);s+=a[i])

a(n) = (n+1)! - floor(((n+1)!+1)/e) - n! + floor((n!+1)/e), n > 1. - Gary Detlefs, Nov 07 2010

Edited by Johan Claes, Jun 16 2004

A095698 Number of permutations of {1,2,3,...,n} where, for 1 < i <= n, the i-th number has maximized sum of the i-1 absolute differences from all previous numbers of the permutation.

Original entry on oeis.org

1, 2, 4, 6, 14, 18, 46, 54, 146, 162, 454, 486, 1394, 1458, 4246, 4374, 12866, 13122, 38854, 39366, 117074, 118098, 352246, 354294, 1058786, 1062882, 3180454, 3188646, 9549554, 9565938, 28665046, 28697814, 86027906, 86093442, 258149254

Offset: 1

Rick L. Shepherd, Jul 06 2004

Another variant of A095236: Here each phone after the first selected (which can still be any) is chosen such that the total distance in the normal sense from the chosen phone to all previously-chosen phones in the row is maximized. (Equivalently, the average distance is maximized.) Another space- or privacy-conscious selection strategy. Are there any applications of this sequence to phyllotaxy? Gregarious (or eavesdropping) strategy: If, instead, the total (average) distance is minimized, the sequence generated is 1,2,4,8,16,32,64,128,256,512,..., apparently the nonnegative powers of 2.
In the gregarious case (suggested by the above comment), the permutations that result are exactly those that avoid the permutation patterns 132 and 312. See link to Art of Problem Solving Forums for proof of formula below. - Joel B. Lewis, May 16 2009
Taking every other term gives A008776 (even-indexed terms) and A027649 (odd-indexed terms). - Joel B. Lewis, May 16 2009
With Lewis's formulas, the addition of the g.f.s for a(2*n) and a(2*n+1) yields the conjectures below: 2*x/(-3*x^2+1) - (-x^2+1)/(-6*x^4+5*x^2-1) = (-4*x^3-x^2+2*x+1)/(6*x^4-5*x^2+1). - Georg Fischer, Nov 19 2022

			a(4)=6 as these six permutations of {1,2,3,4} are counted (as in A095236(4)): (1,4,2,3), (1,4,3,2), (2,4,1,3), (3,1,4,2), (4,1,2,3) and (4,1,3,2).
In particular, (2,4,3,1) and (3,1,2,4), counted in A095236(4), are not counted here.

Problem solved on the Art of Problem Solving forum, Urinal-choice permutations. [From _Joel B. Lewis_, May 16 2009, corrected from pers. comm.]
Index entries for linear recurrences with constant coefficients, signature (0, 5, 0, -6).

Cf. A008776, A027649, A095236.

CoefficientList[Series[(-4*x^3-x^2+2*x+1)/(6*x^4-5*x^2+1), {x,0,34}], x] (* Georg Fischer, Nov 19 2022 *)

a(1) = 1; Conjectured: For k >= 1, a(2k) = a(2k-1) + 2^(k-1) and a(2k+1) = 2*a(2k-1) + a(2k) (needs proof or a reference).
a(2n) = 2 * 3^(n - 1) for n >= 1. a(2n + 1) = 2 * 3^n - 2^n for n >= 0. - Joel B. Lewis, May 16 2009
Conjecture: a(n) = 5*a(n-2) - 6*a(n-4); g.f.: x*(1+2*x-x^2-4*x^3)/((1-2*x^2)*(1-3*x^2)). - Colin Barker, Jul 27 2012
Conjecture: a(n) = 2^(((-1)^n + 2*n - 5)/4)*((-1)^n-1) - 2*3^(((-1)^n + 2*n - 5)/4)*((-1)^n-2). - Luce ETIENNE, Dec 20 2014

More terms from Joel B. Lewis, May 16 2009

cp's OEIS Frontend

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

A192008 Modified linear phone booth sequence: number of ways to occupy n phone booths in a row, one by one, each time picking a phone booth adjacent to the smallest number of previously occupied phone booths.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A192009 Modified cyclic phone booth sequence: number of ways to occupy n labeled phone booths in a circle one by one, each time picking a phone booth adjacent to the smallest number of previously occupied phone booths.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A276657 Number of ways to occupy n unlabeled phone booths in a circle one by one, each time picking a phone booth adjacent to the smallest number of previously occupied phone booths.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Links

Crossrefs

A373182 Number of ways that people can sit in n linearly arranged seats such that there are one or two empty seats between any two persons, zero or one empty seats at the start and end, and at least one person gets seated.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions