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

1, 4, 10, 61, 218, 3136, 13514, 272998, 2362439, 40899248, 295024106, 14045787790, 81055130522, 3040383719360, 61408850927732, 1661142088494553, 15337737297545402, 1128511554421317128, 9768588138876674858, 803306338873366385030, 15452347618762680757428

Offset: 1

Author

Gus Wiseman, Feb 04 2019

Keywords

• nonn

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.

Examples

			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]
		

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, A008965, A060223.

Cf. A323858, A323859, A323866, A323868, A323871.

Programs

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}]

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

Extensions

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