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.

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

Author

Max Alekseyev, Sep 11 2016

Keywords

• nonn

Comments

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

Links

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

Crossrefs

Cf. A192009 (labeled case).

Cf. A095236, A192008.

Programs

Mathematica

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

PARI

{ 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; }

Formula

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.