login
Number of binary toroidal necklaces of size n.
12

%I #9 Jan 24 2023 23:12:09

%S 1,2,6,8,19,16,56,40,152,184,432,376,2132,1264,4728,8768,20688,15424,

%T 87656,55192,315128,399520,762984,729448,5595408,4026576,10325712,

%U 19884504,57527804,37025584,286340544,138547336,805335364,1041204704,2021176512,3926827328

%N Number of binary toroidal necklaces of size n.

%C The 1-dimensional (necklace) case is A000031.

%C 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.

%H Andrew Howroyd, <a href="/A323859/b323859.txt">Table of n, a(n) for n = 0..1000</a>

%H S. N. Ethier, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Ethier/ethier2.html">Counting toroidal binary arrays</a>, J. Int. Seq. 16 (2013) #13.4.7.

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

%e Inequivalent representatives of the a(4) = 19 binary toroidal necklaces:

%e [0 0 0 0] [0 0 0 1] [0 0 1 1] [0 1 0 1] [0 1 1 1] [1 1 1 1]

%e .

%e [0 0] [0 0] [0 0] [0 1] [0 1] [0 1] [1 1]

%e [0 0] [0 1] [1 1] [0 1] [1 0] [1 1] [1 1]

%e .

%e [0] [0] [0] [0] [0] [1]

%e [0] [0] [0] [1] [1] [1]

%e [0] [0] [1] [0] [1] [1]

%e [0] [1] [1] [1] [1] [1]

%t matcyc[m_]:=Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];

%t Table[If[n==0,1,Length[Union[First/@matcyc/@Join@@(Table[Partition[#,d],{d,Divisors[n]}]&/@Tuples[{0,1},n])]]],{n,0,10}]

%o (PARI)

%o U(n, m, k) = (1/(n*m)) * sumdiv(n, c, sumdiv(m, d, eulerphi(c) * eulerphi(d) * k^(n*m/lcm(c, d))))

%o a(n) = if(n<1, n==0, sumdiv(n, d, U(n/d, d, 2))) \\ _Andrew Howroyd_, Jan 24 2023

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

%Y Cf. A323858, A323859, A323865, A323870.

%K nonn

%O 0,2

%A _Gus Wiseman_, Feb 04 2019