login
Table read by antidiagonals where A(n,k) is the number of n X k aperiodic binary toroidal necklaces.
14

%I #14 Aug 22 2019 20:47:29

%S 2,1,1,2,2,2,3,9,9,3,6,27,54,27,6,9,99,335,335,99,9,18,326,2182,4050,

%T 2182,326,18,30,1161,14523,52377,52377,14523,1161,30,56,4050,99858,

%U 698535,1342170,698535,99858,4050,56,99,14532,698870,9586395,35790267,35790267,9586395,698870,14532,99

%N Table read by antidiagonals where A(n,k) is the number of n X k aperiodic binary toroidal necklaces.

%C The 1-dimensional (Lyndon word) case is A001037.

%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. An n X k matrix is aperiodic if all n * k rotations of its sequence of rows and its sequence of columns are distinct.

%H Andrew Howroyd, <a href="/A323861/b323861.txt">Table of n, a(n) for n = 1..1275</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.

%H Andrew Howroyd, <a href="/A323861/a323861.txt">GAP Program Code</a>

%e Table begins:

%e 1 2 3 4

%e ------------------------

%e 1: | 2 1 2 3

%e 2: | 1 2 9 27

%e 3: | 2 9 54 335

%e 4: | 3 27 335 4050

%e Inequivalent representatives of the A(3,2) = 9 aperiodic toroidal necklaces:

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

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

%t apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];

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

%t Table[Length[Select[Partition[#,n-k]&/@Tuples[{0,1},(n-k)*k],And[apermatQ[#],neckmatQ[#]]&]],{n,6},{k,n-1}]

%o (GAP) # See link for code.

%o for n in [1..8] do for k in [1..8] do Print(A323861(n,k), ", "); od; Print("\n"); od; # _Andrew Howroyd_, Aug 21 2019

%Y First and last columns are A001037. Main diagonal is A323872.

%Y Cf. A000031, A000740, A027375, A059966, A179043, A184271.

%Y Cf. A323859, A323860, A323865, A323866, A323871.

%K nonn,tabl

%O 1,1

%A _Gus Wiseman_, Feb 04 2019

%E Terms a(37) and beyond from _Andrew Howroyd_, Aug 21 2019