login
A323870
Number of toroidal necklaces of size n whose entries cover an initial interval of positive integers.
13
1, 4, 10, 61, 218, 3136, 13514, 272998, 2362439, 40899248, 295024106, 14045787790, 81055130522, 3040383719360, 61408850927732, 1661142088494553, 15337737297545402, 1128511554421317128, 9768588138876674858, 803306338873366385030, 15452347618762680757428
OFFSET
1,2
COMMENTS
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.
LINKS
S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.
EXAMPLE
The a(3) = 10 toroidal necklaces:
[1 2 3] [1 3 2] [1 2 2] [1 1 2] [1 1 1]
.
[1] [1] [1] [1] [1]
[2] [3] [2] [1] [1]
[3] [2] [2] [2] [1]
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]}];
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m, {i, j}], {i, Length[m]}, {j, Length[First[m]]}]];
Table[Length[Select[nrmmats[n], neckmatQ]], {n, 6}]
PROG
(PARI)
U(n, m, k) = (1/(n*m)) * sumdiv(n, c, sumdiv(m, d, eulerphi(c) * eulerphi(d) * k^(n*m/lcm(c, d))));
R(v)={sum(n=1, #v, sum(k=1, n, (-1)^(n-k)*binomial(n, k)*v[k]))}
a(n)={if(n < 1, n==0, R(vector(n, k, sumdiv(n, d, U(d, n/d, k))) ))} \\ Andrew Howroyd, Aug 18 2019
KEYWORD
nonn
AUTHOR
Gus Wiseman, Feb 04 2019
EXTENSIONS
Terms a(9) and beyond from Andrew Howroyd, Aug 18 2019
STATUS
approved