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,3

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

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.

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

Prog

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

Crossrefs

Cf. A192009 (labeled case).

Cf. A095236, A192008.

Sequence in context: A287756 A287496 A003616 * A079895 A351512 A053047

Adjacent sequences: A276654 A276655 A276656 * A276658 A276659 A276660

Keyword

nonn

Author

Max Alekseyev, Sep 11 2016

Status

approved