A323858 Number of toroidal necklaces of positive integers summing to n.

1, 1, 3, 5, 10, 14, 31, 44, 90, 154, 296, 524, 1035, 1881, 3636, 6869, 13208, 25150, 48585, 93188, 180192, 347617, 673201, 1303259, 2529740, 4910708, 9549665, 18579828, 36192118, 70540863, 137620889, 268655549, 524873503, 1026068477, 2007178821, 3928564237

Offset

0,3

Comments

The 1-dimensional (necklace) case is A008965.

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

Andrew Howroyd, Table of n, a(n) for n = 0..200

S. N. Ethier, Counting toroidal binary arrays, J. Int. Seq. 16 (2013) #13.4.7.

Example

Inequivalent representatives of the a(6) = 31 toroidal necklaces:
  6  15  24  33  114  123  132  222  1113  1122  1212  11112  111111
.
  1  2  3  11  11  12  12  111
  5  4  3  13  22  12  21  111
.
  1  1  1  2  11
  1  2  3  2  11
  4  3  2  2  11
.
  1  1  1
  1  1  2
  1  2  1
  3  2  2
.
  1
  1
  1
  1
  2
.
  1
  1
  1
  1
  1
  1

Mathematica

primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
ptnmats[n_]:=Union@@Permutations/@Select[Union@@(Tuples[Permutations/@#]&/@Map[primeMS, facs[n], {2}]), SameQ@@Length/@#&];
neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m, {i, j}], {i, Length[m]}, {j, Length[First[m]]}]];
Table[Length[Join@@Table[Select[ptnmats[k], neckmatQ], {k, Times@@Prime/@#&/@IntegerPartitions[n]}]], {n, 10}]

Prog

(PARI)
U(n, m, k) = (1/(n*m)) * sumdiv(n, c, sumdiv(m, d, eulerphi(c) * eulerphi(d) * subst(k, x, x^lcm(c, d))^(n*m/lcm(c, d))));
a(n)={if(n < 1, n==0, sum(i=1, n, sum(j=1, n\i, polcoef(U(i, j, x/(1-x) + O(x*x^n)), n))))} \\ Andrew Howroyd, Aug 18 2019

Crossrefs

Cf. A000031, A000670, A008965, A059966, A101509, A179043, A184271.

Cf. A323859, A323861, A323865, A323866, A323870.

Sequence in context: A182722 A365379 A089483 * A190484 A190545 A190557

Adjacent sequences: A323855 A323856 A323857 * A323859 A323860 A323861

Keyword

nonn

Author

Gus Wiseman, Feb 04 2019

Extensions

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

Status

approved