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

%I #8 Aug 18 2019 22:29:36

%S 1,4,10,61,218,3136,13514,272998,2362439,40899248,295024106,

%T 14045787790,81055130522,3040383719360,61408850927732,

%U 1661142088494553,15337737297545402,1128511554421317128,9768588138876674858,803306338873366385030,15452347618762680757428

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

%C 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.

%H Andrew Howroyd, <a href="/A323870/b323870.txt">Table of n, a(n) for n = 1..200</a>

%H S. N. Ethier, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Ethier/ethier2.html">Counting toroidal binary arrays</a>, J. Int. Seq. 16 (2013) #13.4.7.

%e The a(3) = 10 toroidal necklaces:

%e [1 2 3] [1 3 2] [1 2 2] [1 1 2] [1 1 1]

%e .

%e [1] [1] [1] [1] [1]

%e [2] [3] [2] [1] [1]

%e [3] [2] [2] [2] [1]

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t 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]}];

%t neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];

%t Table[Length[Select[nrmmats[n],neckmatQ]],{n,6}]

%o (PARI)

%o U(n,m,k) = (1/(n*m)) * sumdiv(n, c, sumdiv(m, d, eulerphi(c) * eulerphi(d) * k^(n*m/lcm(c, d))));

%o R(v)={sum(n=1, #v, sum(k=1, n, (-1)^(n-k)*binomial(n,k)*v[k]))}

%o a(n)={if(n < 1, n==0, R(vector(n, k, sumdiv(n, d, U(d, n/d, k))) ))} \\ _Andrew Howroyd_, Aug 18 2019

%Y Cf. A000670, A008965, A060223.

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

%K nonn

%O 1,2

%A _Gus Wiseman_, Feb 04 2019

%E Terms a(9) and beyond from _Andrew Howroyd_, Aug 18 2019