A323859 Number of binary toroidal necklaces of size n.

1, 2, 6, 8, 19, 16, 56, 40, 152, 184, 432, 376, 2132, 1264, 4728, 8768, 20688, 15424, 87656, 55192, 315128, 399520, 762984, 729448, 5595408, 4026576, 10325712, 19884504, 57527804, 37025584, 286340544, 138547336, 805335364, 1041204704, 2021176512, 3926827328

Offset

0,2

Comments

The 1-dimensional (necklace) case is A000031.

We define a toroidal necklace to be an equivalence class of matrices under all possible rotations of the sequence of rows and the sequence of columns. Alternatively, a toroidal necklace is a matrix that is minimal among all possible rotations of its sequence of rows and its sequence of columns.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.

Formula

a(n) = (1/n) * Sum_{d|n} Sum_{e|d, f|(n/d)} phi(e) * phi(f) * 2^(n/lcm(d,n/d)). [Ethier]

Example

Inequivalent representatives of the a(4) = 19 binary toroidal necklaces:
  [0 0 0 0] [0 0 0 1] [0 0 1 1] [0 1 0 1] [0 1 1 1] [1 1 1 1]
.
  [0 0] [0 0] [0 0] [0 1] [0 1] [0 1] [1 1]
  [0 0] [0 1] [1 1] [0 1] [1 0] [1 1] [1 1]
.
  [0] [0] [0] [0] [0] [1]
  [0] [0] [0] [1] [1] [1]
  [0] [0] [1] [0] [1] [1]
  [0] [1] [1] [1] [1] [1]

Mathematica

matcyc[m_]:=Union@@Table[RotateLeft[m, {i, j}], {i, Length[m]}, {j, Length[First[m]]}];
Table[If[n==0, 1, Length[Union[First/@matcyc/@Join@@(Table[Partition[#, d], {d, Divisors[n]}]&/@Tuples[{0, 1}, n])]]], {n, 0, 10}]

Prog

(PARI)
U(n, m, k) = (1/(n*m)) * sumdiv(n, c, sumdiv(m, d, eulerphi(c) * eulerphi(d) * k^(n*m/lcm(c, d))))
a(n) = if(n<1, n==0, sumdiv(n, d, U(n/d, d, 2))) \\ Andrew Howroyd, Jan 24 2023

Crossrefs

Cf. A000031, A008965, A179043, A184271, A323351.

Cf. A323858, A323859, A323865, A323870.

Sequence in context: A301799 A077638 A103015 * A365918 A098092 A221316

Adjacent sequences: A323856 A323857 A323858 * A323860 A323861 A323862

Keyword

nonn

Author

Gus Wiseman, Feb 04 2019

Status

approved