cp's OEIS Frontend

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

%I A323858 #10 Aug 18 2019 22:29:06
%S A323858 1,1,3,5,10,14,31,44,90,154,296,524,1035,1881,3636,6869,13208,25150,
%T A323858 48585,93188,180192,347617,673201,1303259,2529740,4910708,9549665,
%U A323858 18579828,36192118,70540863,137620889,268655549,524873503,1026068477,2007178821,3928564237
%N A323858 Number of toroidal necklaces of positive integers summing to n.
%C A323858 The 1-dimensional (necklace) case is A008965.
%C A323858 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 A323858 Andrew Howroyd, <a href="/A323858/b323858.txt">Table of n, a(n) for n = 0..200</a>
%H A323858 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 A323858 Inequivalent representatives of the a(6) = 31 toroidal necklaces:
%e A323858   6  15  24  33  114  123  132  222  1113  1122  1212  11112  111111
%e A323858 .
%e A323858   1  2  3  11  11  12  12  111
%e A323858   5  4  3  13  22  12  21  111
%e A323858 .
%e A323858   1  1  1  2  11
%e A323858   1  2  3  2  11
%e A323858   4  3  2  2  11
%e A323858 .
%e A323858   1  1  1
%e A323858   1  1  2
%e A323858   1  2  1
%e A323858   3  2  2
%e A323858 .
%e A323858   1
%e A323858   1
%e A323858   1
%e A323858   1
%e A323858   2
%e A323858 .
%e A323858   1
%e A323858   1
%e A323858   1
%e A323858   1
%e A323858   1
%e A323858   1
%t A323858 primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
%t A323858 facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
%t A323858 ptnmats[n_]:=Union@@Permutations/@Select[Union@@(Tuples[Permutations/@#]&/@Map[primeMS,facs[n],{2}]),SameQ@@Length/@#&];
%t A323858 neckmatQ[m_]:=m==First[Union@@Table[RotateLeft[m,{i,j}],{i,Length[m]},{j,Length[First[m]]}]];
%t A323858 Table[Length[Join@@Table[Select[ptnmats[k],neckmatQ],{k,Times@@Prime/@#&/@IntegerPartitions[n]}]],{n,10}]
%o A323858 (PARI)
%o A323858 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 A323858 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 A323858 Cf. A000031, A000670, A008965, A059966, A101509, A179043, A184271.
%Y A323858 Cf. A323859, A323861, A323865, A323866, A323870.
%K A323858 nonn
%O A323858 0,3
%A A323858 _Gus Wiseman_, Feb 04 2019
%E A323858 Terms a(18) and beyond from _Andrew Howroyd_, Aug 18 2019