A323871 Number of aperiodic toroidal necklaces of size n whose entries cover an initial interval of positive integers.

1, 2, 8, 53, 216, 3112, 13512, 272844, 2362412, 40898808, 295024104, 14045779864, 81055130520, 3040383692328, 61408850927280, 1661142087743940, 15337737297545400, 1128511554416582908, 9768588138876674856, 803306338873264137240, 15452347618762680730384

Offset: 1

Author

Gus Wiseman, Feb 04 2019

Keywords

• nonn

Comments

The 1-dimensional (Lyndon word) case is A060223.

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.

Examples

			The a(3) = 8 aperiodic toroidal necklaces:
  [1 2 3] [1 3 2] [1 2 2] [1 1 2]
.
  [1] [1] [1] [1]
  [2] [3] [2] [1]
  [3] [2] [2] [2]
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.

Crossrefs

Cf. A000670, A000740, A008965, A060223.

Cf. A323858, A323859, A323860, A323861, A323866, A323867, A323868, A323870.

Programs

GAP

List([1..30], A323871); # See A323861 for code; Andrew Howroyd, Aug 21 2019

Mathematica

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
nrmmats[n_]:=Join@@Table[Table[Table[Position[stn,{i,j}][[1,1]],{i,d},{j,n/d}],{stn,Join@@Permutations/@sps[Tuples[{Range[d],Range[n/d]}]]}],{d,Divisors[n]}];
apermatQ[m_]:=UnsameQ@@Join@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}];
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
Table[Length[Select[nrmmats[n],neckmatQ[#]&&apermatQ[#]&]],{n,6}]

Extensions

Terms a(9) and beyond from Andrew Howroyd, Aug 21 2019