|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|