cp's OEIS Frontend

A086675 Number of n X n (0,1)-matrices modulo cyclic permutations of the rows.

%I A086675 #17 Nov 30 2023 12:26:05
%S A086675 1,2,10,176,16456,6710912,11453291200,80421421917440,
%T A086675 2305843009750581376,268650182136584290872320,
%U A086675 126765060022823052739661424640,241677817415439249618874010960064512,1858395433210885261795036719974526548094976
%N A086675 Number of n X n (0,1)-matrices modulo cyclic permutations of the rows.
%C A086675 Also the number of digraphical necklaces with n vertices. A digraphical necklace is defined to be a directed graph that is minimal among all n rotations of the vertices. Alternatively, it is an equivalence class of directed graphs under rotation of the vertices. These are a kind of partially labeled digraphs. - _Gus Wiseman_, Mar 04 2019
%H A086675 Alois P. Heinz, <a href="/A086675/b086675.txt">Table of n, a(n) for n = 0..57</a>
%H A086675 Peter Kagey and William Keehn, <a href="https://arxiv.org/abs/2311.13072">Counting tilings of the n X m grid, cylinder, and torus</a>, arXiv:2311.13072 [math.CO], 2023. See p. 3.
%F A086675 a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n^2/d) for n > 0, a(0) = 1.
%e A086675 From _Gus Wiseman_, Mar 04 2019: (Start)
%e A086675 Inequivalent representatives of the a(2) = 10 digraphical necklace edge-sets:
%e A086675   {}
%e A086675   {(1,1)}
%e A086675   {(1,2)}
%e A086675   {(1,1),(1,2)}
%e A086675   {(1,1),(2,1)}
%e A086675   {(1,1),(2,2)}
%e A086675   {(1,2),(2,1)}
%e A086675   {(1,1),(1,2),(2,1)}
%e A086675   {(1,1),(1,2),(2,2)}
%e A086675   {(1,1),(1,2),(2,1),(2,2)}
%e A086675 (End)
%t A086675 Table[Fold[ #1+EulerPhi[ #2] 2^(n^2 /#2)&, 0, Divisors[n]]/n, {n, 16}]
%t A086675 (* second program *)
%t A086675 rotdigra[g_,m_]:=Sort[g/.k_Integer:>If[k==m,1,k+1]];
%t A086675 Table[Length[Select[Subsets[Tuples[Range[n],2]],#=={}||#==First[Sort[Table[Nest[rotdigra[#,n]&,#,j],{j,n}]]]&]],{n,0,4}] (* _Gus Wiseman_, Mar 04 2019 *)
%Y A086675 Cf. A000031 (binary necklaces), A000939 (cycle necklaces), A008965, A060690, A061417 (permutation necklaces), A184271, A192332 (graphical necklaces), A275527 (path necklaces), A323858 (toroidal necklaces), A323870.
%Y A086675 Cf. A324463, A324464, A324513, A324514.
%K A086675 nonn,easy
%O A086675 0,2
%A A086675 Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 27 2003
%E A086675 More terms from _Wouter Meeussen_, Jul 29 2003
%E A086675 a(0)=1 prepended by _Gus Wiseman_, Mar 04 2019