login
A323871
Number of aperiodic toroidal necklaces of size n whose entries cover an initial interval of positive integers.
11
1, 2, 8, 53, 216, 3112, 13512, 272844, 2362412, 40898808, 295024104, 14045779864, 81055130520, 3040383692328, 61408850927280, 1661142087743940, 15337737297545400, 1128511554416582908, 9768588138876674856, 803306338873264137240, 15452347618762680730384
OFFSET
1,2
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.
LINKS
S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.
EXAMPLE
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]
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}]
PROG
(GAP) List([1..30], A323871); # See A323861 for code; Andrew Howroyd, Aug 21 2019
KEYWORD
nonn
AUTHOR
Gus Wiseman, Feb 04 2019
EXTENSIONS
Terms a(9) and beyond from Andrew Howroyd, Aug 21 2019
STATUS
approved