A086675 - OEIS

%I #17 Nov 30 2023 12:26:05

%S 1,2,10,176,16456,6710912,11453291200,80421421917440,

%T 2305843009750581376,268650182136584290872320,

%U 126765060022823052739661424640,241677817415439249618874010960064512,1858395433210885261795036719974526548094976

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

%C 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 Alois P. Heinz, <a href="/A086675/b086675.txt">Table of n, a(n) for n = 0..57</a>

%H 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 a(n) = (1/n)*Sum_{ d divides n } phi(d)*2^(n^2/d) for n > 0, a(0) = 1.

%e From _Gus Wiseman_, Mar 04 2019: (Start)

%e Inequivalent representatives of the a(2) = 10 digraphical necklace edge-sets:

%e   {}

%e   {(1,1)}

%e   {(1,2)}

%e   {(1,1),(1,2)}

%e   {(1,1),(2,1)}

%e   {(1,1),(2,2)}

%e   {(1,2),(2,1)}

%e   {(1,1),(1,2),(2,1)}

%e   {(1,1),(1,2),(2,2)}

%e   {(1,1),(1,2),(2,1),(2,2)}

%e (End)

%t Table[Fold[ #1+EulerPhi[ #2] 2^(n^2 /#2)&, 0, Divisors[n]]/n, {n, 16}]

%t (* second program *)

%t rotdigra[g_,m_]:=Sort[g/.k_Integer:>If[k==m,1,k+1]];

%t 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 Cf. A000031 (binary necklaces), A000939 (cycle necklaces), A008965, A060690, A061417 (permutation necklaces), A184271, A192332 (graphical necklaces), A275527 (path necklaces), A323858 (toroidal necklaces), A323870.

%Y Cf. A324463, A324464, A324513, A324514.

%K nonn,easy

%O 0,2

%A Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 27 2003

%E More terms from _Wouter Meeussen_, Jul 29 2003

%E a(0)=1 prepended by _Gus Wiseman_, Mar 04 2019