login
Number of toroidal necklaces of positive integers summing to n.
15

%I #10 Aug 18 2019 22:29:06

%S 1,1,3,5,10,14,31,44,90,154,296,524,1035,1881,3636,6869,13208,25150,

%T 48585,93188,180192,347617,673201,1303259,2529740,4910708,9549665,

%U 18579828,36192118,70540863,137620889,268655549,524873503,1026068477,2007178821,3928564237

%N Number of toroidal necklaces of positive integers summing to n.

%C The 1-dimensional (necklace) case is A008965.

%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="/A323858/b323858.txt">Table of n, a(n) for n = 0..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 Inequivalent representatives of the a(6) = 31 toroidal necklaces:

%e 6 15 24 33 114 123 132 222 1113 1122 1212 11112 111111

%e .

%e 1 2 3 11 11 12 12 111

%e 5 4 3 13 22 12 21 111

%e .

%e 1 1 1 2 11

%e 1 2 3 2 11

%e 4 3 2 2 11

%e .

%e 1 1 1

%e 1 1 2

%e 1 2 1

%e 3 2 2

%e .

%e 1

%e 1

%e 1

%e 1

%e 2

%e .

%e 1

%e 1

%e 1

%e 1

%e 1

%e 1

%t primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];

%t ptnmats[n_]:=Union@@Permutations/@Select[Union@@(Tuples[Permutations/@#]&/@Map[primeMS,facs[n],{2}]),SameQ@@Length/@#&];

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

%t Table[Length[Join@@Table[Select[ptnmats[k],neckmatQ],{k,Times@@Prime/@#&/@IntegerPartitions[n]}]],{n,10}]

%o (PARI)

%o 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))));

%o 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

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

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

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 04 2019

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